Python實(shí)現(xiàn)二叉排序樹與平衡二叉樹的示例代碼

更新時間：2022年04月28日 10:05:12 作者：一枚大果殼

樹表查詢即借助具有特殊性質(zhì)的樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行關(guān)鍵字查找，本文所涉及到的特殊結(jié)構(gòu)性質(zhì)的樹包括：二叉排序樹、平衡二叉樹。文中詳細(xì)介紹了二者的實(shí)現(xiàn)代碼，需要的可以參考一下

前言

什么是樹表查詢？

借助具有特殊性質(zhì)的樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行關(guān)鍵字查找。

本文所涉及到的特殊結(jié)構(gòu)性質(zhì)的樹包括：

二叉排序樹。
平衡二叉樹。

使用上述樹結(jié)構(gòu)存儲數(shù)據(jù)時，因其本身對結(jié)點(diǎn)之間的關(guān)系以及順序有特殊要求，也得益于這種限制，在查詢某一個結(jié)點(diǎn)時會帶來性能上的優(yōu)勢和操作上的方便。

樹表查詢屬于動態(tài)查找算法。

所謂動態(tài)查找，不僅僅能很方便查詢到目標(biāo)結(jié)點(diǎn)。而且可以根據(jù)需要添加、刪除結(jié)點(diǎn)，而不影響樹的整體結(jié)構(gòu)，也不會影響數(shù)據(jù)的查詢。

本文并不會深入講解樹數(shù)據(jù)結(jié)構(gòu)的基本的概念，僅是站在使用的角度說清楚動態(tài)查詢。閱讀此文之前，請預(yù)備一些樹的基礎(chǔ)知識。

1. 二叉排序樹

二叉樹是樹結(jié)構(gòu)中具有艷明特點(diǎn)的子類。

二叉樹要求樹的每一個結(jié)點(diǎn)（除葉結(jié)點(diǎn)）的子結(jié)點(diǎn)最多只能有 2 個。在二叉樹的基礎(chǔ)上，繼續(xù)對其進(jìn)行有序限制則變成二叉排序樹。

二叉排序樹特點(diǎn)：

基于二叉樹結(jié)構(gòu)，從根結(jié)點(diǎn)開始，從上向下，每一個父結(jié)點(diǎn)的值大于左子結(jié)點(diǎn)（如果存在左子結(jié)點(diǎn)）的值，而小于右子結(jié)點(diǎn)（如果存在右子結(jié)點(diǎn)）的值。則把符合這種特征要求的樹稱為二叉排序樹。

1.1 構(gòu)建一棵二叉排序樹

如有數(shù)列 nums=[5,12,4,45,32,8,10,50,32,3]。通過下面流程，把每一個數(shù)字映射到二叉排序樹的結(jié)點(diǎn)上。

1.如果樹為空，把第一個數(shù)字作為根結(jié)點(diǎn)。如下圖，數(shù)字 5 作為根結(jié)點(diǎn)。

2.如果已經(jīng)存在根結(jié)點(diǎn)，則把數(shù)字和根結(jié)點(diǎn)比較，小于根結(jié)點(diǎn)則作為根結(jié)點(diǎn)的左子結(jié)點(diǎn)，大于根結(jié)點(diǎn)的作為根結(jié)點(diǎn)的右子結(jié)點(diǎn)。如數(shù)字 4 插入到左邊，數(shù)字 12 插入到右邊。

3.數(shù)列中后面的數(shù)字依據(jù)相同法則，分別插入到不同子的位置。

原始數(shù)列中的數(shù)字是無序的，根據(jù)二叉排序樹的插入算法，最終可得到一棵有排序性質(zhì)的樹結(jié)構(gòu)。對此棵樹進(jìn)行中序遍歷就可得到從小到大的一個遞增有序數(shù)列。

綜觀二叉排序樹，進(jìn)行關(guān)鍵字查找時，也應(yīng)該是接近于二分查找算法的時間度。

這里有一個要注意的地方。

原始數(shù)列中的數(shù)字順序不一樣時，生成的二叉排序樹的結(jié)構(gòu)也會有差異性。對于查找算法的性能會產(chǎn)生影響。

1.2 二叉排序樹的數(shù)據(jù)結(jié)構(gòu)

