什么是二叉排序樹

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

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

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

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

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

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