平衡二叉树LR的算法

根据平衡二叉树的定义，当插入或删除节点后，如果树的平衡因子（左子树高度减去右子树高度）的绝对值大于1，则需要进行旋转操作来保持平衡。其中，LR算法是一种针对平衡二叉树的旋转算法，用于解决插入节点后左右子树高度差大于1的情况。

具体来说，当插入节点后，如果左子树高度比右子树高度大2，且新节点插入到了左子树的右子树上，则需要进行LR旋转。该旋转包括以下三个步骤：

1. 对左子树进行一次RR旋转，将新节点的父节点作为旋转后的根节点。
2. 对整棵树进行一次LL旋转，将新节点作为旋转后的根节点。
3. 更新所有节点的高度值。

下面是一个示例代码，其中Node类表示平衡二叉树的节点，height表示节点的高度，left和right分别表示左右子树。

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

def height(node):
    if not node:
        return 0
    return node.height

def balance_factor(node):
    if not node:
        return 0
    return height(node.left) - height(node.right)

def left_rotate(node):
    new_root = node.right
    node.right = new_root.left
    new_root.left = node
    node.height = max(height(node.left), height(node.right)) + 1
    new_root.height = max(height(new_root.left), height(new_root.right)) + 1
    return new_root

def right_rotate(node):
    new_root = node.left
    node.left = new_root.right
    new_root.right = node
    node.height = max(height(node.left), height(node.right)) + 1
    new_root.height = max(height(new_root.left), height(new_root.right)) + 1
    return new_root

def insert_node(node, val):
    if not node:
        return Node(val)
    elif val < node.val:
        node.left = insert_node(node.left, val)
    else:
        node.right = insert_node(node.right, val)
    node.height = max(height(node.left), height(node.right)) + 1
    bf = balance_factor(node)
    if bf > 1 and val < node.left.val:
        return right_rotate(node)
    elif bf < -1 and val > node.right.val:
        return left_rotate(node)
    elif bf > 1 and val > node.left.val:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    elif bf < -1 and val < node.right.val:
        node.right = right_rotate(node.right)
        return left_rotate(node)
    return node