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;
}

相关推荐阅读: