基于拆分旋轉(zhuǎn)法的平衡二叉樹的構(gòu)建

楊金龍 李昕昕 龔勛

摘要：平衡二叉樹就是對(duì)二叉排序樹的一種改進(jìn)，是對(duì)二叉排序樹的平衡化之后的數(shù)據(jù)結(jié)構(gòu)。平衡二叉樹可以有效提高查找運(yùn)算的速度。但是傳統(tǒng)平衡二叉樹的構(gòu)建過程相對(duì)繁瑣，且對(duì)于某些特定問題無法解決。因此，該文提出了一種新的平衡二叉樹構(gòu)建方法——拆分旋轉(zhuǎn)法。實(shí)驗(yàn)證明，該方法切實(shí)可行，且針對(duì)有限序列的平衡二叉樹構(gòu)建過程明顯優(yōu)于傳統(tǒng)平衡二叉樹的構(gòu)建。

關(guān)鍵詞：拆分旋轉(zhuǎn)法；平衡因子；二叉排序樹；平衡二叉樹

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）29-0003-03

1 平衡二叉樹

1.1平衡二叉樹的特性

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

1.2傳統(tǒng)的構(gòu)建平衡二叉樹的方法

傳統(tǒng)的構(gòu)建平衡二叉樹的方法是在規(guī)定一個(gè)插入序列之后，通過序列構(gòu)建一棵平衡二叉樹時(shí)，其中有LL型，RR型，LR型以及RL型的調(diào)整操作方法。[2]

整個(gè)實(shí)現(xiàn)過程是通過在一棵平衡二叉樹中依次按照二叉排序樹的方式插入元素，若二叉樹出現(xiàn)不平衡狀態(tài)，則根據(jù)新插入的結(jié)點(diǎn)與平衡因子大于1的結(jié)點(diǎn)的位置關(guān)系進(jìn)行相應(yīng)的調(diào)整。其調(diào)整方法可分為LL型、RR型、LR型和RL型4種簡單調(diào)整，具體構(gòu)建過程如下：

1.2.1LL型調(diào)整

由于在A的左孩子（L）的左子樹（L）上插入新的結(jié)點(diǎn)C，使原來平衡二叉樹變?yōu)椴黄胶鉅顟B(tài)，此時(shí)A的平衡因子由1增加至2。下面圖1是LL型的最簡單調(diào)整形式。將A的左孩子B向右上方旋轉(zhuǎn)，使其代替A的位置成為根結(jié)點(diǎn)，再將A結(jié)點(diǎn)向右下方旋轉(zhuǎn)成為B的右子樹的根結(jié)點(diǎn)，C則成為B結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)。

1.2.2RR型調(diào)整

由于在A的右孩子（R）的左子樹（R）上插入新的結(jié)點(diǎn)C，使原來平衡二叉樹變?yōu)椴黄胶鉅顟B(tài)，此時(shí)A的平衡因子由-1變?yōu)?2。下面圖12是RR型的最簡單調(diào)整形式。將A的右孩子B向左上方旋轉(zhuǎn)，使其代替A的位置成為根結(jié)點(diǎn)，再將A結(jié)點(diǎn)向左下方旋轉(zhuǎn)成為B的左子樹的根結(jié)點(diǎn)，C則成為B結(jié)點(diǎn)的右子樹的根結(jié)點(diǎn)。

1.2.3LR型調(diào)整

由于在A的左孩子（L）的右子樹（R）上插入新的結(jié)點(diǎn)C，使原來平衡二叉樹變?yōu)椴黄胶鉅顟B(tài)，此時(shí)A的平衡因子由1增加至2。下面圖3是LR型的最簡單調(diào)整形式。此時(shí)的則需要進(jìn)行兩次旋轉(zhuǎn)，先左旋轉(zhuǎn)后再進(jìn)行右旋轉(zhuǎn)。先將A的左孩子B的右子樹的根結(jié)點(diǎn)C向左上方旋轉(zhuǎn)提升到B結(jié)點(diǎn)原來的位置，此時(shí)C成為A結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)，B則成為C的左子樹的根結(jié)點(diǎn)。第一次旋轉(zhuǎn)之后的狀態(tài)也是LL型旋轉(zhuǎn)時(shí)的不平衡狀，再進(jìn)行一次LL型調(diào)整則變?yōu)槠胶鉅顟B(tài)。

