劉慧 張兆維

摘? 要： 平衡二叉樹的失衡調(diào)整不僅是數(shù)據(jù)結(jié)構(gòu)課程的一個(gè)重要理論知識點(diǎn)，在軟件開發(fā)過程中也有廣泛的實(shí)際應(yīng)用。旋轉(zhuǎn)是對平衡二叉樹進(jìn)行失衡調(diào)整的主要手段，然而傳統(tǒng)的左右旋轉(zhuǎn)方法存在著操作繁瑣、處理分散、不易被學(xué)生理解的問題。對此，文章提出一種五步失衡調(diào)整方法，該方法通過對四種旋轉(zhuǎn)類型進(jìn)行統(tǒng)一處理，簡化了處理流程，從而降低了學(xué)生的理解難度。實(shí)際的教學(xué)結(jié)果驗(yàn)證了該方法的教學(xué)效果。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu); 平衡二叉樹; 失衡調(diào)整; 平衡因子; 五步失衡調(diào)整

中圖分類號：G642? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2020）11-78-04

Abstract： The imbalance adjustment of the balanced binary tree is not only an important theoretical knowledge point of data structure course， but also has a wide range of practical applications in the development of software. Rotation is the main means to adjust the imbalance of balanced binary tree. However， the traditional left-right rotation method has the problems of cumbersome operation， scattered processing and difficult to be understood by students. Therefore this paper proposes a five step imbalance adjustment method， which simplifies the process by unifying the processing of four types of rotation， so as to reduce the difficulty of students' understanding. The actual teaching results verify the teaching effect of this method.

Key words： data structure; balanced binary tree; imbalance adjustment; balance factor; five-step imbalance adjustment method

0 引言

作為“數(shù)據(jù)結(jié)構(gòu)”課程[1]中的核心概念，二叉樹在學(xué)生考研或工作中處于重要的地位，其中，平衡二叉樹的失衡調(diào)整又是重重之重，引起了教學(xué)的廣泛關(guān)注和研究。平衡二叉樹是決定搜索性能的關(guān)鍵因素，一旦失衡，其搜索性能有可能會(huì)退化為線性表。失衡調(diào)整是將失去平衡的二叉樹通過某種調(diào)整而成為一棵平衡二叉樹，具有種類多樣（“LL”、“RR”、“LR”和“RL”等四種）、操作繁瑣（左旋轉(zhuǎn)、右旋轉(zhuǎn)、先左后右旋轉(zhuǎn)和先右后左旋轉(zhuǎn)等）、處理分散、容易混淆的特點(diǎn)，加大了學(xué)生的理解難度。

為了進(jìn)一步降低失衡調(diào)整的理解難度，本文提出一種五步失衡調(diào)整方法，化繁為簡，實(shí)用至上，以應(yīng)對所有類型的平衡二叉樹失衡情況。

1 面臨的問題

平衡二叉樹的失衡調(diào)整是“算法與數(shù)據(jù)結(jié)構(gòu)”課程的核心內(nèi)容之一，在考研和工作中都扮演著十分重要的角色。然而，在實(shí)際教學(xué)過程中，平衡二叉樹的傳統(tǒng)失衡調(diào)整方法不容易被學(xué)生理解和掌握，導(dǎo)致學(xué)生在學(xué)習(xí)該知識點(diǎn)時(shí)有畏難情緒，甚至存在厭學(xué)、逃學(xué)的情況。

針對平衡二叉樹的失衡調(diào)整方法，眾多專家和學(xué)者對此進(jìn)行了廣泛的研究和討論[2-4]。在當(dāng)前大部分教材中，根據(jù)平衡二叉樹的失衡狀態(tài)，失衡調(diào)整分為四類（“LL”、“RR”、“LR”和“RL”），在每一類中，失衡調(diào)整采用不同的左、右旋轉(zhuǎn)操作來校正失衡[2]。朱宇[3]等對傳統(tǒng)的旋轉(zhuǎn)調(diào)整方法進(jìn)行了改進(jìn)，提高了調(diào)整速度和效率。陳海濤[4]等根據(jù)二叉排序樹的原理，總結(jié)出四類簡單的失衡調(diào)整方法。張標(biāo)漢[5]利用“左小、中根、右大”規(guī)律提出一種填空法來調(diào)整平衡二叉樹的失衡狀態(tài)。朱洪浩[6]提根據(jù)二叉排序樹的特點(diǎn)，提出一種基于平衡因子和二叉排序樹的失衡調(diào)整方法，在一定程度上降低了學(xué)生理解和掌握的難度。

