朱洪浩

（蚌埠學(xué)院 計算機科學(xué)與技術(shù)系，安徽 蚌埠 233000）

數(shù)據(jù)結(jié)構(gòu)中平衡二叉樹的教學(xué)探討與研究

朱洪浩

（蚌埠學(xué)院 計算機科學(xué)與技術(shù)系，安徽 蚌埠 233000）

平衡二叉樹是對二叉排序樹的一種改進，又被稱為AVL樹，平衡二叉樹的結(jié)構(gòu)較好，可以提高查找運算的速度.本文分析了權(quán)威教材和相關(guān)論文中平衡二叉樹的調(diào)整方法，這些方法學(xué)生普遍反映理解和掌握較困難.據(jù)此，本文依據(jù)平衡因子和二叉排序樹的特性，設(shè)計出一種基于平衡因子和二叉排序樹的平衡二叉樹的調(diào)整方法，該方法易于理解和掌握.

二叉排序樹；平衡因子；平衡二叉樹

1 引言

數(shù)據(jù)結(jié)構(gòu)課程是計算機及相關(guān)專業(yè)的核心課程，是程序設(shè)計的重要理論技術(shù)基礎(chǔ)[1].在動態(tài)查找表中，平衡二叉樹被廣泛的應(yīng)用，平衡二叉樹又稱AVL 樹,它是由 Adel，son-Vel，skii和 Landis兩位數(shù)學(xué)家于1962年提出并用他們的名字來命名的.平衡二叉樹或者是一棵空樹，或者是滿足下列條件的二叉排序樹：二叉排序樹的所有結(jié)點的平衡因子為-1、0 和 1.所謂平衡因子 BF（Balance Factor）可定義為某結(jié)點左子樹的深度減去右子樹的深度[2].若二叉樹中任一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就不是平衡二叉樹.

平衡二叉樹在插入結(jié)點和刪除結(jié)點時候，會使其變得不平衡.為此，需要對二叉排序樹進行調(diào)整,使之重新變?yōu)槠胶舛鏄?相關(guān)教材和論文中關(guān)于平衡二叉樹的調(diào)整方法較難理解，學(xué)生難以接受.筆者通過閱讀大量的相關(guān)資料，并且總結(jié)教學(xué)經(jīng)驗，提出了一種易于理解和實用的二叉排序樹轉(zhuǎn)換成平衡二叉樹方法.

2 平衡二叉樹調(diào)整方法的文獻綜述

由于平衡二叉樹的重要性，以及學(xué)生在學(xué)習(xí)平衡二叉樹調(diào)整的過程中，普遍反映對用于平衡二叉樹調(diào)整的四種方法較難理解，算法復(fù)雜.為此，許多學(xué)者對平衡二叉樹的調(diào)整進行了大量的研究.

嚴(yán)蔚敏、吳偉民[1]在《數(shù)據(jù)結(jié)構(gòu)》（C語言版）一書中二叉排序樹調(diào)整為平衡二叉樹采用左旋轉(zhuǎn)（LL）、右旋轉(zhuǎn)（LR）、先左旋轉(zhuǎn)后右旋轉(zhuǎn)（LR）、先右旋轉(zhuǎn)后左旋轉(zhuǎn)（RL）四種旋轉(zhuǎn)方法.

李春葆[2]在《數(shù)據(jù)結(jié)構(gòu)教程》（第2版）一書中也是采用了LL、LR、RR、RL四種旋轉(zhuǎn)方法.

朱宇、張紅彬[3]在《平衡二叉樹的選擇調(diào)整算法》一文中，提出利用“中為根、小為左、大為右”的調(diào)整策略，但本質(zhì)上仍然是利用旋轉(zhuǎn)的思想.

胡云[4]在《快速構(gòu)建AVL樹》一文中采用“將二叉排序樹中的數(shù)據(jù)進行排序,將中點數(shù)據(jù)作為根,大于中點的數(shù)據(jù)構(gòu)成右子樹，小于中點的數(shù)據(jù)構(gòu)成左子樹，然后采用同樣的方法分別對左子樹和右子樹進行調(diào)整.”但從作者舉出的實例可以看出，該方法與傳統(tǒng)方法得到的平衡二叉樹并不一致.

