二叉搜索樹

二叉排序樹的查找過程和次優(yōu)二叉樹類似，通常采取二叉鏈表作為二叉排序樹的存儲結構。中序遍歷二叉排序樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動某個結點的指針，由空變?yōu)榉强占纯伞Ｋ阉?插入,刪除的復雜度等于樹高，O(log(n)).

AVL樹本質上還是一棵二叉搜索樹，它的特點是:

1.本身首先是一棵二叉搜索樹。

2.帶有平衡條件:每個結點的左右子樹的高度之差的絕對值(平衡因子)最多為1。

也就是說，AVL樹，本質上是帶了平衡功能的二叉查找樹(二叉排序樹，二叉搜索樹)。

我們知道，對于一般的二叉搜索樹(Binary Search Tree)，其期望高度(即為一棵平衡樹時)為log2n，其各操作的時間復雜度(O(log2n))同時也由此而決定。但是，在某些極端的情況下(如在插入的序列是有序的時)，二叉搜索樹將退化成近似鏈或鏈，此時，其操作的時間復雜度將退化成線性的，即O(n)。我們可以通過隨機化建立二叉搜索樹來盡量的避免這種情況，但是在進行了多次的操作之后，由于在刪除時，我們總是選擇將待刪除節(jié)點的后繼代替它本身，這樣就會造成總是右邊的節(jié)點數(shù)目減少，以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間復雜度。

平衡二叉搜索樹(Balanced Binary Tree)具有以下性質:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O(log(n))，大大降低了操作的時間復雜度。

Size Balanced Tree(SBT)是一種通過大小(Size)域來保持平衡的二叉搜索樹，它也因此得名。它總是滿足:

對于SBT的每一個結點 t:

性質(a) s[right[t] ]≥s[left[left[t]]], s[right[left[t]]]

性質(b) s[left[t] ]≥s[right[right[t]]], s[left[right[t]]]

即每棵子樹的大小不小于其兄弟的子樹大小。