然而，上述方法雖有改進(jìn)，但其核心思想還是圍繞左右旋轉(zhuǎn)調(diào)整方法展開的。表1對傳統(tǒng)的左右旋轉(zhuǎn)調(diào)整方法的具體處理方式進(jìn)行了匯總。從表1中我們可以看出，傳統(tǒng)的左右旋轉(zhuǎn)方法有種類多樣、操作繁瑣、處理分散，容易混淆等特點(diǎn)，因而不易被學(xué)生理解。

2 五步失衡調(diào)整方法

為降低學(xué)生對平衡二叉樹失衡調(diào)整的理解難度，本文提出一種五步失衡調(diào)整方法，不再對“LL”、“RR”、“LR”和“RL”四種失衡狀態(tài)進(jìn)行單獨(dú)處理，而是采用一套統(tǒng)一的處理流程，簡化了處理步驟，有利于學(xué)生對平衡二叉樹的掌握。

平衡二叉樹的五步失衡調(diào)整方法的核心思想是依據(jù)失衡路線將結(jié)點(diǎn)分為框內(nèi)結(jié)點(diǎn)和框外結(jié)點(diǎn)，通過這些結(jié)點(diǎn)的重構(gòu)完成所有狀況下平衡二叉樹的失衡調(diào)整，該方法主要包含五個(gè)步驟，如圖1所示，每一步的具體實(shí)現(xiàn)如下：

⑴ 尋找失衡結(jié)點(diǎn)：計(jì)算當(dāng)前二叉樹中各個(gè)結(jié)點(diǎn)的左右子樹的高度差，即平衡因子，依據(jù)平衡因子確定最小失衡子樹，將該子樹的根結(jié)點(diǎn)定義為失衡結(jié)點(diǎn);

⑵ 劃分結(jié)點(diǎn)為框內(nèi)結(jié)點(diǎn)和框外結(jié)點(diǎn)：從失衡結(jié)點(diǎn)開始，沿失衡方向，連續(xù)的三個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)三點(diǎn)框，這三個(gè)結(jié)點(diǎn)定義為框內(nèi)結(jié)點(diǎn)，其余結(jié)點(diǎn)定義為框外結(jié)點(diǎn);

⑶ 框內(nèi)結(jié)點(diǎn)的重構(gòu)：對三點(diǎn)框內(nèi)的結(jié)點(diǎn)進(jìn)行排序，其中中間值結(jié)點(diǎn)替代失衡結(jié)點(diǎn)成為根節(jié)點(diǎn)，小值結(jié)點(diǎn)成為左子樹，大值結(jié)點(diǎn)成為右子樹，構(gòu)成“左小右大”的二叉排序樹;

（4）與框內(nèi)左右子樹相連的框外結(jié)點(diǎn)的重構(gòu)：與框內(nèi)左右子樹相連的框外結(jié)點(diǎn)，分別搬移到框內(nèi)，分別構(gòu)成原有結(jié)點(diǎn)的左子樹或者右子樹;

⑸ 與框內(nèi)根結(jié)點(diǎn)相連的框外結(jié)點(diǎn)的重構(gòu)：依據(jù)二叉排序樹的定義，將其插入到二叉排序樹的對應(yīng)位置中。

為驗(yàn)證五步失衡調(diào)整方法對 “LL”、“RR”、“LR”和“RL”四種失衡狀態(tài)的有效性，以下將采用該方法對各種失衡狀態(tài)進(jìn)行詳細(xì)分析。由于“LL”型和“RR”型，“LR”型和“RL”型分別是對稱的，本文僅考慮“LL”型和“LR”型，其余不再贅述。

