伸展樹(splay)

Preface

首先呢，這是一棵二叉排序樹。

然後呢，它還要是平衡的。

諸如RBT，SBT，Treap等等都可以的。

splay是了解和實作都比較簡單，平均效率也比較好的一種。

但是splay的複雜度比較的玄學（這個待會會講）

Text

一棵二叉排序樹，左子樹小于目前點，右子樹大于目前點。

在不斷删點加點的時候，我們需要用某些算法重構這棵樹，使其達到相對的“平衡”，即使最大深度盡量小，這樣每次複雜度就能達到O(logN)。

splay的核心思想就是旋轉。

旋轉即目前點移到它的父親的位置，然後相應的變換。圖中左到右的就是x旋轉到f,右圖相反。

核心操作splay即将某一個點旋轉到某一個點下面（轉到根就是0之類的）

但是有一種情況，就是三個點連在一起并且同一方向，旋最下面的，要先将中間的旋轉，再旋下面的。

單點操作splay到根直接做。

對于區間[x,y]，隻需要想辦法将這個區間提取出來。

隻需要将x-1轉到根，y+1轉到根下，那麼y+1的左子樹就是這個區間了。

修改就打上标記，在向下查找的時候順便下傳即可。

分析複雜度。

實際上通過它的原理可以發現，事實上一次操作最壞是O（N）的。

但是因為我們有旋轉操作，在不斷旋轉中整棵樹就漸漸平衡，具體嚴謹證明可以參考網上其他的資料，我這蒟蒻也不會。

總的來講，它的均攤複雜度是O（Nlog N）的