現(xiàn)在使用OOP設(shè)計方案描述二叉排序樹的數(shù)據(jù)結(jié)構(gòu)。

首先，設(shè)計一個結(jié)點(diǎn)類，用來描述結(jié)點(diǎn)本身的信息。

'''
二叉排序樹的結(jié)點(diǎn)類
'''
class TreeNode():
    def __init__(self, value):
        # 結(jié)點(diǎn)上的值
        self.value = value
        # 左結(jié)點(diǎn)
        self.l_child = None
        # 右結(jié)點(diǎn)
        self.r_child = None

結(jié)點(diǎn)類中有 3 個屬性：

value：結(jié)點(diǎn)上附加的數(shù)據(jù)信息。
l_child：左子結(jié)點(diǎn)，初始值為 None 。
r_child：右子結(jié)點(diǎn)，初始值為 None。

二叉排序樹類： 用來實(shí)現(xiàn)樹的增、刪、改、查。

'''
二叉排序樹類
'''
class BinarySortTree:
    # 初始化樹
    def __init__(self, value=None):
        pass
    
    '''
    在整棵樹上查詢是否存在給定的關(guān)鍵字
    '''
    def find(self, key):
        pass
    
    '''
    使用遞歸進(jìn)行查詢
    '''
    def find_dg(self, root, key):
        pass

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        pass

     '''
    中序遍歷
    '''
    def inorder_traversal(self):
        pass
    '''
    刪除結(jié)點(diǎn)
    '''
    def delete(self, key):
        pass

    '''
    檢查是不是空樹
    '''
    def is_empty(self):
        return self.root == None

二叉排序樹中可以有更多方法，本文只關(guān)注與查找主題有關(guān)的方法。

1.3 實(shí)現(xiàn)二叉排序樹類中的方法：

__init__ 初始化方法：

    # 初始化樹
    def __init__(self, value=None):
        self.root = None
        if value is not None:
            root_node = TreeNode(value)
            self.root = root_node

在初始化樹對象時，如果指定了數(shù)據(jù)信息，則創(chuàng)建有唯一結(jié)點(diǎn)的樹，否則創(chuàng)建一個空樹。

關(guān)鍵字查詢方法：查詢給定的關(guān)鍵字在二叉排序樹結(jié)構(gòu)中是否存在。

查詢流程：

把給定的關(guān)鍵字和根結(jié)點(diǎn)相比較。如果相等，則返回查找成功，結(jié)束查詢.
如果根結(jié)點(diǎn)的值大于關(guān)鍵字，則繼續(xù)進(jìn)入根結(jié)點(diǎn)的左子樹中開始查找。
如果根結(jié)點(diǎn)的值小于關(guān)鍵字，則進(jìn)入根結(jié)點(diǎn)的右子樹中開始查找。
如果沒有查詢到關(guān)鍵字，則返回最后訪問過的結(jié)點(diǎn)和查詢不成功信息。

關(guān)鍵字查詢的本質(zhì)是二分思想，以當(dāng)前結(jié)點(diǎn)為分界線，然后向左或向右進(jìn)行分枝查找。

非遞歸實(shí)現(xiàn)查詢方法：

    '''
    在整棵樹上查詢是否存在給定的關(guān)鍵字
    key: 給定的關(guān)鍵字
    '''
    def find(self, key):
        # 從根結(jié)點(diǎn)開始查找。
        move_node = self.root
        # 用來保存最后訪問過的結(jié)點(diǎn)
        last_node = None
        while move_node is not None:
            # 保存當(dāng)前結(jié)點(diǎn)
            last_node = move_node
            # 把關(guān)鍵字和當(dāng)前結(jié)點(diǎn)相比較
            if self.root.value == key:
                # 出口一：成功查找
                return move_node
            elif move_node.value > key:
                # 在左結(jié)點(diǎn)查找
                move_node = move_node.l_child
            else:
                # 在右結(jié)點(diǎn)中查找
                move_node = move_node.r_child
        # 出口二：如果沒有查詢到，則返回最后訪問過的結(jié)點(diǎn)及None（None 表示沒查詢到）
        return last_node, None

注意：當(dāng)沒有查詢到時，返回的值有 2 個，最后訪問的結(jié)點(diǎn)和沒有查詢到的信息。