⑴ “LL”型二叉排序樹的五步失衡調(diào)整

對于“LL”型二叉排序樹而言，其失衡狀態(tài)是由于在該樹某一節(jié)點(diǎn)的左子樹的左子樹中插入新的結(jié)點(diǎn)造成的，如圖2（a）所示，由于在n0結(jié)點(diǎn)的左子樹的左子樹中插入n5結(jié)點(diǎn)，造成當(dāng)前二叉排序樹的“LL”型失衡。

采用五步失衡調(diào)整方法對“LL”型二叉排序樹進(jìn)行失衡調(diào)整的具體處理流程如下：首先，尋找失衡結(jié)點(diǎn)，并依此確定哪些結(jié)點(diǎn)為框內(nèi)結(jié)點(diǎn)，哪些結(jié)點(diǎn)為框外結(jié)點(diǎn)，如圖2（b）所示，當(dāng)前二叉排序樹的失衡結(jié)點(diǎn)為n0，框內(nèi)結(jié)點(diǎn)為n0、n1、n3，框外結(jié)點(diǎn)為n2、n4、n5;其次，重構(gòu)框內(nèi)結(jié)點(diǎn)，框內(nèi)結(jié)點(diǎn)的排序結(jié)果為[n3?n1?n0]，以此排序結(jié)果構(gòu)建新的二叉排序樹，如圖2（c）所示，中間值結(jié)點(diǎn)n1為根節(jié)點(diǎn)，小值結(jié)點(diǎn)n3為左子樹，大值結(jié)點(diǎn)n0為右子樹;最后，重構(gòu)框外結(jié)點(diǎn)，框外結(jié)點(diǎn)n5和n2按照原有相連順序進(jìn)行重構(gòu)，框外結(jié)點(diǎn)n4與新的根結(jié)點(diǎn)n1相連，按照二叉排序樹的定義，將其插入到新的二叉排序樹中，如圖2（d）所示。

⑵ “LR”型二叉排序樹的五步失衡調(diào)整

對于“LR”型二叉排序樹而言，其失衡狀態(tài)是由于在該樹某一節(jié)點(diǎn)的左子樹的右子樹中插入新的結(jié)點(diǎn)造成的，如圖3（a）所示，由于在n0結(jié)點(diǎn)的左子樹的右子樹中插入n5結(jié)點(diǎn)，造成當(dāng)前二叉排序樹的“LR”型失衡。

采用五步失衡調(diào)整方法，對“LR”型二叉排序樹進(jìn)行失衡調(diào)整的具體處理流程：首先，尋找失衡結(jié)點(diǎn)，并依此確定哪些結(jié)點(diǎn)為框內(nèi)結(jié)點(diǎn)，哪些結(jié)點(diǎn)為框外結(jié)點(diǎn)，如圖3（b）所示，當(dāng)前二叉排序樹的失衡結(jié)點(diǎn)為n0，框內(nèi)結(jié)點(diǎn)為n0、n1、n4，框外結(jié)點(diǎn)為n2、n3、n5;其次，重構(gòu)框內(nèi)結(jié)點(diǎn)，框內(nèi)結(jié)點(diǎn)的排序結(jié)果為[n1?n4?n0]，以此排序結(jié)果構(gòu)建新的二叉排序樹，如圖3（c）所示，中間值結(jié)點(diǎn)n4為根節(jié)點(diǎn)，小值結(jié)點(diǎn)n1為左子樹，大值結(jié)點(diǎn)n0為右子樹;最后，重構(gòu)框外結(jié)點(diǎn)，框外結(jié)點(diǎn)n3和n2按照原有相連順序進(jìn)行重構(gòu)，框外結(jié)點(diǎn)n5與新的根結(jié)點(diǎn)n1相連，按照二叉排序樹的定義，將其插入到新的二叉排序樹中，如圖3（d）所示。

