“伸展樹—一種高效的索引樹”教學(xué)設(shè)計(jì)

摘要：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的重要目標(biāo)之一是提高操作速度，特別是檢索速度。局部平衡的紅黑樹、平衡的AVL樹等二叉搜索樹具有良好的檢索性能，非常適合于基于內(nèi)存的索引，但為防止樹形結(jié)構(gòu)退化為線性結(jié)構(gòu)，在插入和刪除結(jié)點(diǎn)時(shí)經(jīng)常需要旋轉(zhuǎn)，維護(hù)數(shù)據(jù)結(jié)構(gòu)的操作比較復(fù)雜。文章闡述伸展樹在檢索過程中通過自動(dòng)調(diào)整結(jié)構(gòu)，使訪問最頻繁的結(jié)點(diǎn)靠近樹結(jié)構(gòu)的根，從而減少訪問代價(jià)，指出伸展樹可以作為各種線性序列的索引組織方法，能在一些需要高效索引的大工程中加以運(yùn)用。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；索引；二叉搜索樹；伸展樹

1.在數(shù)據(jù)結(jié)構(gòu)與算法課程中的定位和前測(cè)知識(shí)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)涉及邏輯、存儲(chǔ)和運(yùn)算3個(gè)維度。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有順序、鏈接、索引和散列4種方法。數(shù)據(jù)的運(yùn)算主要是對(duì)單個(gè)數(shù)據(jù)的增、刪、查、改，或?qū)φw數(shù)據(jù)的排序、索引和檢索。有效的索引可以加快運(yùn)算速度，可以說索引是數(shù)據(jù)結(jié)構(gòu)與算法的重要內(nèi)容Ⅲ。

二叉搜索樹是一種非常有效的內(nèi)存索引，但可能面臨退化為線性結(jié)構(gòu)的情況。改進(jìn)二叉搜索樹比普通二叉樹更能提高檢索效率，在現(xiàn)實(shí)中有廣泛的應(yīng)用。以往的數(shù)據(jù)結(jié)構(gòu)教材更多地介紹AVL平衡二叉樹，目前有不少教材開始介紹更易于實(shí)現(xiàn)應(yīng)用的、更廣泛的紅黑樹。

圖靈獎(jiǎng)獲得者Tarjan和他的學(xué)生在1985年發(fā)明的伸展樹（Splay Tree），作為一種自組織的數(shù)據(jù)結(jié)構(gòu)，其操作簡(jiǎn)便，易于編寫，統(tǒng)計(jì)性能高效，有良好的運(yùn)用前景。

伸展樹是用于索引的一種特殊二叉搜索樹，只是改進(jìn)BST性能的一組規(guī)則，而不是一種全新的數(shù)據(jù)結(jié)構(gòu)。在伸展樹中，數(shù)據(jù)隨檢索而采用這些操作規(guī)則來調(diào)整位置，目標(biāo)是把剛檢索的結(jié)點(diǎn)調(diào)整到根。

伸展樹是一種自組織的數(shù)據(jù)結(jié)構(gòu)，即它能隨著檢索等操作而發(fā)生結(jié)構(gòu)的變化。伸展樹中基本操作的均攤代價(jià)是O（logn）。

前測(cè)知識(shí)點(diǎn)要求如下，可以根據(jù)需要給學(xué)生補(bǔ)充：

（1）二叉搜索樹BST的性質(zhì)：中序遍歷下結(jié)點(diǎn)關(guān)鍵碼有序，左旋、右旋基本操作；

（2）二叉搜索樹BST的插入、刪除、查找算法；

（3）AVL樹、紅黑樹的簡(jiǎn)單定義。

2.學(xué)習(xí)目標(biāo)

（1）掌握伸展樹的概念；

（2）伸展樹的索引作用；

（3）伸展樹的實(shí)現(xiàn)和簡(jiǎn)單應(yīng)用；

（4）伸展樹的均攤時(shí)間效率。

3.知識(shí)點(diǎn)和學(xué)時(shí)分配

理論授課0.5學(xué)時(shí)。

主講教師可以根據(jù)學(xué)生的狀況、教師的科研背景等對(duì)某些方面進(jìn)行擴(kuò)展并引導(dǎo)學(xué)生，以適當(dāng)擴(kuò)大學(xué)生的涉獵面。

4.重點(diǎn)和難點(diǎn)

（1）伸展樹的旋轉(zhuǎn)。伸展樹旋轉(zhuǎn)分為單旋轉(zhuǎn)（zig右旋、zag左旋）、一字形雙旋（zig-zig、zag-zag）和之字形雙旋轉(zhuǎn)（zig-zag、zag-zig）。