為什么要返回最后一次訪問過的結(jié)點(diǎn)？

反過來想想，本來應(yīng)該在這個地方找到，但是沒有，如果改成插入操作，就應(yīng)該插入到此位置。

基于遞歸實(shí)現(xiàn)的查找：

    '''
    使用遞歸進(jìn)行查詢
    '''
    def find_dg(self, root, key):
        # 結(jié)點(diǎn)不存在
        if root is None:
            return None
        # 相等
        if root.value == key:
            return root
        if root.value > key:
            return self.find_dg(root.l_child, key)
        else:
            return self.find_dg(root.r_child, key)

再看看如何把數(shù)字插入到二叉排序樹中，利用二叉排序樹進(jìn)行查找的前提條件就是要把數(shù)字映射到二叉排序樹的結(jié)點(diǎn)上。

插入結(jié)點(diǎn)的流程：

當(dāng)需要插入某一個結(jié)點(diǎn)時，先搜索是否已經(jīng)存在于樹結(jié)構(gòu)中。
如果沒有，則獲取到查詢時訪問過的最一個結(jié)點(diǎn)，并和此結(jié)點(diǎn)比較大小。
如果比此結(jié)點(diǎn)大，則插入最后訪問過結(jié)點(diǎn)的右子樹位置。
如果比此結(jié)點(diǎn)小，則插入最后訪問過結(jié)點(diǎn)的左子樹位置。

insert 方法的實(shí)現(xiàn)：

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        # 查詢是否存在此結(jié)點(diǎn)
        res = self.find(value)
        if type(res) != TreeNode:
            # 沒找到，獲取查詢時最后訪問過的結(jié)點(diǎn)
            last_node = res[0]
            # 創(chuàng)建新結(jié)點(diǎn)
            new_node = TreeNode(value)
            # 最后訪問的結(jié)點(diǎn)是根結(jié)點(diǎn)
            if last_node is None:
                self.root = new_node
            if value > last_node.value:
                last_node.r_child = new_node
            else:
                last_node.l_child = new_node

怎么檢查插入的結(jié)點(diǎn)是符合二叉樹特征？

再看一下前面根據(jù)插入原則手工繪制的插入演示圖：

上圖有 4 個子結(jié)點(diǎn)，寫幾行代碼測試一下，看從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的順序是否正確。

測試插入方法：

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    print("測試根5 -> 左4 ->左3:")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.l_child
    print("\n測試根5 -> 右12 ->右45->右50：")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.r_child
    '''
    輸出結(jié)果：
    測試根5 -> 左4 ->左3:
	5 ->4 ->3 ->
	測試根5 -> 右12 ->右45->右50：
	5 ->12 ->45 ->50 ->	
    '''

查看結(jié)果，可以初步判斷插入的數(shù)據(jù)是符合二叉排序樹特征的。當(dāng)然，更科學(xué)的方式是寫一個遍歷方法。樹的遍歷方式有 3 種：

前序：根，左，右。
中序：左，根，右。
后序。左，右，根。

對二叉排序樹進(jìn)行中序遍歷，理論上輸出的數(shù)字應(yīng)該是有序的。這里寫一個中序遍歷，查看輸出的結(jié)點(diǎn)是不是有序的，從而驗證查詢和插入方法的正確性。

使用遞歸實(shí)現(xiàn)中序遍歷：

    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        if root is None:
            return
        self.inorder_traversal(root.l_child)
        print(root.value,end="->")
        self.inorder_traversal(root.r_child)

測試插入的順序：

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    # res = tree.find(51)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    tree.inorder_traversal(tree.root)
   '''
   輸出結(jié)果
   3->4->5->8->10->12->32->45->50->
   '''

二叉排序樹很有特色的數(shù)據(jù)結(jié)構(gòu)，利用其存儲特性，可以很方便地進(jìn)行查找、排序。并且隨時可添加、刪除結(jié)點(diǎn)，而不會影響排序和查找操作?；跇浔淼牟樵儾僮鞣Q為動態(tài)查找。

二叉排序樹中如何刪除結(jié)點(diǎn)

從二叉樹中刪除結(jié)點(diǎn)，需要保證整棵二叉排序樹的有序性依然存在。刪除操作比插入操作要復(fù)雜，下面分別討論。

