曾祥師 王悅 雷甜甜

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

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

中圖分類號：TP3? ? ? ? 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（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)槠胶舛鏄?。此種方法旋轉(zhuǎn)次數(shù)，旋轉(zhuǎn)方向因不同的問題而不同，雖然在理論上嚴(yán)謹(jǐn)，但對初學(xué)者來說理解起來頗為困難。針對這一問題，本文提出了一種更為簡單的平衡二叉排序樹方法，這種方法不需要進(jìn)行旋轉(zhuǎn)平衡，更容易理解。不僅對于初學(xué)者，還是作為教學(xué)中的一種嘗試，都有著積極的意義。

1 基本原理

1.1 基本概念

1.1.1? 平衡二叉排序樹

平衡二叉排序樹的左、右子樹高度之差的絕對值不超過 1，并且左、右子樹都是平衡二叉排序樹?？諛湟彩瞧胶舛媾判驑?。

1.1.2? 平衡因子

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

1.1.3? 最小不平衡子樹

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

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

1.2.1 算法的基本思想

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

1.2.3 算法的正確性

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

1.2.4 算法的復(fù)雜度

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

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

3結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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