【0】README

0.1） 本文總結(jié)于 數(shù)據(jù)結(jié)構(gòu)與算法分析，核心剖析路線為原創(chuàng)， 旨在理清 自底向上伸展樹(shù)（之字形旋轉(zhuǎn)+一字形旋轉(zhuǎn)） 的基本思路；
0.2） 自底向上伸展樹(shù) 是基于 AVL樹(shù)，for detailed AVL, please visit http://blog.csdn.net/pacosonswjtu/article/details/50522677 ;
0.2） 對(duì)于伸展樹(shù)的實(shí)現(xiàn)而言， 自頂向下伸展樹(shù)只用到了O（1）的額外空間，且能夠保持O(logN)的攤還時(shí)間界，通常推薦自頂向下伸展樹(shù)的應(yīng)用；for detailed top-down splay tree, please visit http://blog.csdn.net/pacosonswjtu/article/details/50609414 （干貨——推薦自頂向下伸展樹(shù)的應(yīng)用）

---

【1】伸展樹(shù)（之字形旋轉(zhuǎn)+一字形旋轉(zhuǎn)）

1.1）定義：

• 伸展樹(shù)保證從空樹(shù)開(kāi)始任意連續(xù)M次對(duì)樹(shù)的操作最多花費(fèi) O（M logN）時(shí)間；

1.2）攤還運(yùn)行時(shí)間：

• 當(dāng) M 次操作的序列總的最壞情形運(yùn)行時(shí)間為 O（MF（N））時(shí)，我們就說(shuō)它的攤還運(yùn)行時(shí)間為 O（F（N））， 因此一顆伸展樹(shù) 每次操作的攤還代價(jià)是 O（log N）；（攤還 == 分期償還）

1.3）如果任意特定操作可以有最壞時(shí)間界O（N）， 而我們?nèi)匀灰笠粋€(gè) O（logN）的攤還時(shí)間界， 那么很清楚， 只要一個(gè)節(jié)點(diǎn)被訪問(wèn)， 它就必須被移動(dòng)。 否則，一旦我們發(fā)現(xiàn)一個(gè)深層節(jié)點(diǎn)，我們就有可能不斷對(duì)它進(jìn)行find 操作。 如果這個(gè)節(jié)點(diǎn)不改變位置， 而每次訪問(wèn)又花費(fèi) O（N）， 那么M次訪問(wèn)將花費(fèi) O（M * N）的時(shí)間；
1.4）引入伸展樹(shù)的原因：

• 如果任意特定操作可以有最壞時(shí)間界O（N）， 而我們?nèi)匀灰笠粋€(gè) O（logN）的時(shí)間復(fù)雜度， 顯然，為了達(dá)到這個(gè)目標(biāo)，只要一個(gè)節(jié)點(diǎn)被訪問(wèn)了，那么它必須被移動(dòng)。否則，一旦我們發(fā)現(xiàn)一個(gè)深層節(jié)點(diǎn)，我們就有可能不斷對(duì)它進(jìn)行find操作。 如果這個(gè)節(jié)點(diǎn)不改變位置， 而每次訪問(wèn)又花費(fèi)了 O（N）， 那么M次訪問(wèn)將花費(fèi)O（MN）的時(shí)間； （干貨——引入伸展樹(shù)的原因）

1.5）伸展樹(shù)的基本想法： （干貨——伸展樹(shù)的基本想法）

• 1.5.1）當(dāng)一個(gè)節(jié)點(diǎn)被訪問(wèn)后， 它就要經(jīng)過(guò)一系列AVL 樹(shù)的旋轉(zhuǎn)被放到根上。注意， 如果一個(gè)節(jié)點(diǎn)很深，那么在其路徑上就存在許多的節(jié)點(diǎn)也相對(duì)較深，通過(guò)重新構(gòu)造可以使對(duì)所有這些節(jié)點(diǎn)的進(jìn)一步訪問(wèn)所花費(fèi)的時(shí)間變少。
• 1.5.2）因此，如果節(jié)點(diǎn)過(guò)深，那么我們還要求重新構(gòu)造應(yīng)該具有平衡這棵樹(shù)（到某種程度）的作用；除了在理論上給出好的時(shí)間界外， 這種方法還可能有實(shí)際的效用（reasons）；
  
  • r1）因?yàn)樵谠S多應(yīng)用中當(dāng)一個(gè)節(jié)點(diǎn)被訪問(wèn)時(shí)， 它就很可能不久后再被訪問(wèn)到；
  • r2）另外， 伸展樹(shù)還不要求保留高度或平衡信息， 因此它在某種程度上節(jié)省空間并簡(jiǎn)化代碼；