如果要刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)。

只需要把要刪除結(jié)點(diǎn)的父結(jié)點(diǎn)的左結(jié)點(diǎn)或右結(jié)點(diǎn)的引用值設(shè)置為空就可以了。

刪除的結(jié)點(diǎn)只有一個右子結(jié)點(diǎn)。如下圖刪除結(jié)點(diǎn) 8。

因為結(jié)點(diǎn)8沒有左子樹，在刪除之后，只需要把它的右子結(jié)點(diǎn)替換刪除結(jié)點(diǎn)就可以了。

刪除的結(jié)點(diǎn)即存在左子結(jié)點(diǎn)，如下圖刪除值為 25 的結(jié)點(diǎn)。

一種方案是：找到結(jié)點(diǎn) 25 的左子樹中的最大值，即結(jié)點(diǎn) 20（該結(jié)點(diǎn)的特點(diǎn)是可能會存在左子結(jié)點(diǎn)，但一定不會有右子結(jié)點(diǎn)）。用此結(jié)點(diǎn)替換結(jié)點(diǎn)25 便可。

為什么要這么做？

道理很簡單，既然是左子樹中的最大值，替換刪除結(jié)點(diǎn)后，整個二叉排序樹的特性可以繼續(xù)保持。

如果結(jié)點(diǎn) 20 存在左子結(jié)點(diǎn)，則把它的左子結(jié)點(diǎn)作為結(jié)點(diǎn)18的右子結(jié)點(diǎn)。

另一種方案：同樣找到結(jié)點(diǎn)25中左子樹中的最大值結(jié)點(diǎn) 20，然后把結(jié)點(diǎn) 25 的右子樹作為結(jié)點(diǎn) 20 的右子樹。

再把結(jié)點(diǎn) 25 的左子樹移到 25 位置。

這種方案會讓樹增加樹的深度。所以，建議使用第一種方案。

刪除方法的實(shí)現(xiàn)：

 	'''
    刪除結(jié)點(diǎn)
    key 為要要刪除的結(jié)點(diǎn)
    '''
    def delete(self, key):
        # 從根結(jié)點(diǎn)開始查找，move_node 為搜索指針
        move_node = self.root
        # 要刪除的結(jié)點(diǎn)的父結(jié)點(diǎn),因為根結(jié)點(diǎn)沒有父結(jié)點(diǎn)，初始值為 None
        parent_node = None
        # 結(jié)點(diǎn)存在且沒有匹配上要找的關(guān)鍵字
        while move_node is not None and move_node.value != key:
            # 保證當(dāng)前結(jié)點(diǎn)
            parent_node = move_node
            if move_node.value > key:
                # 在左子樹中繼續(xù)查找
                move_node = move_node.l_child
            else:
                # 在右子樹中繼續(xù)查找
                move_node = move_node.r_child
        # 如果不存在
        if move_node is None:
            return -1
        # 檢查要刪除的結(jié)點(diǎn)是否存在左子結(jié)點(diǎn)
        if move_node.l_child is None:
            if parent_node is None:
                # 如果要刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)
                self.root = move_node.r_child
            elif parent_node.l_child == move_node:
                # 刪除結(jié)點(diǎn)的右結(jié)點(diǎn)作為父結(jié)點(diǎn)的左結(jié)點(diǎn)
                parent_node.l_child = move_node.r_child
            elif parent_node.r_child == move_node:
                parent_node.r_child = move_node.r_child
            return 1
        else:
            # 如果刪除的結(jié)點(diǎn)存在左子結(jié)點(diǎn),則在左子樹中查找最大值
            s = move_node.l_child
            q = move_node
            while s.r_child is not None:
                q = s
                s = s.r_child
            if q == move_node:
                move_node.l_child = s.l_child
            else:
                q.r_child = s.l_child
            move_node.value = s.value
            q.r_child = None
            return 1

測試刪除后的二叉樹是否依然維持其有序性。

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    # res = tree.find(51)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    tree.delete(12)
    tree.inorder_traversal(tree.root)
    '''
    輸出結(jié)果
    3->4->5->8->10->32->45->50->
    '''

