您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“java二叉搜索樹使用實例分析”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學(xué)習(xí)“java二叉搜索樹使用實例分析”吧!
二叉搜索樹又稱二叉排序樹,它或者是一棵空樹,或者是具有以下性質(zhì)的二叉樹:
1、若它的左子樹不為空,則左子樹上所有節(jié)點的值都小于根結(jié)點的值。
2、若它的右子樹不為空,則右子樹上所有節(jié)點的值都大于根結(jié)點的值。
3、它的左右子樹也分別為二叉搜索樹
假設(shè)我們已經(jīng)構(gòu)造好了一個這樣的二叉樹,如下圖
我們要思考的第一個問題是如何查找某個值是否在該二叉樹中?
根據(jù)上述的邏輯,我們來把搜索的方法進行完善。
根據(jù)上述邏輯,我們來寫一個插入節(jié)點的代碼。
再來分析一下:curDummy 和 parentDummy 是怎么找到“替罪羊”的。
class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int val){ this.val = val; } } public class BinarySearchTree { TreeNode root; //在二叉樹中 尋找指定 val 值的節(jié)點 // 找到了,返回其節(jié)點地址;沒找到返回 null public TreeNode search(int key){ TreeNode cur = this.root; while(cur != null){ if(cur.val == key){ return cur; }else if(cur.val < key){ cur = cur.right; }else{ cur = cur.left; } } return null; } // 插入操作 public boolean insert(int key){ if(this.root == null){ this.root = new TreeNode(key); return true; } TreeNode cur = this.root; TreeNode parent = null; while(cur!=null){ if(key > cur.val){ parent = cur; cur = cur.right; }else if(cur.val == key){ return false; }else{ parent = cur; cur = cur.left; } } TreeNode node = new TreeNode(key); if(parent .val > key){ parent.left = node; }else{ parent.right = node; } return true; } // 刪除操作 public void remove(int key){ TreeNode cur = root; TreeNode parent = null; // 尋找 刪除節(jié)點位置。 while(cur!=null){ if(cur.val == key){ removeNode(cur,parent);// 真正刪除節(jié)點的代碼 break; }else if(cur.val < key){ parent = cur; cur = cur.right; }else{ parent = cur; cur = cur.left; } } } // 輔助刪除方法:真正刪除節(jié)點的代碼 private void removeNode(TreeNode cur,TreeNode parent){ // 情況一 if(cur.left == null){ if(cur == this.root){ this.root = this.root.right; }else if( cur == parent.left){ parent.left = cur.right; }else{ parent.right = cur.right; } // 情況二 }else if(cur.right == null){ if(cur == this.root){ this.root = root.left; }else if(cur == parent.left){ parent.left = cur.left; }else{ parent.right = cur.left; } // 情況三 }else{ // 第二種方法:在刪除節(jié)點的右子樹中尋找最小值, TreeNode parentDummy = cur; TreeNode curDummy = cur.right; while(curDummy.left != null){ parentDummy = curDummy; curDummy = curDummy.left; } // 此時 curDummy 指向的 cur 右子樹 cur.val = curDummy.val; if(parentDummy.left != curDummy){ parentDummy.right = curDummy.right; }else{ parentDummy.left = curDummy.right; } } } // 中序遍歷 public void inorder(TreeNode root){ if(root == null){ return; } inorder(root.left); System.out.print(root.val+" "); inorder(root.right); } public static void main(String[] args) { int[] array = {10,8,19,3,9,4,7}; BinarySearchTree binarySearchTree = new BinarySearchTree(); for (int i = 0; i < array.length; i++) { binarySearchTree.insert(array[i]); } binarySearchTree.inorder(binarySearchTree.root); System.out.println();// 換行 System.out.print("插入重復(fù)的數(shù)據(jù) 9:" + binarySearchTree.insert(9)); System.out.println();// 換行 System.out.print("插入不重復(fù)的數(shù)據(jù) 1:" + binarySearchTree.insert(1)); System.out.println();// 換行 binarySearchTree.inorder(binarySearchTree.root); System.out.println();// 換行 binarySearchTree.remove(19); System.out.print("刪除元素 19 :"); binarySearchTree.inorder(binarySearchTree.root); System.out.println();// 換行 System.out.print("查找不存在的數(shù)據(jù)50 :"); System.out.println(binarySearchTree.search(50)); System.out.print("查找存在的數(shù)據(jù) 7:"); System.out.println(binarySearchTree.search(7)); } }
  插入和刪除操作都必須先查找,查找效率代表了二叉搜索樹中各個操作的性能。
 
  對有n個結(jié)點的二叉搜索樹,若每個元素查找的概率相等,則二叉搜索樹平均查找長度是結(jié)點在二叉搜索樹的深度的函數(shù),即結(jié)點越深,則比較次數(shù)越多。
 
  但對于同一個關(guān)鍵碼集合,如果各關(guān)鍵碼插入的次序不同,可能得到不同結(jié)構(gòu)的二叉搜索樹:如果我們能保證 二叉搜索樹的左右子樹高度差不超過1。盡量滿足高度平衡條件。
這就成 AVL 樹了(高度平衡的二叉搜索樹)。而AVL樹,也有缺點:需要一個頻繁的旋轉(zhuǎn)。浪費很多效率。
至此 紅黑樹就誕生了,避免更多的旋轉(zhuǎn)。
TreeMap 和 TreeSet 即 java 中利用搜索樹實現(xiàn)的 Map 和 Set;實際上用的是紅黑樹,而紅黑樹是一棵近似平衡的二叉搜索樹,即在二叉搜索樹的基礎(chǔ)之上 + 顏色以及紅黑樹性質(zhì)驗證,關(guān)于紅黑樹的內(nèi)容,等博主學(xué)了,會寫博客的。
到此,相信大家對“java二叉搜索樹使用實例分析”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。