---

【2】一個(gè)簡(jiǎn)單的想法（不過(guò)行不通）

2.1）執(zhí)行單旋轉(zhuǎn)：實(shí)施上面描述的重新構(gòu)造的一種方法是執(zhí)行單旋轉(zhuǎn)，從下到上進(jìn)行；
2.2）不過(guò)這種方法效率不是很高：因?yàn)檫@些旋轉(zhuǎn)的效果是將 k1 一直推向樹(shù)根，使得對(duì) k1 的進(jìn)一步訪問(wèn)很容易，不足的是它把另外一個(gè)節(jié)點(diǎn) k3 幾乎推向和k1以前同樣的深度；
2.3）結(jié)論（這個(gè)想法還不夠好）：雖然這個(gè)策略使得對(duì) k1 的訪問(wèn)花費(fèi)時(shí)間減少，但是它并沒(méi)有明顯的改變?cè)L問(wèn)路徑上其他節(jié)點(diǎn)的狀況；

【3】展開(kāi)（因?yàn)檎鹿?jié)2中的方法行不通，所以才有伸展樹(shù)的展開(kāi)）

我們?nèi)匀皇菑牡撞肯蛏涎刂L問(wèn) 路徑旋轉(zhuǎn)；
3.1）令X 是在訪問(wèn)路徑上的一個(gè)節(jié)點(diǎn)， 我們將在這個(gè)路徑上實(shí)施旋轉(zhuǎn)操作。

• 3.1.1）如果X 的父節(jié)點(diǎn)是樹(shù)根， 那么我們只要旋轉(zhuǎn)X 和樹(shù)根；（這是沿著路徑上的最后的旋轉(zhuǎn)）（干貨——單旋轉(zhuǎn)定義）

• 3.1.2）否則， X就有父親P 和 祖父G， 存在兩種情況需要考慮：

  • case1）第一種情況是 之字形：我們就執(zhí)行一次AVL 那樣的雙旋轉(zhuǎn)；（訪問(wèn)節(jié)點(diǎn)X是P的右兒子， 而父親P是G的左兒子的形式；或者訪問(wèn)節(jié)點(diǎn)X是P的左兒子， 而父親P是G的右兒子的形式）（干貨——之字形旋轉(zhuǎn)情形的定義，即訪問(wèn)節(jié)點(diǎn)X 介于父節(jié)點(diǎn)P 和 祖父節(jié)點(diǎn)G 之間，確切地說(shuō)是 P≤X≤G）
    

  • case2）第二種情況是 一字形：我們就把左邊的樹(shù)變成右邊的樹(shù)；（訪問(wèn)節(jié)點(diǎn)X 和 父親P 都分別是父親P和祖父G的左兒子，或者都是右兒子） （干貨——一字形旋轉(zhuǎn)情形的定義 ，即訪問(wèn)節(jié)點(diǎn)X 不介于父節(jié)點(diǎn)P 和 祖父節(jié)點(diǎn)G 之間，確切地說(shuō)是 X≤P≤G 或 G≤P≤X）
    

3.2）對(duì)展開(kāi)操作的分析（Analysis）

• A1）展開(kāi)操作不僅將訪問(wèn) 的節(jié)點(diǎn)移動(dòng)到根處，而且還有把訪問(wèn)路徑上的大部分節(jié)點(diǎn)的深度大致減少一半的效果（某些淺的節(jié)點(diǎn)最多向下推后兩個(gè)層次）
• A2）下圖中指出 關(guān)鍵字為1的節(jié)點(diǎn)展開(kāi)的結(jié)果 。區(qū)別在于：在對(duì)關(guān)鍵字1的節(jié)點(diǎn)訪問(wèn)（花費(fèi)N-1個(gè)單元的時(shí)間）之后，對(duì)關(guān)鍵字為2的節(jié)點(diǎn)的訪問(wèn)只花費(fèi) N/2 個(gè)時(shí)間單元而不是 N - 2個(gè)時(shí)間單元；
  

總結(jié)

以上是生活随笔為你收集整理的自底向上伸展树（之字形旋转+一字形旋转）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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