二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。本文詳細(xì)介紹了二叉排序樹的原理，并且提供了Java代碼的完全實(shí)現(xiàn)。

1 二叉排序樹的概述

本文沒有介紹一些基礎(chǔ)知識(shí)。對(duì)于常見查找算法，比如順序查找、二分查找、插入查找、斐波那契查找還不清楚的，可以看這篇文章：常見查找算法詳解以及Java代碼的實(shí)現(xiàn)。對(duì)于樹和二叉樹的概念還不清楚的，建議看這個(gè)專欄：樹。

假設(shè)查找的數(shù)據(jù)集是普通的順序存儲(chǔ)，那么插入操作就是將記錄放在表的末端，給表記錄數(shù)加一即可，刪除操作可以是刪除后，后面的記錄向前移，也可以是要?jiǎng)h除的元素與最后一個(gè)元素互換，表記錄數(shù)減一，反正整個(gè)數(shù)據(jù)集也沒有什么順序，這樣的效率也不錯(cuò)。應(yīng)該說，插入和刪除對(duì)于順序存儲(chǔ)結(jié)構(gòu)來說，效率是可以接受的，但這樣的表由于無序造成查找的效率很低。

如果查找的數(shù)據(jù)集是有序線性表，并且是順序存儲(chǔ)的，查找可以用折半、插值、斐波那契等查找算法來實(shí)現(xiàn)，可惜，因?yàn)橛行?#xff0c;在插入和刪除操作上，為了維持順序，需要移動(dòng)大量元素，就需要耗費(fèi)大量的時(shí)間。

有沒有一種即可以使得插入和刪除效率不錯(cuò)，又可以比較高效率地實(shí)現(xiàn)查找的算法呢？這就是二叉排序樹。

二叉排序樹（Binary Sort Tree），又稱為二叉查找樹/二叉搜索樹（binary search tree）。它是具有下列性質(zhì)的二叉樹：

1. 若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；
2. 若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3. 它的左、右子樹也分別為二叉排序樹；
4. 二叉排序樹也可以是一個(gè)空樹。

構(gòu)造一棵二叉排序樹的目的，其主要目的并不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度，用以提升數(shù)據(jù)結(jié)構(gòu)的綜合能力。不管怎么說，在一個(gè)有序數(shù)據(jù)集上的查找，速度總是要快于無序的數(shù)據(jù)集的，而二叉排序樹這種非線性的結(jié)構(gòu)，也有利于插入和刪除的實(shí)現(xiàn)。

2 二叉排序樹的構(gòu)建

2.1 類架構(gòu)

首先，最簡(jiǎn)單的節(jié)點(diǎn)對(duì)象還是需要一個(gè)數(shù)據(jù)域和兩個(gè)引用域。

另外還需要一個(gè)比較器的引用，因?yàn)樾枰獙?duì)元素進(jìn)行排序，自然需要比較元素的大小，如果外部傳遞了比較器，那么就使用用戶指定的比較器進(jìn)行比較，否則，數(shù)據(jù)類型E必須是Comparable接口的子類，否則因?yàn)椴荒鼙容^而報(bào)錯(cuò)。

另外，還需要提供中序遍歷的方法，該遍歷方法對(duì)于二叉排序樹的結(jié)果將會(huì)順序展示。

