“伸展樹—一種高效的索引樹”教學設計

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

關鍵詞：數(shù)據(jù)結構；索引；二叉搜索樹；伸展樹

1.在數(shù)據(jù)結構與算法課程中的定位和前測知識點

數(shù)據(jù)結構涉及邏輯、存儲和運算3個維度。數(shù)據(jù)的存儲結構主要有順序、鏈接、索引和散列4種方法。數(shù)據(jù)的運算主要是對單個數(shù)據(jù)的增、刪、查、改，或對整體數(shù)據(jù)的排序、索引和檢索。有效的索引可以加快運算速度，可以說索引是數(shù)據(jù)結構與算法的重要內容Ⅲ。

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

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

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

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

前測知識點要求如下，可以根據(jù)需要給學生補充：

（1）二叉搜索樹BST的性質：中序遍歷下結點關鍵碼有序，左旋、右旋基本操作；

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

（3）AVL樹、紅黑樹的簡單定義。

2.學習目標

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

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

（3）伸展樹的實現(xiàn)和簡單應用；

（4）伸展樹的均攤時間效率。

3.知識點和學時分配

理論授課0.5學時。

主講教師可以根據(jù)學生的狀況、教師的科研背景等對某些方面進行擴展并引導學生，以適當擴大學生的涉獵面。

4.重點和難點

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

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

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

5.授課提示

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

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

6.練習與擴展

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

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

算法類作業(yè)有：

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

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

利用伸展樹存儲文件中單詞詞頻可以作為一個小型綜合設計題布置給學生。

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

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

（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.結語

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