Splay樹

Splay樹是一種BST樹，允許查找、插入、删除、分割、合并等操作。

Splay樹的原理:

為了使整個查找時間更少，被查頻率高的那些結點應當經常處于靠近樹根的位置。Splay樹可以通過旋轉的方式把被通路結點旋轉到樹根的位置以減少查找時間。

與Treap樹的不同:

• Splay樹允許把任意結點旋轉到樹根，Treap樹形态固定是以不能。
• Splay樹分裂、合并更簡便。

Splay樹的操作

提根(把結點x旋轉到根)

x的父結點是根，隻需旋轉一次。x是左兒子則右旋，反之左旋，且前後中序順序不變。

x的父結點不是根，但x、x的父結點、x的父結點的父結點三點共線，則先旋轉x的父結點，再旋轉x。

x、x的父結點、x的父結點的父結點三點不共線，把x按不同方向旋轉兩次。

插入:

同BST樹的插入

删除:

待删結點旋轉到根，删除，合并左右子樹。

合并:

隻有left樹的所有元素都小于right樹的所有元素從可以合并。先把left最大元素x旋轉到樹根，再把x的右子樹接到right上。

分裂:

把第k小的元素旋轉到樹根，然後把它與右子樹斷開即可。

查找x:

把x旋轉到根結點

查找最大、最小、第k大的數。用中序周遊查找，查找後把它旋轉到根。