AVL平衡二叉树详解

一、什么是平衡二叉树？

1. 概念

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

2. 为什么要用平衡二叉树

之前我们在学习二分搜索树的时候有遇到过一种情况，在顺序添加一组数据的时候，极端情况下二分搜索树可能会退化成一个链表，所以此处我们需要使用平衡二叉树来解决这些问题。

3. 平衡二叉树详解

从这个图中我们可以看出，一个满二叉树就是一个平衡二叉树。

同样的一个完全二叉树也是一个平衡二叉树。

甚至线段树也是一个平衡二叉树，大家应该已经发现规律了，当在一棵树中左右节点差值不大于1时我们就可以称这棵树为平衡二叉树。

这张图体现了平衡二叉树的第二个条件，高度和节点数量之间的关系也是O(logn)的。

4. 平衡二叉树的实现思路

首先我们维护一个属性来实现对平衡二叉树高度的记录；然后在通过高度来计算平衡因子。

• 高度值：我们从叶子节点开始进行记录，初始值为1，每一层节点的值为左右两个节点中的最大值；
• 平衡因子：左右两个节点的高度差值取正数，就是当前节点的平衡因子；

5. 代码实现

使用BST底层结构

import os
import re

class BST:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None
        self.size = 0

    def get_size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    # 向二分搜索树中添加新的元素(key, value)
    def add(self, key, value):
        self.root = self._add(self.root, key, value)

    # 向以node为根的二分搜索树中插入元素(key, value)，递归算法
    # 返回插入新节点后二分搜索树的根
    def _add(self, node, key, value):
        if node is None:
            self.size += 1
            return self.Node(key, value)

        if key < node.key:
            node.left = self._add(node.left, key, value)
        elif key > node.key:
            node.right = self._add(node.right, key, value)
        else:  # key == node.key
            node.value = value

        return node

    # 返回以node为根节点的二分搜索树中，key所在的节点
    def _get_node(self, node, key):
        if node is None:
            return None

        if key == node.key:
            return node
        elif key < node.key:
            return self._get_node(node.left, key)
        else:  # key > node.key
            return self._get_node(node.right, key)

    def contains(self, key):
        return self._get_node(self.root, key) is not None

    def get(self, key):
        node = self._get_node(self.root, key)
        return None if node is None else node.value

    def set(self, key, new_value):
        node = self._get_node(self.root, key)
        if node is None:
            raise ValueError(f"{key} doesn't exist!")
        node.value = new_value

    # 返回以node为根的二分搜索树的最小值所在的节点
    def _minimum(self, node):
        if node.left is None:
            return node
        return self._minimum(node.left)

    # 删除掉以node为根的二分搜索树中的最小节点
    # 返回删除节点后新的二分搜索树的根
    def _remove_min(self, node):
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node

        node.left = self._remove_min(node.left)
        return node

    # 从二分搜索树中删除键为key的节点
    def remove(self, key):
        node = self._get_node(self.root, key)
        if node is not None:
            self.root = self._remove(self.root, key)
            return node.value
        return None

    def _remove(self, node, key):
        if node is None:
            return None

        if key < node.key:
            node.left = self._remove(node.left, key)
            return node
        elif key > node.key:
            node.right = self._remove(node.right, key)
            return node
        else:  # key == node.key
            # 待删除节点左子树为空的情况
            if node.left is None:
                right_node = node.right
                node.right = None
                self.size -= 1
                return right_node

            # 待删除节点右子树为空的情况
            if node.right is None:
                left_node = node.left
                node.left = None
                self.size -= 1
                return left_node

            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None

            return successor

def main():
    print("Pride and Prejudice")

    words = []
    if read_file("pride-and-prejudice.txt", words):
        print(f"Total words: {len(words)}")

        bst_map = BST()
        for word in words:
            if bst_map.contains(word):
                bst_map.set(word, bst_map.get(word) + 1)
            else:
                bst_map.add(word, 1)

        print(f"Total different words: {bst_map.get_size()}")
        print(f"Frequency of PRIDE: {bst_map.get('pride')}")
        print(f"Frequency of PREJUDICE: {bst_map.get('prejudice')}")

    print()

引入FileOperation

import re
import os

