數據結構中平衡二叉樹的教學探討與研究

朱洪浩

（蚌埠學院 計算機科學與技術系，安徽 蚌埠 233000）

數據結構中平衡二叉樹的教學探討與研究

朱洪浩

（蚌埠學院 計算機科學與技術系，安徽 蚌埠 233000）

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

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

1 引言

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

平衡二叉樹在插入結點和刪除結點時候，會使其變得不平衡.為此，需要對二叉排序樹進行調整,使之重新變為平衡二叉樹.相關教材和論文中關于平衡二叉樹的調整方法較難理解，學生難以接受.筆者通過閱讀大量的相關資料，并且總結教學經驗，提出了一種易于理解和實用的二叉排序樹轉換成平衡二叉樹方法.

2 平衡二叉樹調整方法的文獻綜述

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

嚴蔚敏、吳偉民[1]在《數據結構》（C語言版）一書中二叉排序樹調整為平衡二叉樹采用左旋轉（LL）、右旋轉（LR）、先左旋轉后右旋轉（LR）、先右旋轉后左旋轉（RL）四種旋轉方法.

李春葆[2]在《數據結構教程》（第2版）一書中也是采用了LL、LR、RR、RL四種旋轉方法.

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

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

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

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

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

3 平衡二叉樹的調整方法

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

3.1 插入結點的調整

插入結點時，可以利用規則一、規則二進行：

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

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

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

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

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

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

3.2 刪除結點的調整

刪除結點時，要確定刪除的結點是否是葉子結點，具體方法見規則三.

規則三

（1）若刪除的是葉子結點，直接刪除，并且自底向下查看樹中的平衡因子，若發現存在平衡因子為2時，采用規則一進行調整，若平衡因子為-2時，則采用規則二進行調整.

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

4 算法描述

4.1 插入結點的算法

平衡二叉樹的插入實現算法步驟：

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

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

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

（4）回到（1），繼續插入新的結點，直到所有的結點都插入完為止.

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

圖1 利用規則一、規則二構造AVL樹的過程

4.2 刪除結點的算法

平衡二叉樹的刪除實現算法步驟：

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

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

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

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

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

圖2 刪除AVL中結點的過程

5 結束語

平衡二叉樹的調整是數據結構教學中的重點和難點，學生在學習的過程中對該部分內容難以理解和接受，為了打破這種局面，作者通過閱讀大量的資料，總結了此方法，該方法“只需找到新的根結點，重新構造成二叉排序樹”即可，通過教學實踐發現，本文采用的方法容易被學生理解和掌握，在教學中得到了良好的效果，得到學生的認可.

〔1〕嚴蔚敏，吳偉民.數據結構(C 語言版)[M].北京：清華大學出版社，2007.

〔2〕李春葆.數據結構教程（第 2版）.北京：清華大學出版社，2007.

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

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

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

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

TP311.12

A

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

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