public class BinarySearchTree<E> {/*** 外部保存根節(jié)點(diǎn)的引用*/private BinaryTreeNode<E> root;/*** 自定義比較器*/private Comparator<? super E> cmp;/*** 樹節(jié)點(diǎn)的數(shù)量*/private int size;/*** 內(nèi)部節(jié)點(diǎn)對(duì)象** @param <E> 數(shù)據(jù)類型*/public static class BinaryTreeNode<E> {//數(shù)據(jù)域E data;//左子節(jié)點(diǎn)BinaryTreeNode<E> left;//右子節(jié)點(diǎn)BinaryTreeNode<E> right;public BinaryTreeNode(E data) {this.data = data;}@Overridepublic 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é)點(diǎn)數(shù)** @return 節(jié)點(diǎn)數(shù)*/public int size() {return size;}/*** 對(duì)元素進(jìn)行比較大小的方法,如果傳遞了自定義比較器,則使用自定義比較器,否則則需要數(shù)據(jù)類型實(shí)現(xiàn)Comparable接口** @param e1 被比較的第一個(gè)對(duì)象* @param e2 被比較的第二個(gè)對(duì)象* @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é)點(diǎn)數(shù)據(jù)*/List<BinaryTreeNode<E>> str = new ArrayList<>();/*** 中序遍歷,提供給外部使用的api** @return 遍歷的數(shù)據(jù)*/public String toInorderTraversalString() {//如果是空樹,直接返回空if (isEmpty()) {return null;}//從根節(jié)點(diǎn)開始遞歸inorderTraversal(root);//獲取遍歷結(jié)果String s = str.toString();str.clear();return s;}/*** 中序遍歷 內(nèi)部使用的遞歸遍歷方法,借用了棧的結(jié)構(gòu)** @param root 節(jié)點(diǎn),從根節(jié)點(diǎn)開始*/private void inorderTraversal(BinaryTreeNode<E> root) {BinaryTreeNode<E> left = getLeft(root);if (left != null) {//如果左子節(jié)點(diǎn)不為null,則繼續(xù)遞歸遍歷該左子節(jié)點(diǎn)inorderTraversal(left);}//添加數(shù)據(jù)節(jié)點(diǎn)str.add(root);//獲取節(jié)點(diǎn)的右子節(jié)點(diǎn)BinaryTreeNode<E> right = getRight(root);if (right != null) {//如果右子節(jié)點(diǎn)不為null,則繼續(xù)遞歸遍歷該右子節(jié)點(diǎn)inorderTraversal(right);}}/*** 獲取左子節(jié)點(diǎn)** @param parent 父節(jié)點(diǎn)引用* @return 左子節(jié)點(diǎn)或者null--表示沒有左子節(jié)點(diǎn)*/public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {return parent == null ? null : parent.left;}/*** 獲取右子節(jié)點(diǎn)** @param parent 父節(jié)點(diǎn)引用* @return 右子節(jié)點(diǎn)或者null--表示沒有右子節(jié)點(diǎn)*/public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {return parent == null ? null : parent.right;}/*** 獲取根節(jié)點(diǎn)** @return 根節(jié)點(diǎn) ;或者null--表示空樹*/public BinaryTreeNode<E> getRoot() {return root;}}

2.2 查找的方法

查找的方法很簡(jiǎn)單：

1. 若根節(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功，返回true；
2. 否則，若小于根節(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹；
3. 若大于根節(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹；
4. 最終查找到葉子節(jié)點(diǎn)還是沒有數(shù)據(jù)，那么查找失敗，則返回false。

/*** 查找,開放給外部使用的api*/
public boolean contains(E e) {return contains(e, root);
}/*** 查找,內(nèi)部調(diào)用的方法,從根節(jié)點(diǎn)開始查找** @param e    要查找的元素* @param root 節(jié)點(diǎn)* @return false 不存在 true 存在*/
private boolean contains(E e, BinaryTreeNode<E> root) {/*null校驗(yàn)*/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ù)，那么所謂的二叉排序樹的插入，其實(shí)也就是將關(guān)鍵字放到樹中的合適位置而已，插入操作就好像在調(diào)用查找的操作，如果找到了那么什么都不做，返回false，如果沒找到，則將要插入的元素插入到遍歷的路徑的最后一點(diǎn)上：

1. 若二叉樹為空。則單獨(dú)生成根節(jié)點(diǎn)，返回true。
2. 執(zhí)行查找算法，找出被插節(jié)點(diǎn)的父親節(jié)點(diǎn)。
3. 判斷被插節(jié)點(diǎn)是其父親節(jié)點(diǎn)的左、右兒子。將被插節(jié)點(diǎn)作為葉子節(jié)點(diǎn)插入，返回true。如果原節(jié)點(diǎn)存在那么什么都不做，返回false。注意：新插入的節(jié)點(diǎn)總是葉子節(jié)點(diǎn)。

/*** 插入,開放給外部使用的api** @param e 要插入的元素*/
public void insert(E e) {//返回root,但此時(shí)新的節(jié)點(diǎn)可能已經(jīng)被插入進(jìn)去了root = insert(e, root);
}/*** 插入,開放給外部使用的api** @param es 要插入的元素的數(shù)組,注意,數(shù)組元素的順序存儲(chǔ)的位置將會(huì)影響二叉排序樹的生成*/
public void insert(E[] es) {//返回root,但此時(shí)新的節(jié)點(diǎn)可能已經(jīng)被插入進(jìn)去了for (E e : es) {root = insert(e, root);}}/*** 插入,內(nèi)部調(diào)用的方法,先從根節(jié)點(diǎn)開始遞歸查找要插入的位置,然后插入** @param e    要插入的數(shù)據(jù)* @param root 節(jié)點(diǎn)* @return 原節(jié)點(diǎn)或者新插入的節(jié)點(diǎn)*/
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {/*沒有查找到,那么直接構(gòu)建新的節(jié)點(diǎn)返回,將會(huì)在上一層方法中被賦值給其父節(jié)點(diǎn)的某個(gè)引用,這個(gè)插入的位置肯定是該遍歷路徑上的最后一點(diǎn)* 即插入的元素節(jié)點(diǎn)肯定是屬于葉子節(jié)點(diǎn)*/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é)點(diǎn) 什么都不做*/}//沒查詢到最底層,則返回該節(jié)點(diǎn)return root;
}

2.3.1 測(cè)試

現(xiàn)在我們想要構(gòu)建如下一顆排序二叉樹：

首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16、73，然后是第三層的節(jié)點(diǎn)1、24、59、88，然后是第四層的節(jié)點(diǎn)20、35、62、77。每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的大順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出，但是樹的結(jié)構(gòu)不能保證。

public class BinarySearchTreeTest {BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();@Testpublic void insert() {//首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16,73，然后是第三層的節(jié)點(diǎn)1,24,59,88，然后是第四層的節(jié)點(diǎn)20,35,62,77。// 每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出,但是樹的結(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());//查找某個(gè)數(shù)據(jù)是否存在System.out.println(binarySearchTree.contains(1));System.out.println(binarySearchTree.contains(2));}
}

在System.out處打上斷點(diǎn)，Debug，可以看到樹結(jié)構(gòu)和我們預(yù)想的一致，如果改變層間的大順序，那么使用Debug會(huì)發(fā)現(xiàn)樹結(jié)構(gòu)不如預(yù)期。

2.4 查找最大值和最小值

很簡(jiǎn)單，最左邊的節(jié)點(diǎn)一定是最小的，最右邊的節(jié)點(diǎn)一定是最大的。因此查找最小的節(jié)點(diǎn)只需要向左遞歸查找，查找最大的節(jié)點(diǎn)只需要向右遞歸查找。

/*** 查找最小的節(jié)點(diǎn)** @param root 根節(jié)點(diǎn)* @return 最小的節(jié)點(diǎn)*/
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {if (root == null) {return null;/*如果該節(jié)點(diǎn)沒有左右子節(jié)點(diǎn)，那么該節(jié)點(diǎn)就是最小的節(jié)點(diǎn)，返回*/} else if (root.left == null) {return root;}/*如果該節(jié)點(diǎn)存在左子節(jié)點(diǎn)，那么繼續(xù)向左遞歸查找*/return findMin(root.left);
}/*** 查找最大的節(jié)點(diǎn)** @param root 根節(jié)點(diǎn)* @return 最大的節(jié)點(diǎn)*/
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {if (root == null) {return null;/*如果該節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，那么該節(jié)點(diǎn)就是最大的節(jié)點(diǎn)，返回*/} else if (root.right == null) {return root;}/*如果該節(jié)點(diǎn)存在右子節(jié)點(diǎn)，那么繼續(xù)向右遞歸查找*/return findMax(root.right);
}

2.5 刪除的方法

對(duì)于二叉排序樹的刪除，就不是那么容易，我們不能因?yàn)閯h除了節(jié)點(diǎn)，而讓這棵樹變得不滿足二叉排序樹的特性，所以刪除需要考慮多種情況。一共有三種情況需要考慮：

如果查找到的將要被刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，那么很簡(jiǎn)單，直接刪除父節(jié)點(diǎn)對(duì)于該節(jié)點(diǎn)的引用即可，如下圖的紅色節(jié)點(diǎn)：

例如，刪除20之后：

如果查找到的將要被刪除的節(jié)點(diǎn)具有一個(gè)子節(jié)點(diǎn)，那么也很簡(jiǎn)單，直接繞過該節(jié)點(diǎn)將原本父節(jié)點(diǎn)對(duì)于該節(jié)點(diǎn)的引用指向該節(jié)點(diǎn)的子節(jié)點(diǎn)即可，如下圖的紅色節(jié)點(diǎn)：

例如，刪除59之后：

如果查找到的將要被刪除的節(jié)點(diǎn)具有兩個(gè)子節(jié)點(diǎn)，那么就比較麻煩了，如下圖的紅色節(jié)點(diǎn)：

比如我們需要?jiǎng)h除73，那么我們就必須要找出一個(gè)已存在的能夠替代73的節(jié)點(diǎn)，然后刪除該節(jié)點(diǎn)。實(shí)際上該73節(jié)點(diǎn)的左子樹的最大節(jié)點(diǎn)62和右子樹的最小節(jié)點(diǎn)77都能夠替代73節(jié)點(diǎn)，即它們正好是二叉排序樹中比它小或比它大的最接近73的兩個(gè)數(shù)。

一般我們選擇一種方式即可，我們這次使用右子樹的最小節(jié)點(diǎn)替代要?jiǎng)h除的節(jié)點(diǎn)，使用77替代73之后的結(jié)構(gòu)如下：

完整的代碼如下：