1.2.4RL型調(diào)整

由于在A的右孩子（R）的左子樹（L）上插入新的結(jié)點(diǎn)C，使原來平衡二叉樹變?yōu)椴黄胶鉅顟B(tài)，此時(shí)A的平衡因子由-1變?yōu)?2。下面圖4是RL型的最簡單調(diào)整形式。此時(shí)的則需要進(jìn)行兩次旋轉(zhuǎn)，先右旋轉(zhuǎn)后再進(jìn)行左旋轉(zhuǎn)。先將A的右孩子B的左子樹的根結(jié)點(diǎn)C向右上方旋轉(zhuǎn)提升到B結(jié)點(diǎn)原來的位置，此時(shí)C成為A結(jié)點(diǎn)的右子樹的根結(jié)點(diǎn)，B則成為C的右子樹的根結(jié)點(diǎn)。第一次旋轉(zhuǎn)之后的狀態(tài)也是RR型旋轉(zhuǎn)時(shí)的不平衡狀態(tài)，再進(jìn)行一次RR型調(diào)整則變?yōu)槠胶鉅顟B(tài)。

2 拆分旋轉(zhuǎn)方法

2.1拆分旋轉(zhuǎn)法的特點(diǎn)

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

2.2拆分旋轉(zhuǎn)法的設(shè)計(jì)思路

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

2.3 拆分旋轉(zhuǎn)法的算法實(shí)現(xiàn)

3 拆分旋轉(zhuǎn)法的應(yīng)用

下面將通過使用拆分旋轉(zhuǎn)法對(duì)關(guān)鍵字序列{1，2，3，4，5，6，7，8，9，10，11，12}進(jìn)行二叉樹構(gòu)建的過程為例來對(duì)拆分旋轉(zhuǎn)法的應(yīng)用進(jìn)行具體闡述：

（1）插入1，為根節(jié)點(diǎn)，平衡；插入2為1的右孩子，平衡；插入3為2的右孩子，此時(shí)不平衡，采用RR型調(diào)整方法后的二叉樹為：

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

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

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

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

（6）插入10，為9的右孩子，不平衡，此時(shí)導(dǎo)致結(jié)點(diǎn)關(guān)鍵字為6的平衡因?yàn)闉?2，情況同（3），也采用拆分旋轉(zhuǎn)方法對(duì)二叉樹平衡化，得到平衡二叉樹后插入11，為10的右孩子，不平衡，此時(shí)同（4）的情況一致，采用同樣方法調(diào)整為8的右子樹根節(jié)點(diǎn)為10，10的左孩子為9，右孩子為11，平衡。此時(shí)二叉樹為：

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

4 結(jié)論

本文針對(duì)傳統(tǒng)的平衡二叉樹構(gòu)建過程中存在的對(duì)于插入結(jié)點(diǎn)只造成根節(jié)點(diǎn)的平衡因子不平衡而無法構(gòu)建的問題和插入結(jié)點(diǎn)過多而無法構(gòu)建的問題進(jìn)行了詳細(xì)討論，并給出了解決方案，即平衡二叉樹的拆分旋轉(zhuǎn)構(gòu)建法。實(shí)驗(yàn)證明，該方法對(duì)于有限序列甚至一些特殊序列構(gòu)建平衡二叉樹非常適用。

參考文獻(xiàn)：

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

[2]嚴(yán)蔚敏， 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C 語言版）[M]. 北京：清華大學(xué)出版社， 1997.233-238.

[3]朱宇， 張紅彬. 平衡二叉樹的選擇調(diào)整算法.中國科學(xué)院研究生院，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.

【通聯(lián)編輯：王力】