【python資料結構】平衡二叉樹

具體知識點：https://blog.csdn.net/liyuanyue2017/article/details/83652743 便于了解

平衡二叉樹要解決的問題：

是設計怎樣的樹結構才能使查找的效率比較高。用Asl來進行衡量

平衡因子： 左右子樹的高度差  要求 平衡因子 <=1 這樣的數稱為平衡兒二叉樹  使得樹的高度 logn

在我們将資料插入平衡二叉樹的時候會導緻樹變得不平衡，那怎麼進行調整才能夠變得平衡呢：

1、右單旋  麻煩節點在發現者節點的右子樹的右子樹上（作為左右子節點都行），我們進行的調整稱為  RR  将右子樹的位置提升為根節點

2、左單旋  同理                左     左

調整的時候 隻針對相距最近的發現者與破壞者

還有LR RL 旋轉

同時旋轉之後的相對大小 要保持

插入資料的時候 要注意更新 每個節點的 平衡因子

"""

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : 平衡二叉樹.py
# @Date  : 2019/3/29 0029
# @Contact : [email protected] 
# @Author: DeepMan

from Tree import *

# 以下 函數都是一個子產品，針對發現者 和破壞者 在一棵複雜的樹中  我們就需要調用這些簡單的操作 來完成數的平衡
# 其基本思路是把 B 的右子樹騰出來挂到 A 的左子樹上，傳回 B 作為目前子樹的根
def LLRotation(A): # A是被破壞節點
    B = A.left
    A.left = B.right
    B.right = A

    A.heigh = max(getHeight(A.left), getHeight(A.right)) + 1
    B.heigh = max(getHeight(B.left), A.heigh) + 1

    return B # 将B 作為根節點


# 其基本思路是把 B 的左子樹騰出來挂到 A 的右子樹上，傳回 B 作為目前子樹的根
def RRRotation(A):
    B = A.right
    A.right = B.left # 保證大小關系
    B.left = A

    A.heigh = max(getHeight(A.left), getHeight(A.right)) + 1
    B.heigh = max(getHeight(B.left), A.heigh) + 1

    return B

# 基本思想:是先将 B 作為根結點進行 LL 單旋轉化為 RR 插入，
# 再将 A 作為根結點進行 RR單旋（先 LL 再 RR）
def RLRotation(A):
    A.right = LLRotation(A.right)
    return RRRotation(A)

def LRRotation(A): # 先 RR 再 LL
    A.left = RRRotation(A.left)
    return LLRotation(A)


def getHeight(A):
    if A == None:
        return -1
    else:
        return A.heigh


def Insert(x, BST):
    if not  BST:
        BST = BinaryTree(data=x)
    else:
        if x < BST.data:
            BST.left = Insert(x, BST.left)
            if (getHeight(BST.left) - getHeight(BST.right)) == 2:
                if x < BST.left.data:
                    BST = LLRotation(BST)
                elif BST.left.data < x :
                    BST= LRRotation(BST)
        elif BST.data < x :
            BST.right = Insert(x, BST.right)
            if (getHeight(BST.right) - getHeight(BST.left)) == 2:
                if x < BST.right.data:
                    BST = RLRotation(BST)
                elif BST.right.data < x:
                    BST = RRRotation(BST)
    BST.heigh = max(getHeight(BST.left), getHeight(BST.right)) + 1
    return BST


# 層序周遊
def levelorder(BST):
    q = queue()
    t = BST
    if not BST:
        return
    q.append(t)
    while not q.empty():
        t = q.pop()
        print(t.data)
        if t.left:
            q.append(t.left)
        if t.right:
            q.append(t.right)


def main():
    node_list = [89, 8, 64, 64, 9, 49, 65, 146, 4, 61, 5, 46]

    # 建立一棵樹
    tree = BinaryTree(10)
    for node in node_list:
        BST = Insert(node, tree)

    levelorder(BST) # 先序周遊  根 左 右

main()