def read_file(filename, words):
    """读取文件名称为filename中的内容，并将其中包含的所有词语放进words中"""

    if filename is None or words is None:
        print("filename is None or words is None")
        return False

    # 文件读取
    try:
        if os.path.exists(filename):
            with open(filename, 'r', encoding='utf-8') as file:
                contents = file.read()
        else:
            return False
    except IOError:
        print(f"Cannot open {filename}")
        return False

    # 简单分词
    # 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
    # 在这里只做demo展示用
    if contents:
        start = first_character_index(contents, 0)
        i = start + 1
        while i <= len(contents):
            if i == len(contents) or not contents[i].isalpha():
                word = contents[start:i].lower()
                words.append(word)
                start = first_character_index(contents, i)
                i = start + 1
            else:
                i += 1

    return True

def first_character_index(s, start):
    """寻找字符串s中，从start的位置开始的第一个字母字符的位置"""
    for i in range(start, len(s)):
        if s[i].isalpha():
            return i
    return len(s)

AVLTree

class AVLTree:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            self.height = 1

    def __init__(self):
        self.root = None
        self.size = 0

    def get_size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def get_height(self, node):
        """获取节点node的高度"""
        if node is None:
            return 0
        return node.height

    def get_balance_factor(self, node):
        """获取节点node的平衡因子"""
        if node is None:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    # 向二分搜索树中添加新的元素(key, value)
    def add(self, key, value):
        self.root = self._add(self.root, key, value)

    # 向以node为根的二分搜索树中插入元素(key, value)，递归算法
    # 返回插入新节点后二分搜索树的根
    def _add(self, node, key, value):
        if node is None:
            self.size += 1
            return self.Node(key, value)

        if key < node.key:
            node.left = self._add(node.left, key, value)
        elif key > node.key:
            node.right = self._add(node.right, key, value)
        else:  # key == node.key
            node.value = value

        # 更新height
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 计算平衡因子
        balance_factor = self.get_balance_factor(node)
        if abs(balance_factor) > 1:
            print(f"unbalanced : {balance_factor}")

        return node

    # 返回以node为根节点的二分搜索树中，key所在的节点
    def _get_node(self, node, key):
        if node is None:
            return None

        if key == node.key:
            return node
        elif key < node.key:
            return self._get_node(node.left, key)
        else:  # key > node.key
            return self._get_node(node.right, key)

    def contains(self, key):
        return self._get_node(self.root, key) is not None

    def get(self, key):
        node = self._get_node(self.root, key)
        return None if node is None else node.value

    def set(self, key, new_value):
        node = self._get_node(self.root, key)
        if node is None:
            raise ValueError(f"{key} doesn't exist!")
        node.value = new_value

    # 返回以node为根的二分搜索树的最小值所在的节点
    def _minimum(self, node):
        if node.left is None:
            return node
        return self._minimum(node.left)

    # 删除掉以node为根的二分搜索树中的最小节点
    # 返回删除节点后新的二分搜索树的根
    def _remove_min(self, node):
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node

        node.left = self._remove_min(node.left)
        return node

    # 从二分搜索树中删除键为key的节点
    def remove(self, key):
        node = self._get_node(self.root, key)
        if node is not None:
            self.root = self._remove(self.root, key)
            return node.value
        return None

    def _remove(self, node, key):
        if node is None:
            return None

        if key < node.key:
            node.left = self._remove(node.left, key)
            return node
        elif key > node.key:
            node.right = self._remove(node.right, key)
            return node
        else:  # key == node.key
            # 待删除节点左子树为空的情况
            if node.left is None:
                right_node = node.right
                node.right = None
                self.size -= 1
                return right_node

            # 待删除节点右子树为空的情况
            if node.right is None:
                left_node = node.left
                node.left = None
                self.size -= 1
                return left_node

            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None

            return successor

二、检查二分搜索树的性质和平衡性

1. 检查二分搜索树的性质

def is_bst(self):
    """判断该二叉树是否是一棵二分搜索树"""
    keys = []
    self._in_order(self.root, keys)
    for i in range(1, len(keys)):
        if keys[i - 1] > keys[i]:
            return False
    return True

