平衡二叉樹(shù)調(diào)整教學(xué)探討

張標(biāo)漢

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

摘要：平衡二叉樹(shù)教學(xué)中傳統(tǒng)的旋轉(zhuǎn)方法不太容易被學(xué)生理解，針對(duì)這一問(wèn)題，本文通過(guò)分析二叉排序樹(shù)的基本原理，摸索出一種在教學(xué)實(shí)踐中更加容易被學(xué)生理解的平衡二叉樹(shù)調(diào)整方法。

關(guān)鍵詞：二叉排序樹(shù) 平衡二叉樹(shù) 教學(xué)探討

中圖分類(lèi)號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

在“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)中，許多教科書(shū)在介紹平衡二叉樹(shù)調(diào)整這部分內(nèi)容時(shí)，采用的都是旋轉(zhuǎn)的方法，將不平衡二叉樹(shù)用左右、順逆時(shí)針旋轉(zhuǎn)的方法使失去平衡的二叉排序樹(shù)調(diào)整為平衡二叉樹(shù)。但是在實(shí)際教學(xué)過(guò)程中，筆者發(fā)現(xiàn)這樣的方法不太容易被學(xué)生理解，許多學(xué)生尤其是專(zhuān)科學(xué)生搞不清楚怎么旋轉(zhuǎn)、圍繞誰(shuí)旋轉(zhuǎn)。針對(duì)這一問(wèn)題，筆者通過(guò)不斷的教學(xué)實(shí)踐摸索出一種更容易被學(xué)生接受和理解的平衡二叉樹(shù)調(diào)整方法——填空法，這種方法充分利用了二叉排序樹(shù)的特點(diǎn)，采用填空的方式對(duì)失衡的二叉排序樹(shù)進(jìn)行調(diào)整使之保持平衡。

1基本原理

我們知道，二叉排序樹(shù)具有這樣一個(gè)特點(diǎn)：左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。即有這樣一個(gè)關(guān)系：左<根<右。利用這個(gè)特點(diǎn)，當(dāng)我們?cè)诓迦虢Y(jié)點(diǎn)使得原平衡二叉樹(shù)失去平衡而需要進(jìn)行調(diào)整時(shí)，首先尋找最小不平衡子樹(shù)。最小不平衡子樹(shù)的尋找方法是：從插入的結(jié)點(diǎn)出發(fā)，依次計(jì)算其祖先的平衡因子，發(fā)現(xiàn)的第一個(gè)平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)就是最小不平衡子樹(shù)的根結(jié)點(diǎn)，則以它為根結(jié)點(diǎn)的子樹(shù)就是最小不平衡子樹(shù)。先考慮最簡(jiǎn)單的情況，這棵最小不平衡子樹(shù)僅由三個(gè)結(jié)點(diǎn)構(gòu)成。此時(shí)最小不平衡子樹(shù)可以分為四種基本類(lèi)型，分別是：LL型、LR型、RL型和RR型。如圖1所示：

在教科書(shū)中，這四種情況是分別討論的：對(duì)LL型做一次順時(shí)針旋轉(zhuǎn)，對(duì)LR型先逆時(shí)針旋轉(zhuǎn)后順時(shí)針旋轉(zhuǎn)，對(duì)RL型先順時(shí)針旋轉(zhuǎn)后逆時(shí)針旋轉(zhuǎn)，對(duì)RR型做一次逆時(shí)針旋轉(zhuǎn)。但應(yīng)用填空法，這四種基本情況的調(diào)整可以統(tǒng)一在一起：

可以知道，要使得由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹(shù)平衡，其基本結(jié)構(gòu)必定是一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，一個(gè)作為左孩子結(jié)點(diǎn)，一個(gè)作為右孩子結(jié)點(diǎn)。如圖2所示：

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

進(jìn)一步考慮更為復(fù)雜的情況，假定上述結(jié)點(diǎn)各自還有左右子樹(shù)，我們?nèi)匀豢梢允褂梦覀兊奶羁辗ㄝp松的加以調(diào)整。這四種復(fù)雜情況如圖4所示：

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

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

2示例

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

解：構(gòu)造過(guò)程如圖7、圖8所示。

教學(xué)實(shí)踐證明，本文采用的填空法要比傳統(tǒng)的旋轉(zhuǎn)法更容易被學(xué)生接受和理解。

參考文獻(xiàn)：

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

[2] 馬秋菊. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)[M]. 北京:中國(guó)水利水電出版社,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