基于拆分旋轉法的平衡二叉樹的構建

楊金龍 李昕昕 龔勛

摘要：平衡二叉樹就是對二叉排序樹的一種改進，是對二叉排序樹的平衡化之后的數據結構。平衡二叉樹可以有效提高查找運算的速度。但是傳統平衡二叉樹的構建過程相對繁瑣，且對于某些特定問題無法解決。因此，該文提出了一種新的平衡二叉樹構建方法——拆分旋轉法。實驗證明，該方法切實可行，且針對有限序列的平衡二叉樹構建過程明顯優于傳統平衡二叉樹的構建。

關鍵詞：拆分旋轉法；平衡因子；二叉排序樹；平衡二叉樹

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）29-0003-03

1 平衡二叉樹

1.1平衡二叉樹的特性

在計算機科學中，二叉樹（Binary tree）是每個節點最多只有兩個分支（即不存在分支度大于2的節點）的樹結構，常用于高效率的搜索和排序。平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），它除了具備二叉查找樹的基本特征之外，還具有一個非常重要的特點：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值（平衡因子 ） 不超過1。[1]平衡二叉查找樹可用于表示有序的線性數據結構，如優先隊列、關聯數組、鍵-值的映射等。

1.2傳統的構建平衡二叉樹的方法

傳統的構建平衡二叉樹的方法是在規定一個插入序列之后，通過序列構建一棵平衡二叉樹時，其中有LL型，RR型，LR型以及RL型的調整操作方法。[2]

整個實現過程是通過在一棵平衡二叉樹中依次按照二叉排序樹的方式插入元素，若二叉樹出現不平衡狀態，則根據新插入的結點與平衡因子大于1的結點的位置關系進行相應的調整。其調整方法可分為LL型、RR型、LR型和RL型4種簡單調整，具體構建過程如下：

1.2.1LL型調整

由于在A的左孩子（L）的左子樹（L）上插入新的結點C，使原來平衡二叉樹變為不平衡狀態，此時A的平衡因子由1增加至2。下面圖1是LL型的最簡單調整形式。將A的左孩子B向右上方旋轉，使其代替A的位置成為根結點，再將A結點向右下方旋轉成為B的右子樹的根結點，C則成為B結點的左子樹的根結點。

1.2.2RR型調整

由于在A的右孩子（R）的左子樹（R）上插入新的結點C，使原來平衡二叉樹變為不平衡狀態，此時A的平衡因子由-1變為-2。下面圖12是RR型的最簡單調整形式。將A的右孩子B向左上方旋轉，使其代替A的位置成為根結點，再將A結點向左下方旋轉成為B的左子樹的根結點，C則成為B結點的右子樹的根結點。

1.2.3LR型調整

由于在A的左孩子（L）的右子樹（R）上插入新的結點C，使原來平衡二叉樹變為不平衡狀態，此時A的平衡因子由1增加至2。下面圖3是LR型的最簡單調整形式。此時的則需要進行兩次旋轉，先左旋轉后再進行右旋轉。先將A的左孩子B的右子樹的根結點C向左上方旋轉提升到B結點原來的位置，此時C成為A結點的左子樹的根結點，B則成為C的左子樹的根結點。第一次旋轉之后的狀態也是LL型旋轉時的不平衡狀，再進行一次LL型調整則變為平衡狀態。

1.2.4RL型調整

由于在A的右孩子（R）的左子樹（L）上插入新的結點C，使原來平衡二叉樹變為不平衡狀態，此時A的平衡因子由-1變為-2。下面圖4是RL型的最簡單調整形式。此時的則需要進行兩次旋轉，先右旋轉后再進行左旋轉。先將A的右孩子B的左子樹的根結點C向右上方旋轉提升到B結點原來的位置，此時C成為A結點的右子樹的根結點，B則成為C的右子樹的根結點。第一次旋轉之后的狀態也是RR型旋轉時的不平衡狀態，再進行一次RR型調整則變為平衡狀態。

2 拆分旋轉方法

2.1拆分旋轉法的特點

研究發現，上述方法對于二叉樹非根節點的平衡因子不平衡的狀態調整適用，但對于插入結點只造成根節點的平衡因子不平衡的情況和插入結點過多的情況不適用。例如，對序列{1，2，3，4，5，6，7}構建平衡二叉樹時，插入數字6時，只造成了根節點的平衡因子不平衡，而上述四種旋轉方法都無法高效的進行解決。因此，本文提出了一種新的構建平衡二叉樹的方法——拆分旋轉法。該方法的特點是：在調整的同時，一部分結點不會參與平衡化，只有其中造成不平衡的相關結點會進行調整，并且相關結點調整方法可以直接采用遞歸方法進行平衡化，這種方法使用時，參與調整的結點會比傳統調整方法中參與的結點更少，算法實現起來更加簡單，這樣的調整方法使算法的時間復雜度也相應減小。

