張標漢
文章編號:1672-5913(2009)10-0051-02
摘要:平衡二叉樹教學(xué)中傳統(tǒng)的旋轉(zhuǎn)方法不太容易被學(xué)生理解,針對這一問題,本文通過分析二叉排序樹的基本原理,摸索出一種在教學(xué)實踐中更加容易被學(xué)生理解的平衡二叉樹調(diào)整方法。
關(guān)鍵詞:二叉排序樹 平衡二叉樹 教學(xué)探討
中圖分類號:G642
文獻標識碼:B
在“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)中,許多教科書在介紹平衡二叉樹調(diào)整這部分內(nèi)容時,采用的都是旋轉(zhuǎn)的方法,將不平衡二叉樹用左右、順逆時針旋轉(zhuǎn)的方法使失去平衡的二叉排序樹調(diào)整為平衡二叉樹。但是在實際教學(xué)過程中,筆者發(fā)現(xiàn)這樣的方法不太容易被學(xué)生理解,許多學(xué)生尤其是??茖W(xué)生搞不清楚怎么旋轉(zhuǎn)、圍繞誰旋轉(zhuǎn)。針對這一問題,筆者通過不斷的教學(xué)實踐摸索出一種更容易被學(xué)生接受和理解的平衡二叉樹調(diào)整方法——填空法,這種方法充分利用了二叉排序樹的特點,采用填空的方式對失衡的二叉排序樹進行調(diào)整使之保持平衡。
1基本原理
我們知道,二叉排序樹具有這樣一個特點:左子樹上所有結(jié)點的值均小于它的根結(jié)點的值,右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。即有這樣一個關(guān)系:左<根<右。利用這個特點,當(dāng)我們在插入結(jié)點使得原平衡二叉樹失去平衡而需要進行調(diào)整時,首先尋找最小不平衡子樹。最小不平衡子樹的尋找方法是:從插入的結(jié)點出發(fā),依次計算其祖先的平衡因子,發(fā)現(xiàn)的第一個平衡因子的絕對值大于1的結(jié)點就是最小不平衡子樹的根結(jié)點,則以它為根結(jié)點的子樹就是最小不平衡子樹。先考慮最簡單的情況,這棵最小不平衡子樹僅由三個結(jié)點構(gòu)成。此時最小不平衡子樹可以分為四種基本類型,分別是:LL型、LR型、RL型和RR型。如圖1所示:
在教科書中,這四種情況是分別討論的:對LL型做一次順時針旋轉(zhuǎn),對LR型先逆時針旋轉(zhuǎn)后順時針旋轉(zhuǎn),對RL型先順時針旋轉(zhuǎn)后逆時針旋轉(zhuǎn),對RR型做一次逆時針旋轉(zhuǎn)。但應(yīng)用填空法,這四種基本情況的調(diào)整可以統(tǒng)一在一起:
可以知道,要使得由三個結(jié)點構(gòu)成的二叉排序樹平衡,其基本結(jié)構(gòu)必定是一個結(jié)點作為根結(jié)點,一個作為左孩子結(jié)點,一個作為右孩子結(jié)點。如圖2所示:
根據(jù)二叉排序樹的特點(左<根<右),我們只要把上述每種基本情況中的三個結(jié)點按值從小到大排列,將最小的一個填在左孩子結(jié)點位置,最大的一個填在右孩子結(jié)點位置,中間的填在根結(jié)點位置。很容易地就可以將上述四種最小不平衡子樹調(diào)整為平衡二叉樹,如圖3所示:
進一步考慮更為復(fù)雜的情況,假定上述結(jié)點各自還有左右子樹,我們?nèi)匀豢梢允褂梦覀兊奶羁辗ㄝp松的加以調(diào)整。這四種復(fù)雜情況如圖4所示:
假定都在CL中插入一個結(jié)點使得A的平衡因子的絕對值變?yōu)?從而使得原平衡二叉樹失去平衡,此時以A為根結(jié)點的子樹就是最小不平衡子樹,這棵最小不平衡子樹可以分為7個部分。沿著從根結(jié)點A到插入結(jié)點位置CL的路徑方向依次取三個結(jié)點,假設(shè)為A、B、C,它們和剩下的AL、AR、BL、BR、CL、CR中的4個構(gòu)成的二叉排序樹要成為平衡二叉樹,則由這7個部分組成的平衡二叉樹的基本結(jié)構(gòu)一定是如圖5所示情形:
其中,A、B、C三者中值最小的為左子樹的根結(jié)點,值最大的為右子樹的根結(jié)點,中間的為整個最小不平衡子樹的根結(jié)點。其余的AL、AR、BL、BR、CL、CR等按從小到大的順序排列,將它們從左到右依次填在樹的第三層即可,完成后的二叉樹一定是平衡二叉樹。對上述四種復(fù)雜情形,平衡后如圖6所示:
2示例
例:已知長度為12的表:{Jan,Feb,Mar,Apr,May,June, July,Aug,Sep,Oct,Nov,Dec},按照表中元素順序構(gòu)造一棵平衡二叉排序樹。
解:構(gòu)造過程如圖7、圖8所示。
教學(xué)實踐證明,本文采用的填空法要比傳統(tǒng)的旋轉(zhuǎn)法更容易被學(xué)生接受和理解。
參考文獻:
[1] 嚴蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京:清華大學(xué)出版社,1997.
[2] 馬秋菊. 數(shù)據(jù)結(jié)構(gòu)(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