無論刪除哪一個結(jié)點(diǎn)，其二叉排序樹的中序遍歷結(jié)果都是有序的，很好地印證了刪除算法的正確性。

2. 平衡二叉排序樹

二叉排序樹中進(jìn)行查找時，其時間復(fù)雜度理論上接近二分算法的時間復(fù)雜度，其查找時間與樹的深度有關(guān)。但是，這里有一個問題，前面討論過，如果數(shù)列中的數(shù)字順序不一樣時，所構(gòu)建出來的二叉排序樹的深度會有差異性，對最后評估時間性能也會有影響。

如有數(shù)列 [36,45,67,28,20,40]構(gòu)建的二叉排序樹如下圖：

基于上面的樹結(jié)構(gòu)，查詢?nèi)魏我粋€結(jié)點(diǎn)的次數(shù)不會超過 3 次。

稍調(diào)整一下數(shù)列中數(shù)字的順序 [20,28,36,40,45,67]，由此構(gòu)建出來的樹結(jié)構(gòu)會出現(xiàn)一邊倒的現(xiàn)象，也增加了樹的深度。

此棵樹的深度為6，最多查詢次數(shù)是 6 次。在二叉排序樹中，減少查找次數(shù)的最好辦法，就是盡可能維護(hù)樹左右子樹之間的對稱性，也就讓其有平衡性。

所謂平衡二叉排序樹，顧名思義，基于二叉排序樹的基礎(chǔ)之上，維護(hù)任一結(jié)點(diǎn)的左子樹和右子樹之間的深度之差不超過 1。把二叉樹上任一結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為該結(jié)點(diǎn)的平衡因子。

平衡因子只可能是:

0 ：左、右子樹深度一樣。
1：左子樹深度大于右子樹。
-1：左子樹深度小于右子樹。

如下圖，就是平衡二叉排序樹，根結(jié)點(diǎn)的 2 個子樹深度相差為 0，結(jié)點(diǎn) 28 的左、右子樹深度為 1，結(jié)點(diǎn) 45 的左右子樹深度相差為 0。

平衡二叉排序樹相比較于二叉排序樹，其 API 多了保持平衡的算法。

2.1 二叉平衡排序樹的數(shù)據(jù)結(jié)構(gòu)

結(jié)點(diǎn)類：

'''
結(jié)點(diǎn)類
'''
class TreeNode:
    def __init__(self,value):
        self.value=value
        self.l_child=None
        self.r_child=None
        self.balance=0

結(jié)點(diǎn)類中有 4 個屬性：

value：結(jié)點(diǎn)上附加的值。
l_child：左子結(jié)點(diǎn)。
r_child：右子結(jié)點(diǎn)。
balance：平衡因子，默認(rèn)平衡因子為 0。

二叉平衡排序樹類：

'''
樹類
'''
class Tree:
    def __init__(self, value):
        self.root = None

    '''
    LL型調(diào)整
    '''
    def ll_rotate(self, node):
        pass

    '''
    RR 型調(diào)整
    '''
    def rr_rotate(self, node):
        pass

    '''
    LR型調(diào)整
    '''
    def lr_rotate(self, node):
        pass

    '''
    RL型調(diào)整
    '''
    def rl_rotate(self, node):
        pass

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        pass
    
    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        pass

    def is_empty(self):
        pass

在插入或刪除結(jié)點(diǎn)時，如果導(dǎo)致樹結(jié)構(gòu)發(fā)生了不平衡性，則需要調(diào)整讓其達(dá)到平衡。這里的方案可以有 4種。

LL型調(diào)整（順時針）：左邊不平衡時，向右邊旋轉(zhuǎn)。

如上圖，現(xiàn)在根結(jié)點(diǎn) 36 的平衡因子為 1。如果現(xiàn)插入值為 18 結(jié)點(diǎn)，顯然要作為結(jié)點(diǎn) 20 的左子結(jié)點(diǎn)，才符合二叉排序樹的有序性。但是破壞了根結(jié)點(diǎn)的平衡性。根結(jié)點(diǎn)的左子樹深度變成 3，右子樹深度為1，平衡被打破，結(jié)點(diǎn) 36 的平衡因子變成了2。

這里可以使用順時針旋轉(zhuǎn)方式，讓其繼續(xù)保持平衡，旋轉(zhuǎn)流程：