杜薇薇[5]等在《基于平衡因子的AVL樹設(shè)計實現(xiàn)》一文中則從平衡因子出發(fā),并用數(shù)學(xué)公式進行了驗證了插入和刪除操作.

劉紹翰[6]等在《一種簡化的AVL樹的實現(xiàn)方法》一文提出了高度平衡樹(HAVL)它是一種新的AVL樹的數(shù)學(xué)描述.

以上文獻中雖然提出了較好的調(diào)整方法，但在平衡二叉樹的調(diào)整基本上仍然是采用旋轉(zhuǎn)的方法進行調(diào)整，并沒有從根本上解決學(xué)生的困惑.筆者在教學(xué)中發(fā)現(xiàn)學(xué)生對二叉排序樹的建立普遍能熟練掌握，并且平衡二叉樹的前提必須是一棵二叉排序樹，為此，本文提出了一種利用平衡因子和構(gòu)建二叉排序樹的方法來實現(xiàn)平衡二叉樹的調(diào)整，從而解決了學(xué)生的困惑.

3 平衡二叉樹的調(diào)整方法

根據(jù)平衡二叉樹的定義可知，插入和刪除結(jié)點造成平衡二叉樹不平衡的原因是產(chǎn)生2或者-2的平衡因子，其實，調(diào)整的方法只需將以平衡因子為2或者-2為根結(jié)點的子二叉排序樹重新找一個根結(jié)點建立新的子二叉排序樹.從而使二叉排序樹中的平衡因子都為-1、0或者1，即調(diào)整成為平衡二叉樹.問題的關(guān)鍵是如何找根結(jié)點，即序列中的第一個結(jié)點，具體方法如下文所示規(guī)則.

3.1 插入結(jié)點的調(diào)整

插入結(jié)點時，可以利用規(guī)則一、規(guī)則二進行：

規(guī)則一 某結(jié)點的平衡因子為2時，把以該結(jié)點為根的樹采用中序遍歷的方法進行遍歷，即得到一個遞增的子序列，同時看該結(jié)點的左孩子的平衡因子.

（1）若左孩子的平衡因子為-1時，則取該左孩子的右孩子結(jié)點，并將其移動到序列的最前面，得到一個新的序列，對該序列構(gòu)造二叉排序樹.

（2）若左孩子的平衡因子為1時，則取該左孩子結(jié)點，并將其移動到序列的最前面，得到一個新序列，對該序列構(gòu)造二叉排序樹.

規(guī)則二 某結(jié)點的平衡因子為-2時，把以該結(jié)點為根的樹采用中序遍歷的方法進行遍歷，即得到一個遞增的子序列，同時看該結(jié)點的右孩子的平衡因子.

（1）若右孩子的平衡因子為-1時，則取該右孩子結(jié)點，并將其移動到序列的最前面，得到一個新的序列，對該序列構(gòu)造二叉排序樹.

（2）若右孩子的平衡因子為1時，則取該右孩子的左孩子結(jié)點，并將其移動到序列的最前面，得到一個新序列，對該序列構(gòu)造二叉排序樹.

3.2 刪除結(jié)點的調(diào)整

刪除結(jié)點時，要確定刪除的結(jié)點是否是葉子結(jié)點，具體方法見規(guī)則三.

規(guī)則三

（1）若刪除的是葉子結(jié)點，直接刪除，并且自底向下查看樹中的平衡因子，若發(fā)現(xiàn)存在平衡因子為2時，采用規(guī)則一進行調(diào)整，若平衡因子為-2時，則采用規(guī)則二進行調(diào)整.

（2）若不是葉子結(jié)點，首先按照二叉排序樹非葉子結(jié)點的刪除方法即用該結(jié)點左子樹的最大值（或者右子樹的最小值）代替該結(jié)點，然后在從二叉排序樹中刪去它的最大值（或者最小值），同樣，自底向下查看樹中的平衡因子，若發(fā)現(xiàn)存在平衡因子為2時，采用規(guī)則一進行調(diào)整，若平衡因子為-2時，則采用規(guī)則二進行調(diào)整.

