基于旋轉的平衡二叉排序樹上插入的實現

曾祥師 王悅 雷甜甜

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

關鍵詞：平衡二叉排序樹;平衡因子;二叉樹的平衡化

中圖分類號：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

現行的數據結構教材中，創建平衡二叉排序樹方法是通過順時針、逆時針的旋轉把原非平衡的二叉樹變為平衡二叉樹。此種方法旋轉次數，旋轉方向因不同的問題而不同，雖然在理論上嚴謹，但對初學者來說理解起來頗為困難。針對這一問題，本文提出了一種更為簡單的平衡二叉排序樹方法，這種方法不需要進行旋轉平衡，更容易理解。不僅對于初學者，還是作為教學中的一種嘗試，都有著積極的意義。

1 基本原理

1.1 基本概念

1.1.1? 平衡二叉排序樹

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

1.1.2? 平衡因子

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

1.1.3? 最小不平衡子樹

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

1.2 平衡調整算法

1.2.1 算法的基本思想

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

1.2.3 算法的正確性

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

1.2.4 算法的復雜度

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

2 實例及其調整圖示

3結束語

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

參考文獻：

[1] 嚴蔚敏，李冬梅，吳偉民. 數據結構（C語言版第2版）[M].北京：人民郵電出版社，2014.

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

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

【通聯編輯：代影】