def _in_order(self, node, keys):
    if node is None:
        return

    self._in_order(node.left, keys)
    keys.append(node.key)
    self._in_order(node.right, keys)

2. 检查二分搜索树是否是平衡二叉树

def is_balanced(self):
    """判断该二叉树是否是一颗平衡二叉树"""
    return self._is_balanced(self.root)

def _is_balanced(self, node):
    """判断以node为根的二叉树是不是一颗平衡二叉树，递归算法"""
    if node is None:
        return True

    balance_factor = self.get_balance_factor(node)

    if abs(balance_factor) > 1:
        return False

    return self._is_balanced(node.left) and self._is_balanced(node.right)

三、旋转操作的基本原理

1. 在什么时候维护平衡

首先我们先来看一下二分搜索树插入节点的操作：

当二分搜索树插入一个新的节点的时候机会出现打破平衡的风险；这个风险会直接反应在新加入节点的父亲节点或者祖先节点上；因为我们在插入操作完成以后，高度就需要重新更新一下，更新以后左右子树的高度差可能就会>1；所以维护平衡的操作需要在新加入元素的时候执行。

2. 采用什么样的方式？

加入节点后向上维护平衡性。

3. 右旋转

首先是最一般化的情况：

这样的情况，对于根节点y来说左子树的高度明显是大于右子树的高度的，为了不失一般性我们接着看下一个图示：

其中的T1-T4是虚拟的子节点；从这个图示可以看出，左节点的高度也是明显大于右节点的，另外从这个图中我们可以看出T1<z<T2<x<T3<y<T4这样的一种关系。

对于这个树来说，左节点过于高了，我们需要做的是让这个树平衡同时又不能失去二分搜索树的性质，这就叫做右旋转。

首先我们需要将x的右子树等于y也就是这样：

接下来我们让y的左子树等于T3：

最后我们让x作为新的二叉树的根节点：

这就是右旋转的图示过程；右旋转操作执行完毕以后T1<z<T2<x<T3<y<T4依然是成立的。

4. 代码实现右旋转

def _right_rotate(self, y):
    """对节点y进行向右旋转操作，返回旋转后新的根节点x
            y                              x
           / \                           /   \
          x   T4     向右旋转 (y)        z     y
         / \       - - - - - - - ->    / \   / \
        z   T3                       T1  T2 T3 T4
       / \
     T1   T2
    """
    x = y.left
    T3 = x.right

    # 向右旋转过程
    x.right = y
    y.left = T3

    # 更新height
    y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
    x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1

    return x

5. 左旋转原理

左旋转的原理与右旋转是完全对称的，请参考右旋转。

6. 左旋转代码实现

def _left_rotate(self, y):
    """对节点y进行向左旋转操作，返回旋转后新的根节点x
        y                             x
      /  \                          /   \
     T1   x      向左旋转 (y)       y     z
         / \   - - - - - - - ->   / \   / \
       T2  z                     T1 T2 T3 T4
          / \
         T3 T4
    """
    x = y.right
    T2 = x.left

    # 向左旋转过程
    x.left = y
    y.right = T2

    # 更新height
    y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
    x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1

    return x

7. 平衡维护

实现旋转操作以后我们需要对添加过程进行相应的调用：

def _add(self, node, key, value):
    """向以node为根的二分搜索树中插入元素(key, value)，递归算法
    返回插入新节点后二分搜索树的根
    """
    if node is None:
        self.size += 1
        return self.Node(key, value)

    if key < node.key:
        node.left = self._add(node.left, key, value)
    elif key > node.key:
        node.right = self._add(node.right, key, value)
    else:  # key == node.key
        node.value = value

    # 更新height
    node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(node)
    if abs(balance_factor) > 1:
        print(f"unbalanced : {balance_factor}")

    # 平衡维护
    # LL
    if balance_factor > 1 and self.get_balance_factor(node.left) >= 0:
        return self._right_rotate(node)
    # RR
    if balance_factor < -1 and self.get_balance_factor(node.right) <= 0:
        return self._left_rotate(node)
    # LR
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) < 0:
        ret_node.left = self._left_rotate(ret_node.left)
        return self._right_rotate(ret_node)
    # RL
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) > 0:
        ret_node.right = self._right_rotate(ret_node.right)
        return self._left_rotate(ret_node)

    return ret_node