2.2拆分旋轉法的設計思路

當插入結點過多時，一般認為插入結點后二叉樹深度大于等于4時，插入結點引起了二叉樹的不平衡，則把插入結點到平衡因子絕對值大于等于2的結點（M結點）的路徑與其他結點拆分為多個部分，再選擇平衡因子絕對值大于等于2的結點到插入結點路徑上的前三個結點（M，B，C），其它與這三個結點拆分開的每個部分都分別當做一個整體（E1、E2、E3......）。這三個結點必然形成LL型、RR型、LR型或者RL型的不平衡狀態，然后對這三個結點進行平衡化，再把拆分開的結點整體部分（E1、E2、E3......）按照二叉排序樹的插入方法插入到M，B，C三個結點平衡化之后的結構上，最終形成一棵平衡二叉樹。

2.3 拆分旋轉法的算法實現

3 拆分旋轉法的應用

下面將通過使用拆分旋轉法對關鍵字序列{1，2，3，4，5，6，7，8，9，10，11，12}進行二叉樹構建的過程為例來對拆分旋轉法的應用進行具體闡述：

（1）插入1，為根節點，平衡；插入2為1的右孩子，平衡；插入3為2的右孩子，此時不平衡，采用RR型調整方法后的二叉樹為：

（2）插入4，為3的右孩子，平衡，插入5為4的右孩子，不平衡，由于插入5之后導致3的平衡因子為-2，同樣屬于RR型，所以采用RR型調整方法后的二叉樹為：

（3）插入6，為5的右孩子，不平衡，導致根節點2的平衡因子為-2，此時采用拆分旋轉方法。選取2，4，5為RR型，1，3，6為其他三個整體部分；2，4，5調整為層次遍歷4，2，5；再把其他三個整體部分按照二叉排序樹的方法插入即可，此時二叉樹為：

（4）插入7，為6的右孩子，不平衡，此時造成5的平衡因子為-2，所以只需采用RR型調整方法此時二叉樹為：

（5）插入8，為7的右孩子，平衡；插入9為8的右孩子，不平衡，與（4）的情況一致，采用同樣方法調整為6的右子樹的層次遍歷為8，7，9，平衡；此時二叉樹為：

（6）插入10，為9的右孩子，不平衡，此時導致結點關鍵字為6的平衡因為為-2，情況同（3），也采用拆分旋轉方法對二叉樹平衡化，得到平衡二叉樹后插入11，為10的右孩子，不平衡，此時同（4）的情況一致，采用同樣方法調整為8的右子樹根節點為10，10的左孩子為9，右孩子為11，平衡。此時二叉樹為：

（7）插入12，位11的右孩子，不平衡，此時二叉樹根節點4的平衡因子為-2，采用拆分旋轉方法，把4，8，10三個結點看作RR型部分，4的左子樹看作一個部分（E1），8的左子樹看作一個部分（E2），10的左子樹看作一個部分（E3），10的右子樹看作一個部分（E4），此時RR型部分旋轉調整為根為8，左孩子為4，右孩子為10的二叉樹，再把E1、E2、E3、E4四個部分按照二叉排序樹的方法插入到RR型部分調整后的二叉樹上，此時平衡二叉樹為：

4 結論

本文針對傳統的平衡二叉樹構建過程中存在的對于插入結點只造成根節點的平衡因子不平衡而無法構建的問題和插入結點過多而無法構建的問題進行了詳細討論，并給出了解決方案，即平衡二叉樹的拆分旋轉構建法。實驗證明，該方法對于有限序列甚至一些特殊序列構建平衡二叉樹非常適用。

參考文獻：

[1]朱洪浩. 數據結構中平衡二叉樹的教學探討與研究[J]. 赤峰學院學報（自然科學版），2012，28（5）：19-21.

[2]嚴蔚敏， 吳偉民. 數據結構（C 語言版）[M]. 北京：清華大學出版社， 1997.233-238.

[3]朱宇， 張紅彬. 平衡二叉樹的選擇調整算法.中國科學院研究生院，2006， 23（4）：527-533

[4]William Ford， William Topt. Data Structures with C++.Beijing：Tsinghua University Press，1997.721-728

[5]Clifford A，Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis （C++ Edition）（2nd ed.）.Beijing ：Publishing House ofElectroni cs Industry， 2002.280.

【通聯編輯：王力】