平衡二叉樹的五步失衡調(diào)整方法探索

劉慧 張兆維

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

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

中圖分類號：G642? ? ? ? ? 文獻標識碼：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]中的核心概念，二叉樹在學生考研或工作中處于重要的地位，其中，平衡二叉樹的失衡調(diào)整又是重重之重，引起了教學的廣泛關注和研究。平衡二叉樹是決定搜索性能的關鍵因素，一旦失衡，其搜索性能有可能會退化為線性表。失衡調(diào)整是將失去平衡的二叉樹通過某種調(diào)整而成為一棵平衡二叉樹，具有種類多樣（“LL”、“RR”、“LR”和“RL”等四種）、操作繁瑣（左旋轉(zhuǎn)、右旋轉(zhuǎn)、先左后右旋轉(zhuǎn)和先右后左旋轉(zhuǎn)等）、處理分散、容易混淆的特點，加大了學生的理解難度。

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

1 面臨的問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 教學效果

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

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

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

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

4 結(jié)束語

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

參考文獻（References）：

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

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

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

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

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

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