（2）伸展樹的實(shí)現(xiàn)。伸展樹的實(shí)現(xiàn)很簡(jiǎn)單，最基礎(chǔ)的是Splay（x，f）函數(shù)，即將一個(gè)結(jié)點(diǎn)x旋轉(zhuǎn)到其某個(gè)祖先f的下面。就是從x結(jié)點(diǎn)向上看兩個(gè)結(jié)點(diǎn)（父親、祖父），如果沒有祖父則單旋轉(zhuǎn)，如果有祖父則根據(jù)x與父親、祖父的方向，來判斷是一字形還是之字形雙旋轉(zhuǎn)。

（3）伸展樹的應(yīng)用。一個(gè)簡(jiǎn)單的應(yīng)用是求x的前驅(qū)y，可以先把x旋轉(zhuǎn)到根，然后順著根的左子孩子的右鏈，一直向右走到頭，最后那個(gè)結(jié)點(diǎn)就是所求的y。伸展樹可以作為各種線性序列的索引組織方法。

5.授課提示

開展研究型教學(xué)，挖掘知識(shí)背后的內(nèi)容，通過提出問題、探討方法、研究思想和比較性能，培養(yǎng)學(xué)生的創(chuàng)新意識(shí)和創(chuàng)新能力。

伸展樹在搜索過程中自動(dòng)調(diào)整結(jié)構(gòu)，但是不能保證樹的高度。伸展樹旋轉(zhuǎn)的目的是使訪問最頻繁的結(jié)點(diǎn)靠近樹結(jié)構(gòu)的根，從而減少訪問代價(jià)。教師可結(jié)合動(dòng)畫進(jìn)行講解，并介紹一些實(shí)例體現(xiàn)伸展樹的特點(diǎn)和用途。

6.練習(xí)與擴(kuò)展

融合經(jīng)典的理論教學(xué)內(nèi)容與學(xué)科的前沿新技術(shù)和發(fā)展方向，設(shè)計(jì)驗(yàn)證型、探索型、綜合應(yīng)用型的習(xí)題和上機(jī)題，幫助學(xué)生更好地掌握排序算法的基本原理，訓(xùn)練學(xué)生的創(chuàng)新思維能力訓(xùn)練、工程實(shí)踐能力。

本講可以安排2道算法類作業(yè)題和1道小型綜合設(shè)計(jì)型實(shí)習(xí)題。

算法類作業(yè)有：

（1）通過二叉搜索樹的找最大最小操作實(shí)現(xiàn)雙端隊(duì)列（http：//poj.org/problem？id=3481）；

（2）用伸展樹實(shí)現(xiàn)add，insert，delete，min等操作（http：//poj.org/problem？id=3580）。

利用伸展樹存儲(chǔ)文件中單詞詞頻可以作為一個(gè)小型綜合設(shè)計(jì)題布置給學(xué)生。

圖1顯示了一個(gè)短文件的結(jié)點(diǎn)樹。掃描一個(gè)文本文件，并計(jì)算出這一文件中每個(gè)詞的詞頻。為簡(jiǎn)化起見，略去標(biāo)點(diǎn)符號(hào)，按照字典排列的順序?qū)卧~排序，并忽略大小寫，如man’s將被當(dāng)成man和s。類似地，分隔符也被忽略，如pre-existence被當(dāng)做pre和existence。用一棵BST作為一個(gè)文件中單詞的存儲(chǔ)結(jié)構(gòu)，并用伸展技術(shù)對(duì)這棵樹進(jìn)行輔助維護(hù)，以使輸入流中的下一個(gè)單詞出現(xiàn)在樹中接近于根的位置的幾率較大。

對(duì)于半伸展樹、動(dòng)態(tài)伸展樹等變種，我們給出如下擴(kuò)展閱讀建議：

（1）Daniel Sleator和Robert Tarian的文章《Self-Adjusting Binary Search Trees》，ACM，1985，32（3）：652-686。

（2）Daniel Sleator和Robe～Tarjan的文章《A Data Structure for Dynamic Trees》，Computre and System Science，1983，26（3）：362-391。

（3）Wiki的伸展樹詞條（http：//en，wikipedia，org/wiki/Splay tree）。

7.結(jié)語

數(shù)據(jù)結(jié)構(gòu)與算法課程的主要目標(biāo)是訓(xùn)練學(xué)生數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法思想、創(chuàng)新思維能力和工程實(shí)踐能力，而伸展樹在保持?jǐn)?shù)據(jù)結(jié)構(gòu)性質(zhì)、算法操作性能方面起到非常重要的作用，伸展樹可以作為各種線性序列的索引組織方法，在一些需要高效索引的大工程中加以運(yùn)用。