四、LR和RL

LR情况

新插入的节点在左侧的右侧：

这样的情况下我们需要先对x进行左旋转让它变成LL(左倾斜)的情况：

此时我们直接使用右旋转就可以搞定了。

RL情况

新插入的节点在右侧的左侧：

此时我们首先对x节点进行右旋转：

然后直接使用左旋转就可以搞定。

AVL树LR和RL旋转代码实现

向以node为根的二分搜索树中插入元素(key, value)，递归算法，返回插入新节点后二分搜索树的根：

def _add(self, node, key, value):
    if node is None:
        self.size += 1
        return self.Node(key, value)

    if key < node.key:
        node.left = self._add(node.left, key, value)
    elif key > node.key:
        node.right = self._add(node.right, key, value)
    else:  # key == node.key
        node.value = value

    # 更新height
    node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(node)
    if abs(balance_factor) > 1:
        print(f"unbalanced : {balance_factor}")

    # 平衡维护
    # LL情况
    if balance_factor > 1 and self.get_balance_factor(node.left) >= 0:
        return self._right_rotate(node)

    # RR情况
    if balance_factor < -1 and self.get_balance_factor(node.right) <= 0:
        return self._left_rotate(node)

    # LR情况
    if balance_factor > 1 and self.get_balance_factor(node.left) < 0:
        node.left = self._left_rotate(node.left)
        return self._right_rotate(node)

    # RL情况
    if balance_factor < -1 and self.get_balance_factor(node.right) > 0:
        node.right = self._right_rotate(node.right)
        return self._left_rotate(node)

    return node

AVL树删除操作

对于AVL树的删除操作其实非常简单，添加的时候我们有四种情况可能会出现失衡（LL、RR、LR、RL），对于删除操作也是一样的；使用向上回溯的方式就会发现，当我们删除一个元素后也有可能会导致二分搜索树的失衡；这个时候就需要我们来维护AVL的平衡，维护的方式和添加的时候是一样的。

初始版本实现