    /*** 刪除,開放給外部使用的api** @param e 要?jiǎng)h除的元素*/public void delete(E e) {//返回root,但此時(shí)可能有一個(gè)節(jié)點(diǎn)已經(jīng)被刪除了root = delete(e, root);}/*** 刪除,內(nèi)部調(diào)用的方法,刪除分為三種情況: 1、該節(jié)點(diǎn)沒有子節(jié)點(diǎn) 2、該字節(jié)僅有一個(gè)子節(jié)點(diǎn) 3、該節(jié)點(diǎn)具有兩個(gè)子節(jié)點(diǎn)** @param e    要?jiǎng)h除的數(shù)據(jù)* @param root 根節(jié)點(diǎn)* @return 該節(jié)點(diǎn)*/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í)行刪除*//*如果兩個(gè)子節(jié)點(diǎn)都不為null*/if (root.left != null && root.right != null) {/*方法1、遞歸查找最小的節(jié)點(diǎn)，然后遞歸刪除  該方法不推薦使用*///root.data = findMin(root.right).data;//root.right = delete(root.data, root.right);/*方法2、遞歸查找并刪除最小的節(jié)點(diǎn) 推薦*/root.data = findAndDeleteMin(root.right, root);size--;} else {/*如果一個(gè)子節(jié)點(diǎn)不為null，則返回該子節(jié)點(diǎn)；或者兩個(gè)子節(jié)點(diǎn)都為null，則返回null* 此時(shí)該root節(jié)點(diǎn)已經(jīng)被"繞過了"*/root = (root.left != null) ? root.left : root.right;size--;}}//沒查詢到最底層,則返回該節(jié)點(diǎn)return root;}/*** 查找最小的節(jié)點(diǎn)并刪除* 最小的節(jié)點(diǎn)肯定不存在兩個(gè)子節(jié)點(diǎn),有可能沒有子節(jié)點(diǎn),有可能存在右子節(jié)點(diǎn)** @param root   節(jié)點(diǎn)* @param parent 節(jié)點(diǎn)的父節(jié)點(diǎn)* @return 被刪除的最小的節(jié)點(diǎn)*/private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {//如果節(jié)點(diǎn)為null，返回if (root == null) {return null;/*如果節(jié)點(diǎn)的左子節(jié)點(diǎn)為null,那么該節(jié)點(diǎn)就是最小的節(jié)點(diǎn)*//*1、該最小節(jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)，因?yàn)樽笞庸?jié)點(diǎn)比父節(jié)點(diǎn)小，但是可能有右子節(jié)點(diǎn)*//*2、此時(shí)該節(jié)點(diǎn)可能作為某個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)，也可能作為原父節(jié)點(diǎn)的右子節(jié)點(diǎn)（即右子樹是一顆右斜樹），這里需要分開討論*/} else if (root.left == null) {//如果該節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn),說明還沒進(jìn)行遞歸或者第一次遞歸就找到了最小節(jié)點(diǎn).//那么此時(shí),應(yīng)該讓該節(jié)點(diǎn)的父節(jié)點(diǎn)的右子節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn),并返回該節(jié)點(diǎn)的數(shù)據(jù)，該節(jié)點(diǎn)由于沒有了強(qiáng)引用，會(huì)被GC刪除if (root == parent.right) {parent.right = root.right;} else {//如果該節(jié)點(diǎn)不是父節(jié)點(diǎn)的右子節(jié)點(diǎn)，說明進(jìn)行了多次遞歸。//那么此時(shí),應(yīng)該讓該節(jié)點(diǎn)的父節(jié)點(diǎn)的左子節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn),并返回該節(jié)點(diǎn)的數(shù)據(jù)，該節(jié)點(diǎn)由于沒有了強(qiáng)引用，會(huì)被GC刪除parent.left = root.right;}//返回最小節(jié)點(diǎn)的數(shù)據(jù)return root.data;}//遞歸調(diào)用,注意此時(shí)是往左查找return findAndDeleteMin(root.left, root);}

2.5.1 測(cè)試

public class BinarySearchTreeTest {BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();@Testpublic void test() {//首先要插入根節(jié)點(diǎn)47，然后是第二層的節(jié)點(diǎn)16,73，然后是第三層的節(jié)點(diǎn)1,24,59,88，然后是第四層的節(jié)點(diǎn)20,35,62,77。// 每一層內(nèi)部節(jié)點(diǎn)的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時(shí)候能夠正常輸出,但是樹的結(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é)

總之，二叉排序樹是以鏈接的方式存儲(chǔ)，保持了鏈接存儲(chǔ)結(jié)構(gòu)在執(zhí)行插入或刪除操作時(shí)不用移動(dòng)元素的優(yōu)點(diǎn)，只要找到合適的插入和刪除位置后，僅需修改鏈接指針即可。

插入刪除的時(shí)間性能比較好。而對(duì)于二叉排序樹的查找，走的就是從根節(jié)點(diǎn)到要查找的節(jié)點(diǎn)的路徑，其比較次數(shù)等于給定值的節(jié)點(diǎn)在二叉排序樹的層數(shù)。極端情況，最少為1次，即根節(jié)點(diǎn)就是要找的節(jié)點(diǎn)，最多也不會(huì)超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀?？蓡栴}就在于，二叉排序樹的形狀是不確定的。

例如{47, 16, 73, 1, 24, 59, 88}這樣的數(shù)組，我們可以構(gòu)建下圖左的二叉排序樹。但如果數(shù)組元素的次序是從小到大有序，如{1, 16, 24, 47, 59, 73, 88}，則二叉排序樹就成了極端的右斜樹，注意它依然是一棵二叉排序樹，如下圖右。此時(shí)，同樣是查找節(jié)點(diǎn)88，左圖只需要3次比較，而右圖就需要7次比較才可以得到結(jié)果，二者差異很大。

也就是說，我們希望二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，均為|log2n+1|(|x|表示不大于x的最大整數(shù))，那么查找的時(shí)間復(fù)雜也就為O(logn)，近似于折半查找，事實(shí)上，上圖的左圖也不夠平衡，明顯的左重右輕。而極端情況下的右圖,則完全退化成為鏈表，查找的時(shí)間復(fù)雜度為O(n)，這等同于順序查找。

因此，如果我們希望對(duì)一個(gè)集合按二叉排序樹查找，最好是把它構(gòu)建成一棵平衡的二叉排序樹，防止極端情況的發(fā)生。這樣我們就引申出另一個(gè)問題，如何讓二叉排序樹平衡的問題。關(guān)于這個(gè)問題，在后續(xù)的平衡二叉樹（AVL樹)的部分將會(huì)詳細(xì)解釋！

相關(guān)參考：

1. 《算法》
2. 《算法圖解》
3. 《大話數(shù)據(jù)結(jié)構(gòu)》

如果有什么不懂或者需要交流，可以留言。另外希望點(diǎn)贊、收藏、關(guān)注，我將不間斷更新各種Java學(xué)習(xí)博客！