splay樹首先是個平衡樹，那麼什麼是平衡樹呢？

平衡樹都是可以保證高度的二叉搜索樹。

但是splay和avl樹/紅黑樹等不同的是，他是均攤復雜度的。類似於並查集。

在觀看本文章前請確保你瞭解過二叉搜索樹Pecco：算法學習筆記(45): 二叉搜索樹

當然如果splay隻是個平衡樹的話，就很沒意思瞭。

splay也可以進行類似於線段樹的操作，區間加區間查詢。而且還有一個操作是線段樹做不到的，那就是區間翻轉。

這裡推薦閱讀嚴格鴿：什麼是權值線段樹 —— 用線段樹來實現平衡樹

首先，splay是個“旋轉樹”，什麼是旋轉呢？

就是我們在插入二叉搜索樹的時候，可能會出現一條很長的鏈。

b8587c4f4b985191403c4e75bdc8ed4b

那麼我們就通過旋轉，使得他變得高度低一些。

d8f8c9a1502d308874e5d27c1cf9693c

值得註意的是

旋轉不會改變中序遍歷的結果

旋轉不會改變中序遍歷的結果

旋轉不會改變中序遍歷的結果

因為二叉搜索樹是有序的，中序遍歷就是排序後的結果，顯然中序遍歷不會發生改變。

那麼splay是怎麼旋轉的呢？

當插入一個節點後，我們就將這個節點變成根節點。

7d026a383346fc3c42c5a45235fd11c4這個就是瞎畫的，不是真的會旋轉成這個樣子

但是！一般的旋轉，我們稱其為“單旋”，一條鏈“單旋”後還是一條鏈。

所以splay使用的是“雙旋”。但是你可能會感覺，就算是這樣“雙旋”，為什麼可以保證復雜度呢？

這個就是個比較復雜度的證明瞭。

伸展樹（Splay）復雜度證明 - Mr_Spade - 博客園

所以這裡我們就把他當成黑盒來用就可以瞭（畢竟並查集的復雜度我們也不會證明

那麼我們這裡放上板子

這裡 rm ch[x][0/1] 表示 x 的左右兒子

rm rt 根節點是哪個

rm siz[x] 表示 x 的子樹大小

rm val[x] 表示 x 節點上的值

rm cnt[x] 表示 val[x] 在 x 上出現瞭多少次

rm fa[x] x 的父親節點

rm splay(x,y) 可以將節點 x 旋轉到 y 的子節點上

僅供理解，並不是真的旋轉成這個樣子

rm pushup(x) 更新點 x 的子樹大小

這裡不需要關心 rm rotate ,get ,splay 三個函數，當成黑箱就可以瞭。