二叉搜索樹(shù)原理

二叉排序樹(shù)的查找過(guò)程和次優(yōu)二叉樹(shù)類似，通常采取二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)。中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字的有序序列，一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。每次插入的新的結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn)，在進(jìn)行插入操作時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，只需改動(dòng)某個(gè)結(jié)點(diǎn)的指針，由空變?yōu)榉强占纯?。搜?插入,刪除的復(fù)雜度等于樹(shù)高，O(log(n)).

AVL樹(shù)本質(zhì)上還是一棵二叉搜索樹(shù)，它的特點(diǎn)是:

1.本身首先是一棵二叉搜索樹(shù)。

2.帶有平衡條件:每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值(平衡因子)最多為1。

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

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

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

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

對(duì)于SBT的每一個(gè)結(jié)點(diǎn) t:

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

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

即每棵子樹(shù)的大小不小于其兄弟的子樹(shù)大小。