讓結(jié)點(diǎn) 28 成為新根結(jié)點(diǎn)，結(jié)點(diǎn)36成為結(jié)點(diǎn)28的左子結(jié)點(diǎn)。
結(jié)點(diǎn)29成為結(jié)點(diǎn)36的新左子結(jié)點(diǎn)。

旋轉(zhuǎn)后，樹結(jié)構(gòu)即滿足了有序性，也滿足了平衡性。

LL 旋轉(zhuǎn)算法具體實(shí)現(xiàn)：

    '''
    LL型調(diào)整
    順時針對調(diào)整
    '''
    def ll_rotate(self, p_root):
        # 原父結(jié)點(diǎn)的左子結(jié)點(diǎn)成為新父結(jié)點(diǎn)
        new_p_root = p_root.l_child
        # 新父結(jié)點(diǎn)的右子結(jié)點(diǎn)成為原父結(jié)點(diǎn)的左子結(jié)點(diǎn)
        p_root.l_child = new_p_root.r_child
        # 原父結(jié)點(diǎn)成為新父結(jié)點(diǎn)的右子結(jié)點(diǎn)
        new_p_root.r_child = p_root
        # 重置平衡因子
        p_root.balance = 0
        new_p_root.balance = 0
        return new_p_root

RR 型調(diào)整(逆時針旋轉(zhuǎn))：RR旋轉(zhuǎn)和 LL旋轉(zhuǎn)的算法差不多，只是當(dāng)右邊不平衡時，向左邊旋轉(zhuǎn)。

如下圖所示，結(jié)點(diǎn) 50 插入后，樹的平衡性被打破。

這里使用左旋轉(zhuǎn)（逆時針）方案。結(jié)點(diǎn) 36 成為結(jié)點(diǎn) 45 的左子結(jié)點(diǎn)，結(jié)點(diǎn)45 原來的左子結(jié)點(diǎn)成為結(jié)點(diǎn)36的右子結(jié)點(diǎn)。

向逆時針旋轉(zhuǎn)后，結(jié)點(diǎn)45的平衡因子為 0，結(jié)點(diǎn)36的平衡因子為0，結(jié)點(diǎn) 48 的平衡因子為 -1。樹的有序性和平衡性得到保持。

RR 旋轉(zhuǎn)算法具體實(shí)現(xiàn)：

    '''
    RR 型調(diào)整
    '''
    def rr_rotate(self, node):
        # 右子結(jié)點(diǎn)
        new_p_node = p_node.r_child
        p_node.r_child = new_p_node.l_child
        new_p_node.l_child = p_node
        # 重置平衡因子
        p_node.balance = 0
        new_p_node.balance = 0
        return new_p_node

LR型調(diào)整（先逆后順）：如下圖當(dāng)插入結(jié)點(diǎn) 28 后，結(jié)點(diǎn) 36 的平衡因子變成 2，則可以使用 LR 旋轉(zhuǎn)算法。

以結(jié)點(diǎn) 29 作為新的根結(jié)點(diǎn)，結(jié)點(diǎn)27以結(jié)點(diǎn)29為旋轉(zhuǎn)中心，逆時針旋轉(zhuǎn)。

結(jié)點(diǎn)36以結(jié)點(diǎn)29為旋轉(zhuǎn)中心向順時針旋轉(zhuǎn)。

最后得到的樹還是一棵二叉平衡排序樹。

LR 旋轉(zhuǎn)算法實(shí)現(xiàn)：

    '''
    LR型調(diào)整
    '''
    def lr_rotate(self, p_node):
        # 左子結(jié)點(diǎn)
        b = p_node.l_child
        new_p_node = b.r_child
        p_node.l_child = new_p_node.r_child
        b.r_child = new_p_node.l_child
        new_p_node.l_child = b
        new_p_node.r_child = p_node
        if new_p_node.balance == 1:
            p_node.balance = -1
            b.balance = 0
        elif new_p_node.balance == -1:
            p_node.balance = 0
            b.balance = 1
        else:
            p_node.balance = 0
            b.balance = 0
        new_p_node.balance = 0
        return new_p_node

RL型調(diào)整：如下圖插入結(jié)點(diǎn)39 后，整棵樹的平衡打破，這時可以使用 RL 旋轉(zhuǎn)算法進(jìn)行調(diào)整。