4 算法描述

4.1 插入結(jié)點的算法

平衡二叉樹的插入實現(xiàn)算法步驟：

（1）插入結(jié)點L（L總是作為新的葉子結(jié)點插入的），插入的方法同一般的二叉排序樹插入結(jié)點一樣.

（2）沿著插入結(jié)點L的路線返回，逐層回溯.必要時修改L的祖先的平衡因子，發(fā)現(xiàn)平衡因子為2或-2時，則利用規(guī)則一、規(guī)則二找到結(jié)點R.

（3）把該二叉排序樹進行中序遍歷，得到一遞增序列，并把結(jié)點R移動到該序列的最前面，然后對新形成的序列構(gòu)造二叉排序樹.同時檢查樹中其它結(jié)點，若發(fā)現(xiàn)平衡因子為2或-2的結(jié)點，進行調(diào)整.重復(fù)（2）（3）直到所有的結(jié)點都保持平衡為止.

（4）回到（1），繼續(xù)插入新的結(jié)點，直到所有的結(jié)點都插入完為止.

實例1：輸入關(guān)鍵字序列{16,3,7,11,9,26,18,14,15}，構(gòu)造一棵平衡二叉樹[2].

圖1 利用規(guī)則一、規(guī)則二構(gòu)造AVL樹的過程

4.2 刪除結(jié)點的算法

平衡二叉樹的刪除實現(xiàn)算法步驟：

（1）用二叉排序樹的刪除算法找到并刪除結(jié)點L.

（2）從被刪除結(jié)點到根結(jié)點逐層向上回溯，必要時修改L的祖先結(jié)點的平衡因子，發(fā)現(xiàn)平衡因子為2或-2時，則利用規(guī)則一、規(guī)則二找到結(jié)點R.

（3）把該二叉排序樹進行中序遍歷，得到一遞增序列，并把結(jié)點R移動到該序列的最前面，然后對新形成的序列構(gòu)造二叉排序樹.

（4）如果調(diào)整之后，子樹的總高度比調(diào)整前降低了，仍然要繼續(xù)回溯，直到所有結(jié)點平衡因子都為-1、0、1時，即都保持平衡為止.

實例2：對實例1生成的AVL樹，給出刪除結(jié)點11,9,14的步驟[2].

圖2 刪除AVL中結(jié)點的過程

5 結(jié)束語

平衡二叉樹的調(diào)整是數(shù)據(jù)結(jié)構(gòu)教學(xué)中的重點和難點，學(xué)生在學(xué)習(xí)的過程中對該部分內(nèi)容難以理解和接受，為了打破這種局面，作者通過閱讀大量的資料，總結(jié)了此方法，該方法“只需找到新的根結(jié)點，重新構(gòu)造成二叉排序樹”即可，通過教學(xué)實踐發(fā)現(xiàn)，本文采用的方法容易被學(xué)生理解和掌握，在教學(xué)中得到了良好的效果，得到學(xué)生的認(rèn)可.

〔1〕嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C 語言版)[M].北京：清華大學(xué)出版社，2007.

〔2〕李春葆.數(shù)據(jù)結(jié)構(gòu)教程（第 2版）.北京：清華大學(xué)出版社，2007.

〔3〕朱宇，張紅彬.平衡二叉樹的選擇調(diào)整算法[J].中國科學(xué)院研究生院學(xué)報，2006，23（4）:527-533.

〔4〕胡云.快速構(gòu)建 AVL樹[J].安陽師范學(xué)院學(xué)報，2007（6）：61-63.

〔5〕杜薇薇，張翼燕，瞿春柳.基于平衡因子的AVL樹設(shè)計實現(xiàn)[J].計算機技術(shù)與發(fā)展，2010，20（3）:24-27.

〔6〕劉紹翰，高天行，黃志球.一種簡化的AVL樹的實現(xiàn)方法 [J].三峽大學(xué)學(xué)報 (自然科學(xué)版)，2011，33（1）:85-87.

TP311.12

A

1673-260X（2012）03-0019-03

安徽省自然科學(xué)基金項目（11040606M151）資助