樹看的越來越多，越來越神奇。

看伸展樹這種神級數(shù)據(jù)結(jié)構(gòu)之前，建議大家首先徹底明白二叉搜索樹，這是萬樹的基礎(chǔ)。

然后可以去看下treap,最好再去看下紅黑樹。如果有線段樹的基礎(chǔ)那更好了，我們會發(fā)現(xiàn)線段樹難以實(shí)現(xiàn)一些直接刪除，直接插入的數(shù)據(jù)。

這個(gè)時(shí)候就體現(xiàn)出神級數(shù)據(jù)解耦 伸展樹的魅力了，他的區(qū)間操作的非常優(yōu)雅的。

有了這些基礎(chǔ)之后，那就可以splay了。

zig,zag,zig和zag的組合。splay也就是通過一系列的左右旋轉(zhuǎn)達(dá)到了splay的目的，把當(dāng)前節(jié)點(diǎn)旋轉(zhuǎn)到指定節(jié)點(diǎn)的下面。

具體信息可以查看：http://blog.csdn.net/niuox/article/details/8018280

里面有介紹如何運(yùn)用伸展樹進(jìn)行區(qū)間操作，這是我們學(xué)伸展樹的一個(gè)關(guān)鍵所在，否則，一般的二叉搜索樹，我們用treap或者set完全可以搞定。

昨天睡不著我想，splay不過是一種平衡樹而已，我們是不是可以用紅黑樹來達(dá)到區(qū)間操作的呢，或者用treap。。。。不曉得。不過紅黑樹代碼太長。。。

void Rotate(node *x, int c) // 旋轉(zhuǎn)操作，c=0 表示左旋，c=1 表示右旋 {node *y = x->pre;y->ch[! c] = x->ch[c];if (x->ch[c] != Null) x->ch[c]->pre = y;x->pre = y->pre;if (y->pre != Null)if (y->pre->ch[0] == y) y->pre->ch[0] = x;else y->pre->ch[1] = x;x->ch[c] = y, y->pre = x;if (y == root) root = x; // root 表示整棵樹的根結(jié)點(diǎn) }
這么一段旋轉(zhuǎn)的代碼，寫的非常優(yōu)雅，把所選右旋都集合在一起了，無聊的人可以把他拆開2個(gè)。。

具體的題目：

hdu 1754 ?

我先閃人 ?有空再來繼續(xù)。。。。未完待續(xù)。。。。

總結(jié)

以上是生活随笔為你收集整理的伸展树(Splay tree)浅谈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。