算法导论第十二章：二叉查找树
查找樹是一種數據結構,它支持多種動態集合操作,包括search, minimum, maximum, predecessor, successor, insert以及delete。他既可以用作字典，也可以用作優先隊列。
二叉查找樹上基本操作的執行時間和樹的高度成正比。對一棵n個結點的完全二叉樹來說，這些操作的最壞情況運行時間為Θ(lgn)。但是如果樹是含有那個結點的線性鏈，則這些操作的最壞運行時間是Θ(n)。本章可以看到一棵隨機構造的二叉查找樹的期望高度為O(lgn)。
實際中，并不能總是保證二叉查找樹是隨機構造的，但有些二叉查找樹的變形能保證各種基本操作的最壞情況性能。第十三章介紹的紅黑樹，其高度為O(lgn)。第十八章介紹B樹，這種結構對維護隨機訪問的二級存儲器上的數據庫特別有效。
?
二叉查找樹
? 二叉查找樹是按二叉樹結構來組織的，每個結點除了key域和衛星數據外，還包含left，right和p。結點的存儲方案滿足以下性質：如果結點y是結點x左子樹種的一個結點，則key[y]<=key[x]。如果y是x右子樹中的一個結點，則key[x]<=key[y]。
?
對二叉查找樹進行中序遍歷可以有序輸出所有的結點關鍵字。
?
練習：
12.1.3給出二叉樹的一個非遞歸的中序遍歷算法。
（1）可以用一個棧數據結構來模擬遞歸過程中的棧變化過程，從而完成非遞歸形式的遍歷算法；
（2）也可以不借助棧數據結構，中序遍歷的過程中是由從根到葉、從父到子的down過和從子到父的up過程組成的。在非遞歸的情況下，在處理某個節點x時，關鍵是要分清下一步是要down還是up。其實這可以由上一個結點位置來判斷，如果上一個結點是x的父節點且x是它的左兒子，則應該往左down，如果x是它的右兒子，則應該up。如果上一結點是x的左兒子，則應該往右down，如果是x的右兒子，則應該up。
OPTYPE {down, up}
INORDER_WITHOUTSTACK（T）
1???????? Node x = root[T]
2???????? Node last_node = nil
3???????? OPTYPE last_op = down
4???????? while (!over)
5???????? ??switch (last_op)
6???????? ????Case down:???????
7???????? ???????If (left[x]) last_node=x, last_op=down, x=left[x]
8???????? ???????Else output(x);
9???????? ???????????if (right[x]) last_node=x, last_op=down, x=right[x]
10???? ???????????Else if (x.p) last_node=x,last_op=up,x=x.p
11???? ???????????????Else over=true
12???? ????Case up:
13???? ???????If (last_node = left[x]) output(x)
14???? ??????????????????????????If (right[x]) last_node=x, last_op=down, x=right[x]
15???? ????????????????????????Else if (x.p) last_node=x,last_op=up,x=x.p
16???? ????????????????????????????Else over=true
17???? ?????Else if (x.p) last_node=x,last_op=up,x=x.p
18???? ????????????????????????????Else over=true?
?
查詢二叉查找樹
查找關鍵字k：
從樹根開始比較key[x]和k，如果key[x]=k停止，如果key[x]>k則往左子樹查找，否則往右子樹查找，如此循環。
?
最大關鍵字元素和最小關鍵字元素：
最大關鍵字就是樹的最右結點：沿樹根往右子節點移動，直到NIL。
最小關鍵字元素就是樹的最左結點：沿樹根往左子結點移動，直到NIL。
?
前驅和后繼：
某個節點x的前驅：如果x有左子，那么前驅是左子樹的最大關鍵字；否則從下往上查看x的祖先結點，直到某個節點y滿足性質：x出現在y的右子樹種。如果y存在，則y就是x的前驅，否則x沒有前驅。
某個節點x的后繼：如果x有右子，則x的后繼是右子樹的最小關鍵字；否則從下往上查看x的祖先結點，直到某個結點y滿足性質：x出現在y的左字數中，如果y存在，則y是x的后繼，否則x沒有后繼。
?
查找前驅和后繼的最壞運行時間為lgn。
但對x查找其后繼（前驅）的k個結點的運行時間為lgn+k，以前驅為例，證明如下：
假設x的左子樹有k1個結點，如果k<k1，則k1時間內就可以完成，假設k1<k，遍歷這k1個結點需要k1時間，找到下一個前驅需要往根方向移動，不妨設移動的距離為h1。如此往復。假設期間產生了 k1,k2,k3..，h1,h2…這些數據。可知 k1+k2+k3…<=k，h1+h2+…<=樹的高度。所以運行時間k1+k2+k3+…+h1+h2+…<=lgn+k。
實際上，如果對樹的最小結點調用n-1次后繼操作，等同于中序遍歷二叉查找樹。
?
插入刪除結點
插入一個結點與查找一個關鍵字的過程是基本一致的。當查找過程到達nil時，這個位置就是插入的位置。
刪除的過程要稍微復雜一點：
（1）?????? 如果結點沒有子節點，則直接刪除。
（2）?????? 如果結點只有左子樹或右子樹，則刪除該節點，然后用該子樹的根節點來取代該節點的位置。
（3）?????? 如果該節點有左右子樹，則將該節點的數據與其前驅或后繼結點的數據進行交換，再刪除該前驅或后繼結點
?
隨機構造的二叉查找樹
二叉查找樹的操作性能依賴于樹的高度，為了避免壞的關鍵字順序造成樹的高度過高，可以采用隨機化的手段來構造樹。可以證明，隨機構造的二叉查找樹的期望高度為O(lgn)。
先定義三個隨機變量：
Xn：n個結點的二叉查找樹的高度；
Yn：指數高度Yn=2Xn；Yn = 2*max(Yi-1,Yn-i)。
Rn：根節點的在關鍵字中的統計順序。
Zn,i：定義指示器隨機變量Zn,i=I{Rn=i}; E[Zn,i] = 1/n。
推理過程如下：
????????????????????????????????????????????????????????????????????
利用恒等式：,用數學歸納得出,再利用jensen不等式：，可得E[Xn] = O(lgn)。
?
?
?
?
隨機構造二叉查找樹與隨機化快速排序比較
在構造二叉樹的時候，當選定某個關鍵字稱為根節點之后，那么比這個關鍵字大的關鍵字都將出現在該節點的右字數，小的關鍵字都將出現在左子樹。這個過程與快速排序選定中軸節點的過程及其相似。進一步，所有的結點都將與根節點進行比較，但左子樹中的結點不會與右子樹的結點比較，反之亦然。可以看出構造二叉查找樹的過程與快速排序的過程驚人地相似，實際上如果將選定根節點和選定中軸結點相對應，那么兩者整個過程中所進行的元素比較是完全相同的，只是順序不一致而已。
?
可以分析二叉查找樹的平均結點深度。每個結點的深度等于其在插入樹的過程中的比較次數，所有的比較次數之和平均為nlgn，因此平均的結點深度為lgn。
?
思考題
基數樹：
基數樹數據結構，用來存儲0,1位串，位置串并沒有存儲在節點中，一個結點只要標明從根到該節點的路徑是否構成一個有效位串。當查找某關鍵字a=a0a1…ap，時，在深度為i的一個結點處，如果ai=0，則向左轉，如果ai=1則向右轉。下圖的基數樹存儲了位串0,001,10， 100，1011．白色結點為有效位串的終結結點。
設S為一組不同的二進制構成的集合，各串的長度之和為n。說明如何利用基數樹，在Θ(n)時間內將S按字典順序排序。
?
分析：構造基數樹的過程很顯然，假設一個位串的長度為k，則只需要時間k就可以將串插入基數樹中。然后進行中序遍歷就可以，按序輸出。
如果將基數樹擴展，是否可以用來存儲一般的字符串，并加快查找過程？
?
?
轉載于:https://www.cnblogs.com/longhuihu/archive/2011/02/26/10423370.html
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的算法导论第十二章：二叉查找树的全部內容，希望文章能夠幫你解決所遇到的問題。