把結(jié)點(diǎn)40設(shè)置為新的根結(jié)點(diǎn)，結(jié)點(diǎn)45以結(jié)點(diǎn) 40 為中心點(diǎn)順時針旋轉(zhuǎn)，結(jié)點(diǎn)36逆時針旋轉(zhuǎn)。

RL 算法具體實(shí)現(xiàn)：

    '''
    RL型調(diào)整
    '''
    def rl_rotate(self, p_node):
        b = p_node.r_child
        new_p_node = b.l_child
        p_node.r_child = new_p_node.l_child
        b.l_child = new_p_node.r_child
        new_p_node.l_child = p_node
        new_p_node.r_child = b
        if new_p_node.balance == 1:
            p_node.balance = 0
            b.balance = -1
        elif new_p_node.balance == -1:
            p_node.balance = 1
            b.balance = 0
        else:
            p_node.balance = 0
            b.balance = 0
        new_p_node.balance = 0
        return new_p_node

編寫完上述算法后，就可以編寫插入算法。在插入新結(jié)點(diǎn)時，檢查是否破壞二叉平衡排序樹的的平衡性，否則調(diào)用平衡算法。

當(dāng)插入一個結(jié)點(diǎn)后，為了保持平衡，需要找到最小不平衡子樹。

什么是最小不平衡子樹？

指離插入結(jié)點(diǎn)最近，且平衡因子絕對值大于 1 的結(jié)點(diǎn)為根結(jié)點(diǎn)構(gòu)成的子樹。

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, val):
        # 新的結(jié)點(diǎn)
        new_node = TreeNode(val)
        if self.root is None:
            # 空樹
            self.root = new_node
            return
        # 記錄離 s 最近的平衡因子不為 0 的結(jié)點(diǎn)。
        min_b = self.root
        # f 指向 a 的父結(jié)點(diǎn)
        f_node = None
        move_node = self.root
        f_move_node = None
        while move_node is not None:
            if move_node.value == new_node.value:
                # 結(jié)點(diǎn)已經(jīng)存在
                return
            if move_node.balance != 0:
                # 尋找最小不平衡子樹
                min_b = move_node
                f_node = f_move_node
            f_move_node = move_node
            if new_node.value < move_node.value:
                move_node = move_node.l_child
            else:
                move_node = move_node.r_child

        if new_node.value < f_move_node.value:
            f_move_node.l_child = new_node
        else:
            f_move_node.r_child = new_node
        move_node = min_b
        # 修改相關(guān)結(jié)點(diǎn)的平衡因子
        while move_node != new_node:
            if new_node.value < move_node.value:
                move_node.balance += 1
                move_node = move_node.l_child
            else:
                move_node.balance -= 1
                move_node = move_node.r_child

        if min_b.balance > -2 and min_b.balance < 2:
            # 插入結(jié)點(diǎn)后沒有破壞平衡性
            return

        if min_b.balance == 2:
            b = min_b.l_child
            if b.balance == 1:
                move_node = self.ll_rotate(min_b)
            else:
                move_node = self.lr_rotate(min_b)
        else:
            b = min_b.r_child
            if b.balance == 1:
                move_node = self.rl_rotate(min_b)
            else:
                move_node = self.rr_rotate(min_b)
        if f_node is None:
            self.root = move_node
        elif f_node.l_child == min_b:
            f_node.l_child = move_node
        else:
            f_node.r_child = move_node

中序遍歷： 此方法為了驗證樹結(jié)構(gòu)還是排序的。

    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        if root is None:
            return
        self.inorder_traversal(root.l_child)
        print(root.value, end="->")
        self.inorder_traversal(root.r_child)

二叉平衡排序樹本質(zhì)還是二樹排序樹。如果使用中序遍歷輸出的數(shù)字是有序的。測試代碼。

if __name__ == "__main__":
    nums = [3, 12, 8, 10, 9, 1, 7]
    tree = Tree(3)
    for i in range(1, len(nums)):
        tree.inster(nums[i])
    # 中序遍歷    
    tree.inorder_traversal(tree.root)
    '''
    輸出結(jié)果
    1->3->7->8->9->10->12->
    '''