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 三個函數,當成黑箱就可以瞭。
void push_up(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x]; }
bool get(int x) { return x == ch[fa[x]][1]; }
void clear(int x) {
ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
}
void rotate(int x) {
int y = fa[x], z = fa[y], chk = get(x);
ch[y][chk] = ch[x][chk ^ 1];
if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
ch[x][chk ^ 1] = y;
fa[y] = x;
fa[x] = z;
if (z) ch[z][y == ch[z][1]] = x;
push_up(y);
}
void splay(int x, int goal) {
for (int f = fa[x]; (f = fa[x]) != goal; rotate(x))
if (fa[f] != goal) rotate(get(x) == get(f) ? f : x);
if (goal == 0)rt = x;
}