平衡二叉樹調整教學探討

張標漢

文章編號：1672-5913(2009)10-0051-02

摘要：平衡二叉樹教學中傳統的旋轉方法不太容易被學生理解，針對這一問題，本文通過分析二叉排序樹的基本原理，摸索出一種在教學實踐中更加容易被學生理解的平衡二叉樹調整方法。

關鍵詞：二叉排序樹 平衡二叉樹 教學探討

中圖分類號：G642

文獻標識碼：B

在“數據結構與算法”課程教學中，許多教科書在介紹平衡二叉樹調整這部分內容時，采用的都是旋轉的方法，將不平衡二叉樹用左右、順逆時針旋轉的方法使失去平衡的二叉排序樹調整為平衡二叉樹。但是在實際教學過程中，筆者發現這樣的方法不太容易被學生理解，許多學生尤其是?？茖W生搞不清楚怎么旋轉、圍繞誰旋轉。針對這一問題，筆者通過不斷的教學實踐摸索出一種更容易被學生接受和理解的平衡二叉樹調整方法——填空法，這種方法充分利用了二叉排序樹的特點，采用填空的方式對失衡的二叉排序樹進行調整使之保持平衡。

1基本原理

我們知道，二叉排序樹具有這樣一個特點：左子樹上所有結點的值均小于它的根結點的值，右子樹上所有結點的值均大于它的根結點的值。即有這樣一個關系：左<根<右。利用這個特點，當我們在插入結點使得原平衡二叉樹失去平衡而需要進行調整時，首先尋找最小不平衡子樹。最小不平衡子樹的尋找方法是：從插入的結點出發，依次計算其祖先的平衡因子，發現的第一個平衡因子的絕對值大于1的結點就是最小不平衡子樹的根結點，則以它為根結點的子樹就是最小不平衡子樹。先考慮最簡單的情況，這棵最小不平衡子樹僅由三個結點構成。此時最小不平衡子樹可以分為四種基本類型，分別是：LL型、LR型、RL型和RR型。如圖1所示：

在教科書中，這四種情況是分別討論的：對LL型做一次順時針旋轉，對LR型先逆時針旋轉后順時針旋轉，對RL型先順時針旋轉后逆時針旋轉，對RR型做一次逆時針旋轉。但應用填空法，這四種基本情況的調整可以統一在一起：

可以知道，要使得由三個結點構成的二叉排序樹平衡，其基本結構必定是一個結點作為根結點，一個作為左孩子結點，一個作為右孩子結點。如圖2所示：

根據二叉排序樹的特點(左<根<右)，我們只要把上述每種基本情況中的三個結點按值從小到大排列，將最小的一個填在左孩子結點位置，最大的一個填在右孩子結點位置，中間的填在根結點位置。很容易地就可以將上述四種最小不平衡子樹調整為平衡二叉樹，如圖3所示：

進一步考慮更為復雜的情況，假定上述結點各自還有左右子樹，我們仍然可以使用我們的填空法輕松的加以調整。這四種復雜情況如圖4所示：

假定都在CL中插入一個結點使得A的平衡因子的絕對值變為2從而使得原平衡二叉樹失去平衡，此時以A為根結點的子樹就是最小不平衡子樹，這棵最小不平衡子樹可以分為7個部分。沿著從根結點A到插入結點位置CL的路徑方向依次取三個結點，假設為A、B、C，它們和剩下的AL、AR、BL、BR、CL、CR中的4個構成的二叉排序樹要成為平衡二叉樹，則由這7個部分組成的平衡二叉樹的基本結構一定是如圖5所示情形：

其中，A、B、C三者中值最小的為左子樹的根結點，值最大的為右子樹的根結點，中間的為整個最小不平衡子樹的根結點。其余的AL、AR、BL、BR、CL、CR等按從小到大的順序排列，將它們從左到右依次填在樹的第三層即可，完成后的二叉樹一定是平衡二叉樹。對上述四種復雜情形，平衡后如圖6所示：

2示例

例：已知長度為12的表：{Jan,Feb,Mar,Apr,May,June, July,Aug,Sep,Oct,Nov,Dec}，按照表中元素順序構造一棵平衡二叉排序樹。

解：構造過程如圖7、圖8所示。

教學實踐證明，本文采用的填空法要比傳統的旋轉法更容易被學生接受和理解。

參考文獻：

[1] 嚴蔚敏,吳偉民. 數據結構(C語言版)[M]. 北京:清華大學出版社,1997.

[2] 馬秋菊. 數據結構(C語言描述)[M]. 北京:中國水利水電出版社,2006.

Discussion on Teaching of Balancing the Binary Tree

ZHANG Biao-han

(The Department of Maths & Computer Science, Sanming College, Sanming 365004, China)

Abstract:The rotation method for balanced binary tree is not easy to understand by the students, This paper introduced a new method using the characteristics of the binary sort tree that is easier to understand by the students.

Key words:binary sort tree; balanced binary tree; teaching discussion