二叉樹在?這篇文章?中講到過了，其中講述了二叉樹的各種性質(zhì)，特點

二叉查找樹

今天我們就要學(xué)習(xí)一棵特別的二叉樹 —— 二叉查找樹 ( Binary Search Tree , 即 BST?)

怎么樣的一棵樹才能稱作二叉查找樹呢，當(dāng)然是要能夠查找，所以在這棵二叉樹上，每一個結(jié)點都儲存著一個能夠比較大小的值，讓我們可以按照順序排序以及查找它們，例如下面的兩個都是二叉查找樹 ( 順序為左子樹 < 根結(jié)點 < 右子樹?)

在二叉查找樹中，其任意一棵子樹都是二叉查找樹

所以，二叉查找樹的中序遍歷是一個有序的序列，例如上面兩棵二叉樹的中序遍歷為

當(dāng)我們要在二叉查找樹上查找一個數(shù)時，需要從根結(jié)點開始，一步一步向根深處走去，例如在二叉查找樹.1 中，我們要查找 12，根據(jù)這棵二叉樹的性質(zhì) ( 即左子樹的值 < 右子樹?)，我們知道在第一步中 ( 根結(jié)點中 )，因為 ，所以我們需要在右子樹中尋找 12，而不是去左子樹中尋找，因為左子樹上所有結(jié)點的值均小于根結(jié)點

于是我們尋找到了 19，雖然這次我們只能向左子樹走，但是當(dāng)存在右子樹時，我們也知道應(yīng)該向左子樹走，因為?，右子樹中的值絕對大于 12，所以 12 絕對在其左子樹

相比數(shù)組查詢某個特定的值的位置需要 次，二叉查找樹僅查找了?，要快上很多，原因是每次向下查找時，都排除了一半的結(jié)點，但是所有的二叉查找樹都會更快嗎

這不一定，如果二叉查找樹長成 二叉查找樹.2 的樣子，查找一個數(shù)的時間復(fù)雜度與使用數(shù)組就沒有區(qū)別了，因為在查找時，每次向下查找都只排除了 1 個結(jié)點，導(dǎo)致效率低下，這時我們稱這棵二叉查找樹退化成為了鏈，是退化的

而像 二叉查找樹.1 這樣，根結(jié)點到任意一個結(jié)點的距離小于等于??的二叉查找樹則稱為平衡的二叉查找樹

想都不用想，我們自然希望查找某個數(shù)時花費的時間最少，因此我們就希望一棵樹要在插入和刪除結(jié)點時要一直維持它的平衡狀態(tài)，讓查找效率保持一個較高的水平

為了維持二叉查找樹的平衡，我們就需要用到平衡樹

當(dāng)然這篇文章不講

好了那么關(guān)于二叉查找樹的內(nèi)容就講到這里了，如果你覺得本篇文章對你有所幫助的話，請不要忘記三連支持！