def _remove(self, node, key):
    if node is None:
        return None

    ret_node = None

    if key < node.key:
        node.left = self._remove(node.left, key)
        ret_node = node
    elif key > node.key:
        node.right = self._remove(node.right, key)
        ret_node = node
    else:  # key == node.key
        # 待删除节点左子树为空的情况
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            ret_node = right_node

        # 待删除节点右子树为空的情况
        elif node.right is None:
            left_node = node.left
            node.left = None
            self.size -= 1
            ret_node = left_node
        else:
            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None
            ret_node = successor

    # 更新height
    ret_node.height = 1 + max(self.get_height(ret_node.left), self.get_height(ret_node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(ret_node)

    # 平衡维护
    # LL情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) >= 0:
        return self._right_rotate(ret_node)

    # RR情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) <= 0:
        return self._left_rotate(ret_node)

    # LR情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) < 0:
        ret_node.left = self._left_rotate(ret_node.left)
        return self._right_rotate(ret_node)

    # RL情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) > 0:
        ret_node.right = self._right_rotate(ret_node.right)
        return self._left_rotate(ret_node)

    return ret_node

修复版本

问题说明： 对于我们现在的代码是有一个小BUG的，因为我们在进行remove_min操作的时候并没有维护自平衡所以这个时候可能会导致失衡的情况发生；此时我们只需要维护remove_min的删除操作即可。

修复后的完整实现：

def _remove(self, node, key):
    if node is None:
        return None

    ret_node = None

    if key < node.key:
        node.left = self._remove(node.left, key)
        ret_node = node
    elif key > node.key:
        node.right = self._remove(node.right, key)
        ret_node = node
    else:  # key == node.key
        # 待删除节点左子树为空的情况
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            ret_node = right_node
        elif node.right is None:
            # 待删除节点右子树为空的情况
            left_node = node.left
            node.left = None
            self.size -= 1
            ret_node = left_node
        else:
            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove(node.right, successor.key)
            successor.left = node.left

            node.left = node.right = None
            ret_node = successor

    if ret_node is None:
        return None

    # 更新height
    ret_node.height = 1 + max(self.get_height(ret_node.left), self.get_height(ret_node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(ret_node)

    # 平衡维护
    # LL情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) >= 0:
        return self._right_rotate(ret_node)

    # RR情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) <= 0:
        return self._left_rotate(ret_node)

    # LR情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) < 0:
        ret_node.left = self._left_rotate(ret_node.left)
        return self._right_rotate(ret_node)

    # RL情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) > 0:
        ret_node.right = self._right_rotate(ret_node.right)
        return self._left_rotate(ret_node)

    return ret_nodenode.left) < 0:
        node.left = self._left_rotate(node.left)
        return self._right_rotate(node)
    # RL
    if balance_factor < -1 and self.get_balance_factor(node.right) > 0:
        node.right = self._right_rotate(node.right)
        return self._left_rotate(node)

    return node

五、从AVL树中删除元素

对于AVL树的删除操作其实非常简单，添加的时候我们有四种情况可能会出现失衡(LL RR LR RL)，对于删除操作也是一样的；使用向上回溯的方式就会发现，当我们删除一个元素后也有可能会导致二分搜索树的失衡；这个时候就需要我们来维护AVL的平衡，维护的方式和添加的时候是一样的。

代码实现

def _remove(self, node, key):
    if node is None:
        return None

    ret_node = None

    if key < node.key:
        node.left = self._remove(node.left, key)
        ret_node = node
    elif key > node.key:
        node.right = self._remove(node.right, key)
        ret_node = node
    else:  # key == node.key
        # 待删除节点左子树为空的情况
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            ret_node = right_node

        # 待删除节点右子树为空的情况
        elif node.right is None:
            left_node = node.left
            node.left = None
            self.size -= 1
            ret_node = left_node
        else:
            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None
            ret_node = successor

    # 更新height
    ret_node.height = 1 + max(self.get_height(ret_node.left), self.get_height(ret_node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(ret_node)

    # 平衡维护
    # LL
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) >= 0:
        return self._right_rotate(ret_node)
    # RR
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) <= 0:
        return self._left_rotate(ret_node)
    # LR
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) < 0:
        ret_node.left = self._left_rotate(ret_node.left)
        return self._right_rotate(ret_node)
    # RL
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) > 0:
        ret_node.right = self._right_rotate(ret_node.right)
        return self._left_rotate(ret_node)

    return ret_node

其实对于我们现在的代码是有一个小BUG的，因为我们在进行remove_min操作的时候并没有维护自平衡所以这个时候可能会导致失衡的情况发生；此时我们只需要维护remove_min的删除操作即可：

def remove(self, node, key):
    """
    删除AVL树中的节点
    Args:
        node: 当前节点
        key: 要删除的键
    Returns:
        删除后的子树根节点
    """
    if node is None:
        return None

    ret_node = None

    if key < node.key:
        node.left = self.remove(node.left, key)
        ret_node = node
    elif key > node.key:
        node.right = self.remove(node.right, key)
        ret_node = node
    else:  # key == node.key
        # 待删除节点左子树为空的情况
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            ret_node = right_node
        elif node.right is None:
            # 待删除节点右子树为空的情况
            left_node = node.left
            node.left = None
            self.size -= 1
            ret_node = left_node
        else:
            # 待删除节点左右子树均不为空的情况
            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self.minimum(node.right)
            successor.right = self.remove(node.right, successor.key)
            successor.left = node.left
            node.left = node.right = None
            ret_node = successor

    if ret_node is None:
        return None

    # 更新高度
    ret_node.height = 1 + max(self.get_height(ret_node.left), 
                              self.get_height(ret_node.right))

    # 计算平衡因子
    balance_factor = self.get_balance_factor(ret_node)

    # 平衡维护
    # LL情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) >= 0:
        return self.right_rotate(ret_node)

    # RR情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) <= 0:
        return self.left_rotate(ret_node)

    # LR情况
    if balance_factor > 1 and self.get_balance_factor(ret_node.left) < 0:
        ret_node.left = self.left_rotate(ret_node.left)
        return self.right_rotate(ret_node)

    # RL情况
    if balance_factor < -1 and self.get_balance_factor(ret_node.right) > 0:
        ret_node.right = self.right_rotate(ret_node.right)
        return self.left_rotate(ret_node)

    return ret_node