什么是二叉排序樹

二叉排序樹（Binary Sort Tree），首先它是一棵樹，“二叉”這個描述已經(jīng)很明顯了，就是樹上的一根樹枝開兩個叉，于是遞歸下來就是二叉樹了（下圖所示），而這棵樹上的節(jié)點是已經(jīng)排好序的，具體的排序規(guī)則如下：

若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值

若右子樹不空，則右字?jǐn)?shù)上所有節(jié)點的值均大于它的根節(jié)點的值

它的左、右子樹也分別為二叉排序數(shù)（遞歸定義）

從圖中可以看出，二叉排序樹組織數(shù)據(jù)時，用于查找是比較方便的，因為每次經(jīng)過一次節(jié)點時，最多可以減少一半的可能，不過極端情況會出現(xiàn)所有節(jié)點都位于同一側(cè)，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進(jìn)行平衡化處理，于是就有了平衡二叉樹（Balenced Binary Tree）

所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小于1，這樣就不會出現(xiàn)一條支路特別長的情況。于是，在這樣的平衡樹中進(jìn)行查找時，總共比較節(jié)點的次數(shù)不超過樹的高度，這就確保了查詢的效率（時間復(fù)雜度為O(logn)）