曾祥師 王悅 雷甜甜

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

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

中圖分類(lèi)號(hào)：TP3? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）17-0003-02

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

1 基本原理

1.1 基本概念

1.1.1? 平衡二叉排序樹(shù)

平衡二叉排序樹(shù)的左、右子樹(shù)高度之差的絕對(duì)值不超過(guò) 1，并且左、右子樹(shù)都是平衡二叉排序樹(shù)?？諛?shù)也是平衡二叉排序樹(shù)。

1.1.2? 平衡因子

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

1.1.3? 最小不平衡子樹(shù)

最小不平衡子樹(shù)是指具有以下屬性作為根的節(jié)點(diǎn)的子樹(shù)：最接近插入節(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)相對(duì)于不平衡結(jié)點(diǎn)A的位置）

1.2.3 算法的正確性

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

1.2.4 算法的復(fù)雜度

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

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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