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

更新時(shí)間：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)存儲(chǔ)數(shù)據(jù)時(shí)，因其本身對(duì)結(jié)點(diǎn)之間的關(guān)系以及順序有特殊要求，也得益于這種限制，在查詢某一個(gè)結(jié)點(diǎn)時(shí)會(huì)帶來(lái)性能上的優(yōu)勢(shì)和操作上的方便。

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

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

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

1. 二叉排序樹

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

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

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

基于二叉樹結(jié)構(gòu)，從根結(jié)點(diǎn)開(kāi)始，從上向下，每一個(gè)父結(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]。通過(guò)下面流程，把每一個(gè)數(shù)字映射到二叉排序樹的結(jié)點(diǎn)上。

1.如果樹為空，把第一個(gè)數(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ù)字是無(wú)序的，根據(jù)二叉排序樹的插入算法，最終可得到一棵有排序性質(zhì)的樹結(jié)構(gòu)。對(duì)此棵樹進(jìn)行中序遍歷就可得到從小到大的一個(gè)遞增有序數(shù)列。

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

這里有一個(gè)要注意的地方。

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

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

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

首先，設(shè)計(jì)一個(gè)結(jié)點(diǎn)類，用來(lái)描述結(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 個(gè)屬性：

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

二叉排序樹類： 用來(lái)實(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

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

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

查詢流程：

把給定的關(guān)鍵字和根結(jié)點(diǎn)相比較。如果相等，則返回查找成功，結(jié)束查詢.
如果根結(jié)點(diǎn)的值大于關(guān)鍵字，則繼續(xù)進(jìn)入根結(jié)點(diǎn)的左子樹中開(kāi)始查找。
如果根結(jié)點(diǎn)的值小于關(guān)鍵字，則進(jìn)入根結(jié)點(diǎn)的右子樹中開(kāi)始查找。
如果沒(méi)有查詢到關(guān)鍵字，則返回最后訪問(wèn)過(guò)的結(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)開(kāi)始查找。
        move_node = self.root
        # 用來(lái)保存最后訪問(wèn)過(guò)的結(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
        # 出口二：如果沒(méi)有查詢到，則返回最后訪問(wèn)過(guò)的結(jié)點(diǎn)及None（None 表示沒(méi)查詢到）
        return last_node, None

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

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

反過(guò)來(lái)想想，本來(lái)應(yīng)該在這個(gè)地方找到，但是沒(méi)有，如果改成插入操作，就應(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)需要插入某一個(gè)結(jié)點(diǎn)時(shí)，先搜索是否已經(jīng)存在于樹結(jié)構(gòu)中。
如果沒(méi)有，則獲取到查詢時(shí)訪問(wèn)過(guò)的最一個(gè)結(jié)點(diǎn)，并和此結(jié)點(diǎn)比較大小。
如果比此結(jié)點(diǎn)大，則插入最后訪問(wèn)過(guò)結(jié)點(diǎn)的右子樹位置。
如果比此結(jié)點(diǎn)小，則插入最后訪問(wèn)過(guò)結(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:
            # 沒(méi)找到，獲取查詢時(shí)最后訪問(wèn)過(guò)的結(jié)點(diǎn)
            last_node = res[0]
            # 創(chuàng)建新結(jié)點(diǎn)
            new_node = TreeNode(value)
            # 最后訪問(wèn)的結(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 個(gè)子結(jié)點(diǎn)，寫幾行代碼測(cè)試一下，看從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的順序是否正確。

測(cè)試插入方法：

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("測(cè)試根5 -> 左4 ->左3:")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.l_child
    print("\n測(cè)試根5 -> 右12 ->右45->右50：")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.r_child
    '''
    輸出結(jié)果：
    測(cè)試根5 -> 左4 ->左3:
	5 ->4 ->3 ->
	測(cè)試根5 -> 右12 ->右45->右50：
	5 ->12 ->45 ->50 ->	
    '''

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

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

對(duì)二叉排序樹進(jìn)行中序遍歷，理論上輸出的數(shù)字應(yīng)該是有序的。這里寫一個(gè)中序遍歷，查看輸出的結(jié)點(diǎn)是不是有序的，從而驗(yà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)

測(cè)試插入的順序：

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)，利用其存儲(chǔ)特性，可以很方便地進(jìn)行查找、排序。并且隨時(shí)可添加、刪除結(jié)點(diǎn)，而不會(huì)影響排序和查找操作?；跇浔淼牟樵儾僮鞣Q為動(dòng)態(tài)查找。

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

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

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

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

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

因?yàn)榻Y(jié)點(diǎn)8沒(méi)有左子樹，在刪除之后，只需要把它的右子結(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)是可能會(huì)存在左子結(jié)點(diǎn)，但一定不會(huì)有右子結(jié)點(diǎn)）。用此結(jié)點(diǎn)替換結(jié)點(diǎn)25 便可。

為什么要這么做？

道理很簡(jiǎn)單，既然是左子樹中的最大值，替換刪除結(jié)點(diǎn)后，整個(gè)二叉排序樹的特性可以繼續(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 位置。

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

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

 	'''
    刪除結(jié)點(diǎn)
    key 為要要?jiǎng)h除的結(jié)點(diǎn)
    '''
    def delete(self, key):
        # 從根結(jié)點(diǎn)開(kāi)始查找，move_node 為搜索指針
        move_node = self.root
        # 要?jiǎng)h除的結(jié)點(diǎn)的父結(jié)點(diǎn),因?yàn)楦Y(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)，初始值為 None
        parent_node = None
        # 結(jié)點(diǎn)存在且沒(méi)有匹配上要找的關(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ǎng)h除的結(jié)點(diǎn)是否存在左子結(jié)點(diǎn)
        if move_node.l_child is None:
            if parent_node is None:
                # 如果要?jiǎng)h除的結(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

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

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->
    '''

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

2. 平衡二叉排序樹

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

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

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

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

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

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

平衡因子只可能是:

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

如下圖，就是平衡二叉排序樹，根結(jié)點(diǎn)的 2 個(gè)子樹深度相差為 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 個(gè)屬性：

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)時(shí)，如果導(dǎo)致樹結(jié)構(gòu)發(fā)生了不平衡性，則需要調(diào)整讓其達(dá)到平衡。這里的方案可以有 4種。

LL型調(diào)整（順時(shí)針）：左邊不平衡時(shí)，向右邊旋轉(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。

這里可以使用順時(shí)針旋轉(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)整
    順時(shí)針對(duì)調(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)整(逆時(shí)針旋轉(zhuǎn))：RR旋轉(zhuǎn)和 LL旋轉(zhuǎn)的算法差不多，只是當(dāng)右邊不平衡時(shí)，向左邊旋轉(zhuǎn)。

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

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

向逆時(shí)針旋轉(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)中心，逆時(shí)針旋轉(zhuǎn)。

結(jié)點(diǎn)36以結(jié)點(diǎn)29為旋轉(zhuǎn)中心向順時(shí)針旋轉(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 后，整棵樹的平衡打破，這時(shí)可以使用 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)順時(shí)針旋轉(zhuǎn)，結(jié)點(diǎn)36逆時(shí)針旋轉(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)時(shí)，檢查是否破壞二叉平衡排序樹的的平衡性，否則調(diào)用平衡算法。

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

什么是最小不平衡子樹？

指離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值大于 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)后沒(méi)有破壞平衡性
            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

中序遍歷： 此方法為了驗(yàn)證樹結(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ù)字是有序的。測(cè)試代碼。

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->
    '''