概念
伸展樹是一種二叉查找樹住拭，它能在O(logn)內(nèi)完成插入偷线、查找和刪除操作。
伸展樹是一種自調(diào)整形式的二叉查找樹推掸，它會沿著從某個節(jié)點到樹根之間的路徑桶蝎，通過一系列的旋轉(zhuǎn)把這個節(jié)點搬移到樹根去驻仅。
它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息。
優(yōu)點
- 可靠的性能-它的平均效率不輸于其他平衡樹
- 存儲所需的內(nèi)存少-伸展樹無需記錄額外的什么值來維護樹的信息登渣，相對于其他平衡樹噪服，內(nèi)存占用要小
缺點
伸展樹最明顯的缺點是它有可能會變成一條鏈表。這種情況可能發(fā)生在以非降順序訪問n個元素之后胜茧。然而均攤的最壞情況是對數(shù)級的O(logn)
基本操作
伸展樹主要有三種旋轉(zhuǎn)操作粘优，分別為單旋轉(zhuǎn)，一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn)呻顽。為了便于解釋雹顺，我們假設當前被訪問節(jié)點為X，X的父親節(jié)點為Y（如果X的父親節(jié)點存在）廊遍，X的祖父節(jié)點為Z（如果X的祖父節(jié)點存在）嬉愧。
- 單旋轉(zhuǎn)
節(jié)點X的父節(jié)點Y是根節(jié)點。這時喉前，如果X是Y的左孩子没酣，我們進行一次右旋操作；如果X是Y的右孩子被饿，則我們進行一次左旋操作四康。經(jīng)過旋轉(zhuǎn)，X成為二叉查找樹T的根節(jié)點狭握，調(diào)整結(jié)束。
單旋轉(zhuǎn)
- 一字型旋轉(zhuǎn)
節(jié)點X的父節(jié)點Y不是根節(jié)點疯溺，Y的父節(jié)點為Z论颅，且X與Y同時是各自父節(jié)點的左孩子或者同時是各自父節(jié)點的右孩子。這時囱嫩，我們進行一次左左旋轉(zhuǎn)操作或者右右旋轉(zhuǎn)操作恃疯。
一字型旋轉(zhuǎn)
- 之字形旋轉(zhuǎn)
節(jié)點X的父節(jié)點Y不是根節(jié)點，Y的父節(jié)點為Z墨闲，X與Y中一個是其父節(jié)點的左孩子而另一個是其父節(jié)點的右孩子今妄。這時，我們進行一次左右旋轉(zhuǎn)操作或者右左旋轉(zhuǎn)操作鸳碧。
之字形旋轉(zhuǎn)
