温故知新：数据结构的分水树（岭）- 中篇

阅前提示

该系列为数据结构回顾向文章，重点在于温故知新。
适合人群：All
阅读方式：浏览回顾
本系列在不断更新中，如果对你有所帮助，点赞收藏吧：）

---

AVL 树

平衡的二叉查找树，节点的左右子树高度差不超过1

右旋：（左子树高于右子树，且是左-左型）顺时针旋转两个节点，使得父节点被自己的左孩子取代，左孩子的右子节点变成自己的左孩子，而自己成为自己的右孩子

左旋：（右高于左，且是右-右型）逆时针旋转两个节点，使得父节点被自己的右孩子取代，右孩子的左子节点变成自己的右孩子，而自己成为自己的左孩子

另外两种情况

右-左型：先右旋，再左旋

左-右型：先左旋，再右旋

优点：查找速度保持在O(logN)

缺点：由于要保持平衡，所以添加操作会存在左旋右旋的操作，频繁增删操作会影响性能。

class BTreeNode:
    Value = None;
    Left = None;
    Right = None;
    Depth = None;
    def __init__(self,v:int):
        self.Value = v;

class AVLTree:
    Node = None

    def Find(self,X:int) -> BTreeNode:
        self.__find(self.Node,X)

    def __find(self,Node:BTreeNode,X:int):
        if Node == None :
            return None;
        if Node.Value == X:
            return Node
        if Node.Value > X:
            return self.__find(Node.Left,X);
        return self.__find(Node.Right,X);

    def Add(self,X:int):
        self.Node = self.__add(self.Node,X);

    def __add(self,Node:BTreeNode,X:int) -> BTreeNode:
        if Node == None:
            Node = BTreeNode(X)
            Node.Depth = 0
        else:
            if Node.Value > X :
                Node.Left = self.__add(Node.Left,X)
                if self.GetDepth(Node.Left) - self.GetDepth(Node.Right) == 2:
                    if Node.Left.Value > X:
                        Node = self.SingleRotateRight(Node) # 左-左型
                    else:
                        Node = self.DoubleRotateLeft(Node) # 左-右型
            elif Node.Value < X:
                Node.Right = self.__add(Node.Right,X)
                if self.GetDepth(Node.Right) - self.GetDepth(Node.Left) == 2:
                    if Node.Right.Value < X:
                        Node = self.SingleRotateLeft(Node) # 右-右型
                    else:
                        Node = self.DoubleRotateRight(Node) # 右-左型

        Node.Depth = (self.GetDepth(Node.Right) if self.GetDepth(Node.Left) < self.GetDepth(Node.Right) else self.GetDepth(Node.Left)) + 1
        return Node

    def GetDepth(self,Node:BTreeNode) -> int:
        if Node == None:
            return -1;
        return Node.Depth

    #右-右型：左旋 父节点被自己的右孩子取代，右孩子的左子节点变成自己的右孩子，而自己成为自己的左孩子
    def SingleRotateLeft(self,Node:BTreeNode) -> BTreeNode:
        TempNode = Node
        Node = TempNode.Right
        TempNode.Right = Node.Left
        TempNode.Depth = (self.GetDepth(TempNode.Right) if self.GetDepth(TempNode.Left) < self.GetDepth(
            TempNode.Right) else self.GetDepth(TempNode.Left)) + 1
        Node.Left = TempNode
        Node.Depth = (self.GetDepth(Node.Right) if self.GetDepth(Node.Left) < self.GetDepth(
            Node.Right) else self.GetDepth(Node.Left)) + 1
        return Node

    # 左-左型：右旋  父节点被自己的左孩子取代，左孩子的右子节点变成自己的左孩子，而自己成为自己的右孩子
    def SingleRotateRight(self,Node:BTreeNode)-> BTreeNode:
        TempNode = Node
        Node = TempNode.Left
        TempNode.Left = Node.Right
        TempNode.Depth = (self.GetDepth(TempNode.Right) if self.GetDepth(TempNode.Left) < self.GetDepth(
            TempNode.Right) else self.GetDepth(TempNode.Left)) + 1
        Node.Right = TempNode
        Node.Depth = (self.GetDepth(Node.Right) if self.GetDepth(Node.Left) < self.GetDepth(
            Node.Right) else self.GetDepth(Node.Left)) + 1
        return Node

    # 左-右型  先对左子节点进行左旋,后对父节点右旋
    def DoubleRotateLeft(self,Node:BTreeNode) -> BTreeNode:
        Node.Left = self.SingleRotateLeft(Node.Left)
        return self.SingleRotateRight(Node)

    # 右-左型  先对右子节点进行右旋,后对父节点左旋
    def DoubleRotateRight(self, Node: BTreeNode) -> BTreeNode:
        Node.Right = self.SingleRotateRight(Node.Right)
        return self.SingleRotateLeft(Node)

    # 删除操作：叶子就直接删除，存在一个子节点则连接上下，若存在两个，则将该节点右侧的最小值（叶子）替代该节点的值，并删除叶子。
    def Delete(self,X:int):
        self.__delete(self.Node,X);

    def __delete(self,Node:BTreeNode,X:int) -> BTreeNode:
        if Node == None:
            return None;
        if Node.Value > X:
            Node.Left = self.__delete(Node.Left,X)
        elif Node.Value < X:
            Node.Right = self.__delete(Node.Right,X)
        elif Node.Value == X:
            if Node.Left != None and Node.Right != None:
                v = self.__getMin(Node.Right);
                Node.Value = v
                Node.Right = self.__delete(Node.Right,v) # 替换了右子树的最小值后删除该最小值的叶子节点。
            else:
                if Node.Left == None:
                    Node = Node.Right;
                elif Node.Right == None:
                    Node = Node.Left;
        return Node


    def GetMin(self) -> int:
        return self.__getMin(self.Node)
    def __getMin(self,Node) -> int:
        if Node == None:
            return None;
        if Node.Left == None:
            return Node.Value;
        return self.__getMin(Node.Left);

    # 最大值就是右侧叶子
    def GetMax(self) -> int:
        return self.__getMax(self.Node)
    def __getMax(self,Node) -> int:
        if Node == None:
            return None;
        if Node.Right == None:
            return Node.Value;
        return self.__getMax(Node.Right);

    def Log(self):
        self.__log(self.Node,0)
    def __log(self,Node:BTreeNode,depth:int):
        empty = "  "
        if (Node == None):
            return;
        if (Node.Value == None):
            print(empty * depth + "N")
        else:
            print(empty * depth + str(Node.Value))
        if (Node.Left != None):
            self.__log(Node.Left, depth + 1);
        if (Node.Right != None):
            self.__log(Node.Right, depth + 1);

---

.
.
.
.
.

---

嗨，我是作者Vin129，逐儿时之梦正在游戏制作的技术海洋中漂泊。知道的越多，不知道的也越多。希望我的文章对你有所帮助：）

---