如前所述，鑒于四種失衡類型的對稱性，“RR”和“RL”型二叉排序樹的五步調(diào)整步驟本文中不再贅述，有興趣的讀者可自行驗(yàn)證。根據(jù)以上說明，我們可以看到，五步失衡調(diào)整方法對“LL”、“RR”、“LR”和“RL”四種失衡狀態(tài)都是有效的，能夠以一套統(tǒng)一的流程進(jìn)行處理，簡化了處理流程，具有統(tǒng)一處理、操作易記、不易混淆等特點(diǎn)，有效的降低了學(xué)生的理解難度。

3 教學(xué)效果

為分析本文所提方法的實(shí)際教學(xué)效果，筆者對學(xué)生的知識掌握水平和學(xué)習(xí)情況等進(jìn)行了面談和統(tǒng)計(jì)。被調(diào)查的對象為294名普通二本高校的大二學(xué)生，其中144名學(xué)生采用傳統(tǒng)的左右旋轉(zhuǎn)法進(jìn)行教學(xué)，150名學(xué)生采用本文提出的五步調(diào)整法進(jìn)行教學(xué)。

圖4中兩組學(xué)生的平衡二叉樹方面的考試成績（轉(zhuǎn)換為百分制）統(tǒng)計(jì)，將分?jǐn)?shù)分為五檔，來評估學(xué)生對知識的掌握程度。與傳統(tǒng)調(diào)整方法（左右旋轉(zhuǎn)）相比，本文方法能夠降低低分段人數(shù)并提高高分段人數(shù)。比如，在傳統(tǒng)方法下，不及格（低于60分）的比例占到55%，這也說明平衡二叉樹的失衡調(diào)整是一個(gè)學(xué)習(xí)難點(diǎn)，尤其是對基礎(chǔ)較薄弱的二本高校的學(xué)生。學(xué)生在掌握本文方法后，不及格率下降到40%，且高分段（80分以上）比例上升了12%。

圖5調(diào)查了學(xué)生掌握失衡調(diào)整所花費(fèi)的時(shí)間，調(diào)查對象為成績60分以上的學(xué)生。利用傳統(tǒng)掌握失衡調(diào)整方法，51%以上的學(xué)生需要花費(fèi)三個(gè)小時(shí)以上的時(shí)間才能夠掌握該知識。在本文方法下，81%的學(xué)生掌握失衡調(diào)整集中在三小時(shí)以內(nèi)，甚至有12%比例的學(xué)生能夠在45分鐘內(nèi)掌握。

綜上所述，本文的五步調(diào)整方法能夠降低學(xué)生的理解難度，減少學(xué)生的掌握時(shí)間，在一定程度上提高了學(xué)生的學(xué)習(xí)成績和學(xué)習(xí)效率。

4 結(jié)束語

為了降低平衡二叉樹中失衡調(diào)整的理解難度，本文提出一種五步調(diào)整方法來提高學(xué)生的學(xué)習(xí)效果。五步調(diào)整方法不再將失衡調(diào)整劃分為四類，而是歸為一類進(jìn)行統(tǒng)一處理，能夠顯著地縮短學(xué)生的掌握時(shí)間和提高學(xué)生的學(xué)習(xí)成績，取得了一定的教學(xué)效果。在五步調(diào)整方法基礎(chǔ)上，如何進(jìn)一步簡化處理流程仍然值得我們進(jìn)一步探討。

參考文獻(xiàn)（References）：

[1] 李春葆.數(shù)據(jù)結(jié)構(gòu)教程（第五版）[M].清華大學(xué)出版社，2017.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（第二版）[M].清華大學(xué)出版社，2008.

[3] 朱宇，張紅彬.平衡二叉樹的選擇調(diào)整算法[J].中國科學(xué)院研究生院學(xué)報(bào)，2006.4：98-104

[4] 張標(biāo)漢.平衡二叉樹調(diào)整教學(xué)探討[J].計(jì)算機(jī)教育，2009.10：53-54

[5] 朱洪浩.數(shù)據(jù)結(jié)構(gòu)中平衡二叉樹的教學(xué)探討與研究[J].赤峰學(xué)院學(xué)報(bào)（自然版），2012.5：19-21

[6] 陳海濤，李宗惠.平衡二叉樹的失衡調(diào)整方法探討[J].中國科教創(chuàng)新導(dǎo)刊，2010.34：146-146