基于旋轉(zhuǎn)的平衡二叉排序樹上插入的實現(xiàn)

曾祥師 王悅 雷甜甜

摘要：創(chuàng)建平衡二叉排序樹可采用不少種方法。對于教材中采用的旋轉(zhuǎn)法，在實際教學中常常引起初學者的疑惑。為了解決這個問題，該文提出了一種更為簡單的平衡二叉排序樹方法，與教材中的旋轉(zhuǎn)法相比，本算法簡單易被理解，有較大的推廣和應用價值。

關(guān)鍵詞：平衡二叉排序樹;平衡因子;二叉樹的平衡化

中圖分類號：TP3? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）17-0003-02

開放科學（資源服務）標識碼（OSID）：

Abstract： There are many methods for balanced binary tree sorting. For the teaching materials used in the rotation method， in practical teaching often caused confusion for beginners. In order to solve this problem， this paper proposes a more simple balanced binary sort tree method. Compared with the rotation method in the textbook， this algorithm is simple and easy to understand， and has great promotion and application value.

Key words： balanced binary sort tree; equilibrium factor; equilibrium of binary trees

現(xiàn)行的數(shù)據(jù)結(jié)構(gòu)教材中，創(chuàng)建平衡二叉排序樹方法是通過順時針、逆時針的旋轉(zhuǎn)把原非平衡的二叉樹變?yōu)槠胶舛鏄洹４朔N方法旋轉(zhuǎn)次數(shù)，旋轉(zhuǎn)方向因不同的問題而不同，雖然在理論上嚴謹，但對初學者來說理解起來頗為困難。針對這一問題，本文提出了一種更為簡單的平衡二叉排序樹方法，這種方法不需要進行旋轉(zhuǎn)平衡，更容易理解。不僅對于初學者，還是作為教學中的一種嘗試，都有著積極的意義。

1 基本原理

1.1 基本概念

1.1.1? 平衡二叉排序樹

平衡二叉排序樹的左、右子樹高度之差的絕對值不超過 1，并且左、右子樹都是平衡二叉排序樹。空樹也是平衡二叉排序樹。

1.1.2? 平衡因子

平衡因子是左子樹的高度減去右子樹的高度差也即深度差。因此，所有結(jié)點的均衡因子是-1，0，1的二叉樹，是平衡二叉排序樹。

1.1.3? 最小不平衡子樹

最小不平衡子樹是指具有以下屬性作為根的節(jié)點的子樹：最接近插入節(jié)點的祖先節(jié)點，并且平衡因子不是-1，0，1。

1.2 平衡調(diào)整算法

1.2.1 算法的基本思想

重新插入結(jié)點向根算平衡因子，將離新插入結(jié)點最近的不平衡結(jié)點標為A，順向新插入結(jié)點方向標注B，C調(diào)整，分以下4種情況（新插入結(jié)點相對于不平衡結(jié)點A的位置）

1.2.3 算法的正確性

調(diào)整為平衡二叉樹后，中序遍歷對關(guān)鍵字進行了有序排列，它可以維持二叉排序樹原有的性質(zhì)。與此同時，不管任何一種情況，在調(diào)整后，都能確保根的新子樹與原來的相同。因此，當平衡的二叉排序樹引入新的結(jié)點而失去平衡時，只需要平衡最小不平衡子樹。

1.2.4 算法的復雜度

假設平衡二叉數(shù)有n個結(jié)點，平衡二叉排序樹的n個結(jié)點的深度為[log2n]，插入結(jié)點時的數(shù)量級為n的對數(shù)階，故其時間復雜度為 O（[log2n]）。在尋找新結(jié)點的插入位置時，就能選擇尋找最小的不平衡子樹，故查找最小不平衡子樹的時間復雜度與插入結(jié)點的時間復雜度相等也為O（[log2n]）。

2 實例及其調(diào)整圖示

3結(jié)束語

該算法的源代碼程序已在Visual C++ 6.0運行成功。算法條理清晰，深受同學們喜愛，因此取得了較好的學習效果。二叉排序樹平衡化可采用的方法中，本方法有一定的優(yōu)勢。對它的準確掌握可以對后續(xù)的學習起到非常好的推動作用。由實踐可以表明，本文采用的簡單調(diào)整平衡算法要比教材中的旋轉(zhuǎn)法更易被接受。

參考文獻：

[1] 嚴蔚敏，李冬梅，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版第2版）[M].北京：人民郵電出版社，2014.

[2] 張標漢.平衡二叉樹調(diào)整教學探討[J].教育與教學研究，2009.

[3] 張冰川.平衡二叉排序樹的平衡調(diào)整簡單算法[J].科技廣場，2007.

【通聯(lián)編輯：代影】