Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實現(xiàn)
1 二叉排序樹的概述
本文沒有介紹一些基礎(chǔ)知識。對于常見查找算法,比如順序查找、二分查找、插入查找、斐波那契查找還不清楚的,可以看這篇文章:常見查找算法詳解以及Java代碼的實現(xiàn)。
假設(shè)查找的數(shù)據(jù)集是普通的順序存儲,那么插入操作就是將記錄放在表的末端,給表記錄數(shù)加一即可,刪除操作可以是刪除后,后面的記錄向前移,也可以是要刪除的元素與最后一個元素互換,表記錄數(shù)減一,反正整個數(shù)據(jù)集也沒有什么順序,這樣的效率也不錯。應(yīng)該說,插入和刪除對于順序存儲結(jié)構(gòu)來說,效率是可以接受的,但這樣的表由于無序造成查找的效率很低。
如果查找的數(shù)據(jù)集是有序線性表,并且是順序存儲的,查找可以用折半、插值、斐波那契等查找算法來實現(xiàn),可惜,因為有序,在插入和刪除操作上,為了維持順序,需要移動大量元素,就需要耗費大量的時間。
有沒有一種即可以使得插入和刪除效率不錯,又可以比較高效率地實現(xiàn)查找的算法呢?這就是二叉排序樹。
二叉排序樹(Binary Sort Tree),又稱為二叉查找樹/二叉搜索樹(binary search tree)。它是具有下列性質(zhì)的二叉樹:
- 若它的左子樹不空,則左子樹上所有節(jié)點的值均小于它的根結(jié)構(gòu)的值;
- 若它的右子樹不空,則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值;
- 它的左、右子樹也分別為二叉排序樹;
- 二叉排序樹也可以是一個空樹。
構(gòu)造一棵二叉排序樹的目的,其主要目的并不是為了排序,而是為了提高查找和插入刪除關(guān)鍵字的速度,用以提升數(shù)據(jù)結(jié)構(gòu)的綜合能力。不管怎么說,在一個有序數(shù)據(jù)集上的查找,速度總是要快于無序的數(shù)據(jù)集的,而二叉排序樹這種非線性的結(jié)構(gòu),也有利于插入和刪除的實現(xiàn)。
2 二叉排序樹的構(gòu)建
2.1 類架構(gòu)
首先,最簡單的節(jié)點對象還是需要一個數(shù)據(jù)域和兩個引用域。
另外還需要一個比較器的引用,因為需要對元素進行排序,自然需要比較元素的大小,如果外部傳遞了比較器,那么就使用用戶指定的比較器進行比較,否則,數(shù)據(jù)類型E必須是Comparable接口的子類,否則因為不能比較而報錯。
另外,還需要提供中序遍歷的方法,該遍歷方法對于二叉排序樹的結(jié)果將會順序展示。
public class BinarySearchTree<E> { /** * 外部保存根節(jié)點的引用 */ private BinaryTreeNode<E> root; /** * 自定義比較器 */ private Comparator<? super E> cmp; /** * 樹節(jié)點的數(shù)量 */ private int size; /** * 內(nèi)部節(jié)點對象 * * @param <E> 數(shù)據(jù)類型 */ public static class BinaryTreeNode<E> { //數(shù)據(jù)域 E data; //左子節(jié)點 BinaryTreeNode<E> left; //右子節(jié)點 BinaryTreeNode<E> right; public BinaryTreeNode(E data) { this.data = data; } @Override public String toString() { return data.toString(); } } /** * 指定比較器 * * @param cmp 比較器 */ public BinarySearchTree(Comparator<? super E> cmp) { this.cmp = cmp; } /** * 空構(gòu)造器 */ public BinarySearchTree() { } /** * 是否是空樹 * * @return true 是 ;false 否 */ public boolean isEmpty() { return size == 0; } /** * 返回節(jié)點數(shù) * * @return 節(jié)點數(shù) */ public int size() { return size; } /** * 對元素進行比較大小的方法,如果傳遞了自定義比較器,則使用自定義比較器,否則則需要數(shù)據(jù)類型實現(xiàn)Comparable接口 * * @param e1 被比較的第一個對象 * @param e2 被比較的第二個對象 * @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2 */ private int compare(E e1, E e2) { if (cmp != null) { return cmp.compare(e1, e2); } else { return ((Comparable<E>) e1).compareTo(e2); } } /** * 保存遍歷出來的節(jié)點數(shù)據(jù) */ List<BinaryTreeNode<E>> str = new ArrayList<>(); /** * 中序遍歷,提供給外部使用的api * * @return 遍歷的數(shù)據(jù) */ public String toInorderTraversalString() { //如果是空樹,直接返回空 if (isEmpty()) { return null; } //從根節(jié)點開始遞歸 inorderTraversal(root); //獲取遍歷結(jié)果 String s = str.toString(); str.clear(); return s; } /** * 中序遍歷 內(nèi)部使用的遞歸遍歷方法,借用了棧的結(jié)構(gòu) * * @param root 節(jié)點,從根節(jié)點開始 */ private void inorderTraversal(BinaryTreeNode<E> root) { BinaryTreeNode<E> left = getLeft(root); if (left != null) { //如果左子節(jié)點不為null,則繼續(xù)遞歸遍歷該左子節(jié)點 inorderTraversal(left); } //添加數(shù)據(jù)節(jié)點 str.add(root); //獲取節(jié)點的右子節(jié)點 BinaryTreeNode<E> right = getRight(root); if (right != null) { //如果右子節(jié)點不為null,則繼續(xù)遞歸遍歷該右子節(jié)點 inorderTraversal(right); } } /** * 獲取左子節(jié)點 * * @param parent 父節(jié)點引用 * @return 左子節(jié)點或者null--表示沒有左子節(jié)點 */ public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) { return parent == null ? null : parent.left; } /** * 獲取右子節(jié)點 * * @param parent 父節(jié)點引用 * @return 右子節(jié)點或者null--表示沒有右子節(jié)點 */ public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) { return parent == null ? null : parent.right; } /** * 獲取根節(jié)點 * * @return 根節(jié)點 ;或者null--表示空樹 */ public BinaryTreeNode<E> getRoot() { return root; } }
2.2 查找的方法
查找的方法很簡單:
- 若根節(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字,成功,返回true;
- 否則,若小于根節(jié)點的關(guān)鍵字值,遞歸查左子樹;
- 若大于根節(jié)點的關(guān)鍵字值,遞歸查右子樹;
- 最終查找到葉子節(jié)點還是沒有數(shù)據(jù),那么查找失敗,則返回false。
/** * 查找,開放給外部使用的api */ public boolean contains(E e) { return contains(e, root); } /** * 查找,內(nèi)部調(diào)用的方法,從根節(jié)點開始查找 * * @param e 要查找的元素 * @param root 節(jié)點 * @return false 不存在 true 存在 */ private boolean contains(E e, BinaryTreeNode<E> root) { /*null校驗*/ if (root == null) { return false; } /*調(diào)用比較的方法*/ int i = compare(e, root.data); /*如果大于0,則說明e>root.date 繼續(xù)查詢右子樹*/ if (i > 0) { return contains(e, root.right); /*如果小于0,則說明e<root.date 繼續(xù)查詢左子樹*/ } else if (i < 0) { return contains(e, root.left); } else { /*如果等于0,則說明e=root.date 即查詢成功*/ return true; } }
2.3 插入的方法
有了二叉排序樹的查找函數(shù),那么所謂的二叉排序樹的插入,其實也就是將關(guān)鍵字放到樹中的合適位置而已,插入操作就好像在調(diào)用查找的操作,如果找到了那么什么都不做,返回false,如果沒找到,則將要插入的元素插入到遍歷的路徑的最后一點上:
- 若二叉樹為空。則單獨生成根節(jié)點,返回true。
- 執(zhí)行查找算法,找出被插節(jié)點的父親節(jié)點。
- 判斷被插節(jié)點是其父親節(jié)點的左、右兒子。將被插節(jié)點作為葉子節(jié)點插入,返回true。如果原節(jié)點存在那么什么都不做,返回false。注意:新插入的節(jié)點總是葉子節(jié)點。
/** * 插入,開放給外部使用的api * * @param e 要插入的元素 */ public void insert(E e) { //返回root,但此時新的節(jié)點可能已經(jīng)被插入進去了 root = insert(e, root); } /** * 插入,開放給外部使用的api * * @param es 要插入的元素的數(shù)組,注意,數(shù)組元素的順序存儲的位置將會影響二叉排序樹的生成 */ public void insert(E[] es) { //返回root,但此時新的節(jié)點可能已經(jīng)被插入進去了 for (E e : es) { root = insert(e, root); } } /** * 插入,內(nèi)部調(diào)用的方法,先從根節(jié)點開始遞歸查找要插入的位置,然后插入 * * @param e 要插入的數(shù)據(jù) * @param root 節(jié)點 * @return 原節(jié)點或者新插入的節(jié)點 */ private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) { /*沒有查找到,那么直接構(gòu)建新的節(jié)點返回,將會在上一層方法中被賦值給其父節(jié)點的某個引用,這個插入的位置肯定是該遍歷路徑上的最后一點 * 即插入的元素節(jié)點肯定是屬于葉子節(jié)點*/ if (root == null) { size++; return new BinaryTreeNode<>(e); } /*調(diào)用比較的方法*/ int i = compare(e, root.data); /*如果大于0,則說明e>root.date 繼續(xù)查詢右子樹*/ if (i > 0) { //重新賦值 root.right = insert(e, root.right); /*如果小于0,則說明e<root.date 繼續(xù)查詢左子樹*/ } else if (i < 0) { //重新賦值 root.left = insert(e, root.left); } else { /*如果等于0,則說明e=root.date 即存在節(jié)點 什么都不做*/ } //沒查詢到最底層,則返回該節(jié)點 return root; }
2.3.1 測試
現(xiàn)在我們想要構(gòu)建如下一顆排序二叉樹:
首先要插入根節(jié)點47,然后是第二層的節(jié)點16、73,然后是第三層的節(jié)點1、24、59、88,然后是第四層的節(jié)點20、35、62、77。每一層內(nèi)部節(jié)點的順序可以不一致,但是每一層之間的大順序一定要保持一致,否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結(jié)構(gòu)不能保證。
public class BinarySearchTreeTest { BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>(); @Test public void insert() { //首先要插入根節(jié)點47,然后是第二層的節(jié)點16,73,然后是第三層的節(jié)點1,24,59,88,然后是第四層的節(jié)點20,35,62,77。 // 每一層內(nèi)部節(jié)點的順序可以不一致,但是每一層之間的打順序一定要保持一致,否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結(jié)構(gòu)不能保證。 Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77}; binarySearchTree.insert(es); //中序遍歷輸出 System.out.println(binarySearchTree.toInorderTraversalString()); //查找某個數(shù)據(jù)是否存在 System.out.println(binarySearchTree.contains(1)); System.out.println(binarySearchTree.contains(2)); } }
在System.out處打上斷點,Debug,可以看到樹結(jié)構(gòu)和我們預想的一致,如果改變層間的大順序,那么使用Debug會發(fā)現(xiàn)樹結(jié)構(gòu)不如預期。
2.4 查找最大值和最小值
很簡單,最左邊的節(jié)點一定是最小的,最右邊的節(jié)點一定是最大的。因此查找最小的節(jié)點只需要向左遞歸查找,查找最大的節(jié)點只需要向右遞歸查找。
/** * 查找最小的節(jié)點 * * @param root 根節(jié)點 * @return 最小的節(jié)點 */ private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) { if (root == null) { return null; /*如果該節(jié)點沒有左右子節(jié)點,那么該節(jié)點就是最小的節(jié)點,返回*/ } else if (root.left == null) { return root; } /*如果該節(jié)點存在左子節(jié)點,那么繼續(xù)向左遞歸查找*/ return findMin(root.left); } /** * 查找最大的節(jié)點 * * @param root 根節(jié)點 * @return 最大的節(jié)點 */ private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) { if (root == null) { return null; /*如果該節(jié)點沒有右子節(jié)點,那么該節(jié)點就是最大的節(jié)點,返回*/ } else if (root.right == null) { return root; } /*如果該節(jié)點存在右子節(jié)點,那么繼續(xù)向右遞歸查找*/ return findMax(root.right); }
2.5 刪除的方法
對于二叉排序樹的刪除,就不是那么容易,我們不能因為刪除了節(jié)點,而讓這棵樹變得不滿足二叉排序樹的特性,所以刪除需要考慮多種情況。一共有三種情況需要考慮:
如果查找到的將要被刪除的節(jié)點沒有子節(jié)點,那么很簡單,直接刪除父節(jié)點對于該節(jié)點的引用即可,如下圖的紅色節(jié)點:
例如,刪除20之后:
如果查找到的將要被刪除的節(jié)點具有一個子節(jié)點,那么也很簡單,直接繞過該節(jié)點將原本父節(jié)點對于該節(jié)點的引用指向該節(jié)點的子節(jié)點即可,如下圖的紅色節(jié)點:
例如,刪除59之后:
如果查找到的將要被刪除的節(jié)點具有兩個子節(jié)點,那么就比較麻煩了,如下圖的紅色節(jié)點:
比如我們需要刪除73,那么我們就必須要找出一個已存在的能夠替代73的節(jié)點,然后刪除該節(jié)點。實際上該73節(jié)點的左子樹的最大節(jié)點62和右子樹的最小節(jié)點77都能夠替代73節(jié)點,即它們正好是二叉排序樹中比它小或比它大的最接近73的兩個數(shù)。
一般我們選擇一種方式即可,我們這次使用右子樹的最小節(jié)點替代要刪除的節(jié)點,使用77替代73之后的結(jié)構(gòu)如下:
完整的代碼如下:
/** * 刪除,開放給外部使用的api * * @param e 要刪除的元素 */ public void delete(E e) { //返回root,但此時可能有一個節(jié)點已經(jīng)被刪除了 root = delete(e, root); } /** * 刪除,內(nèi)部調(diào)用的方法,刪除分為三種情況: 1、該節(jié)點沒有子節(jié)點 2、該字節(jié)僅有一個子節(jié)點 3、該節(jié)點具有兩個子節(jié)點 * * @param e 要刪除的數(shù)據(jù) * @param root 根節(jié)點 * @return 該節(jié)點 */ private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) { /*沒有查找到,那么什么都不做*/ if (root == null) { return null; } /*調(diào)用比較的方法*/ int i = compare(e, root.data); /*如果大于0,則說明e>root.date 繼續(xù)查詢右子樹*/ if (i > 0) { //從新賦值 root.right = delete(e, root.right); /*如果小于0,則說明e<root.date 繼續(xù)查詢左子樹*/ } else if (i < 0) { //從新賦值 root.left = delete(e, root.left); } else { /*如果等于0,則說明e=root.date 即查詢成功 開始執(zhí)行刪除*/ /*如果兩個子節(jié)點都不為null*/ if (root.left != null && root.right != null) { /*方法1、遞歸查找最小的節(jié)點,然后遞歸刪除 該方法不推薦使用*/ //root.data = findMin(root.right).data; //root.right = delete(root.data, root.right); /*方法2、遞歸查找并刪除最小的節(jié)點 推薦*/ root.data = findAndDeleteMin(root.right, root); size--; } else { /*如果一個子節(jié)點不為null,則返回該子節(jié)點;或者兩個子節(jié)點都為null,則返回null * 此時該root節(jié)點已經(jīng)被"繞過了"*/ root = (root.left != null) ? root.left : root.right; size--; } } //沒查詢到最底層,則返回該節(jié)點 return root; } /** * 查找最小的節(jié)點并刪除 * 最小的節(jié)點肯定不存在兩個子節(jié)點,有可能沒有子節(jié)點,有可能存在右子節(jié)點 * * @param root 節(jié)點 * @param parent 節(jié)點的父節(jié)點 * @return 被刪除的最小的節(jié)點 */ private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) { //如果節(jié)點為null,返回 if (root == null) { return null; /*如果節(jié)點的左子節(jié)點為null,那么該節(jié)點就是最小的節(jié)點*/ /*1、該最小節(jié)點肯定沒有左子節(jié)點,因為左子節(jié)點比父節(jié)點小,但是可能有右子節(jié)點*/ /*2、此時該節(jié)點可能作為某個節(jié)點的左子節(jié)點,也可能作為原父節(jié)點的右子節(jié)點(即右子樹是一顆右斜樹),這里需要分開討論*/ } else if (root.left == null) { //如果該節(jié)點是父節(jié)點的右子節(jié)點,說明還沒進行遞歸或者第一次遞歸就找到了最小節(jié)點. //那么此時,應(yīng)該讓該節(jié)點的父節(jié)點的右子節(jié)點指向該節(jié)點的右子節(jié)點,并返回該節(jié)點的數(shù)據(jù),該節(jié)點由于沒有了強引用,會被GC刪除 if (root == parent.right) { parent.right = root.right; } else { //如果該節(jié)點不是父節(jié)點的右子節(jié)點,說明進行了多次遞歸。 //那么此時,應(yīng)該讓該節(jié)點的父節(jié)點的左子節(jié)點指向該節(jié)點的右子節(jié)點,并返回該節(jié)點的數(shù)據(jù),該節(jié)點由于沒有了強引用,會被GC刪除 parent.left = root.right; } //返回最小節(jié)點的數(shù)據(jù) return root.data; } //遞歸調(diào)用,注意此時是往左查找 return findAndDeleteMin(root.left, root); }
2.5.1 測試
public class BinarySearchTreeTest { BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>(); @Test public void test() { //首先要插入根節(jié)點47,然后是第二層的節(jié)點16,73,然后是第三層的節(jié)點1,24,59,88,然后是第四層的節(jié)點20,35,62,77。 // 每一層內(nèi)部節(jié)點的順序可以不一致,但是每一層之間的打順序一定要保持一致,否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結(jié)構(gòu)不能保證。 Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77}; binarySearchTree.insert(es); //中序遍歷輸出 System.out.println(binarySearchTree.toInorderTraversalString()); //查找是否存在 System.out.println(binarySearchTree.contains(1)); System.out.println(binarySearchTree.contains(2)); //移除 binarySearchTree.delete(73); //中序遍歷輸出 System.out.println(binarySearchTree.toInorderTraversalString()); } }
3 二叉排序樹的總結(jié)
總之,二叉排序樹是以鏈接的方式存儲,保持了鏈接存儲結(jié)構(gòu)在執(zhí)行插入或刪除操作時不用移動元素的優(yōu)點,只要找到合適的插入和刪除位置后,僅需修改鏈接指針即可。
插入刪除的時間性能比較好。而對于二叉排序樹的查找,走的就是從根節(jié)點到要查找的節(jié)點的路徑,其比較次數(shù)等于給定值的節(jié)點在二叉排序樹的層數(shù)。極端情況,最少為1次,即根節(jié)點就是要找的節(jié)點,最多也不會超過樹的深度。也就是說,二叉排序樹的查找性能取決于二叉排序樹的形狀??蓡栴}就在于,二叉排序樹的形狀是不確定的。
例如{47, 16, 73, 1, 24, 59, 88}這樣的數(shù)組,我們可以構(gòu)建下圖左的二叉排序樹。但如果數(shù)組元素的次序是從小到大有序,如{1, 16, 24, 47, 59, 73, 88},則二叉排序樹就成了極端的右斜樹,注意它依然是一棵二叉排序樹,如下圖右。此時,同樣是查找節(jié)點88,左圖只需要3次比較,而右圖就需要7次比較才可以得到結(jié)果,二者差異很大。
也就是說,我們希望二叉排序樹是比較平衡的,即其深度與完全二叉樹相同,均為|log2n+1|(|x|表示不大于x的最大整數(shù)),那么查找的時間復雜也就為O(logn),近似于折半查找,事實上,上圖的左圖也不夠平衡,明顯的左重右輕。而極端情況下的右圖,則完全退化成為鏈表,查找的時間復雜度為O(n),這等同于順序查找。
因此,如果我們希望對一個集合按二叉排序樹查找,最好是把它構(gòu)建成一棵平衡的二叉排序樹,防止極端情況的發(fā)生。這樣我們就引申出另一個問題,如何讓二叉排序樹平衡的問題。關(guān)于這個問題,在后續(xù)的平衡二叉樹(AVL樹)的部分將會詳細解釋!
以上就是Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實現(xiàn)的詳細內(nèi)容,更多關(guān)于Java二叉排序樹的資料請關(guān)注腳本之家其它相關(guān)文章!
- Java數(shù)據(jù)結(jié)構(gòu)常見幾大排序梳理
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之排序算法
- java 數(shù)據(jù)結(jié)構(gòu)與算法 (快速排序法)
- Java深入了解數(shù)據(jù)結(jié)構(gòu)中常見的排序算法
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之高級排序
- Java數(shù)據(jù)結(jié)構(gòu)和算法之冒泡,選擇和插入排序算法
- ?Java數(shù)據(jù)結(jié)構(gòu)的十大排序
- Java 數(shù)據(jù)結(jié)構(gòu)七大排序使用分析
相關(guān)文章
Netty分布式pipeline傳播inbound事件源碼分析
這篇文章主要為大家介紹了Netty分布式pipeline傳播inbound事件的源碼分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步2022-03-03如何使用IDEA2022.1?創(chuàng)建Spring?Boot項目
這篇文章主要介紹了如何使用IDEA2022.1?創(chuàng)建Spring?Boot項目,大家在使用idea開發(fā)工具時發(fā)現(xiàn)給以往的版本略微的不同,細心的小編在此記錄下,需要的朋友可以參考下2022-08-08Java?Http請求方式之RestTemplate常用方法詳解
這篇文章主要為大家介紹了Java?Http請求方式之RestTemplate常用方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-09-09Java開發(fā)編程到底是用idea好還是eclipse好
這篇文章主要介紹了Java開發(fā)編程到底是用idea好還是eclipse好,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-08-08