数据结构--AVL树

时间：2025-02-20 14:30:58

AVL树是一种自平衡的二叉搜索树，得名于其发明者G. M. Adelson-Velsky和E. M. Landis。在AVL树中，任何节点的两个子树的高度差最多为1，因此它也被称为高度平衡树。以下是使用Python实现的简单AVL树代码示例：

定义节点类

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 新节点默认高度为1

计算节点高度

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

获取节点的平衡因子

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

右旋转操作（LL）

def rightRotate(y):
    x = y.left
    T2 = x.right

    # 旋转操作
    x.right = y
    y.left = T2

    # 更新高度
    y.height = max(getHeight(y.left), getHeight(y.right)) + 1
    x.height = max(getHeight(x.left), getHeight(x.right)) + 1

    # 返回新的根节点
    return x

左旋转操作（RR）

def leftRotate(x):
    y = x.right
    T2 = y.left

    # 旋转操作
    y.left = x
    x.right = T2

    # 更新高度
    x.height = max(getHeight(x.left), getHeight(x.right)) + 1
    y.height = max(getHeight(y.left), getHeight(y.right)) + 1

    # 返回新的根节点
    return y

左右旋转操作（LR）

def leftRightRotate(z):
    z.left = leftRotate(z.left)
    return rightRotate(z)

右左旋转操作（RL）

def rightLeftRotate(z):
    z.right = rightRotate(z.right)
    return leftRotate(z)

插入节点

def insert(node, key):
    # 1. 执行正常的BST插入
    if not node:
        return TreeNode(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    # 2. 更新这个节点的高度
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))

    # 3. 获取平衡因子，检查是否失衡
    balance = getBalance(node)

    # 如果失衡，进行相应的旋转
    # 左左情况
    if balance > 1 and key < node.left.key:
        return rightRotate(node)
    # 右右情况
    if balance < -1 and key > node.right.key:
        return leftRotate(node)
    # 左右情况
    if balance > 1 and key > node.left.key:
        return leftRightRotate(node)
    # 右左情况
    if balance < -1 and key < node.right.key:
        return rightLeftRotate(node)

    return node

中序遍历（可选，用于验证树结构）

def inOrder(root):
    if root:
        inOrder(root.left)
        print(root.key, end=' ')
        inOrder(root.right)

示例使用

if __name__ == "__main__":
    root = None
    keys = [10, 20, 30, 40, 50, 25]
    for key in keys:
        root = insert(root, key)
    print("Inorder traversal of the constructed AVL tree is")
    inOrder(root)

相关文章