正文

掌握AVL树构建技巧，实例解析助你轻松入门

/0 浏览量
0320

引言

AVL树是一种自平衡二叉搜索树，由Adelson-Velsky和Landis于1962年提出。它通过在插入和删除节点时保持树的平衡，从而确保查找、插入和删除操作的时间复杂度均为O(log n)。本文将详细解析AVL树的构建技巧，并通过实例帮助你轻松入门。

AVL树的基本概念

1. 定义

AVL树是一种特殊的二叉搜索树，它的每个节点都有一个平衡因子（Balance Factor），即左子树的高度与右子树的高度的差值。AVL树要求所有节点的平衡因子都在-1、0或1之间。

2. 平衡因子

平衡因子的计算公式为：

平衡因子 = 左子树高度 - 右子树高度

3. 平衡操作

当插入或删除节点导致某个节点的平衡因子超过1或低于-1时，需要进行平衡操作。AVL树的平衡操作包括四种情况：左左（LL）、右右（RR）、左右（LR）和右左（RL）。

AVL树的构建技巧

1. 插入操作

插入操作分为以下步骤：

  1. 插入节点：按照二叉搜索树的规则插入节点。
  2. 更新高度：从插入节点开始，向上更新每个节点的height属性。
  3. 检查平衡因子：从插入节点开始，向上检查每个节点的平衡因子。
  4. 平衡操作：如果发现某个节点的平衡因子超过1或低于-1，则根据情况选择相应的平衡操作。

2. 删除操作

删除操作分为以下步骤：

  1. 删除节点：按照二叉搜索树的规则删除节点。
  2. 更新高度：从删除节点开始，向上更新每个节点的height属性。
  3. 检查平衡因子：从删除节点开始，向上检查每个节点的平衡因子。
  4. 平衡操作：如果发现某个节点的平衡因子超过1或低于-1，则根据情况选择相应的平衡操作。

实例解析

以下是一个AVL树的构建实例，包括插入和删除操作：

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

class AVLTree:
    def insert(self, root, key):
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        balanceFactor = self.getBalance(root)

        if balanceFactor > 1 and key < root.left.key:
            return self.rightRotate(root)
        if balanceFactor < -1 and key > root.right.key:
            return self.leftRotate(root)
        if balanceFactor > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        if balanceFactor < -1 and key < root.right.key:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def delete(self, root, key):
        if not root:
            return root
        elif key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete(root.right, temp.key)

        if root is None:
            return root

        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        balanceFactor = self.getBalance(root)

        if balanceFactor > 1 and self.getBalance(root.left) >= 0:
            return self.rightRotate(root)
        if balanceFactor < -1 and self.getBalance(root.right) <= 0:
            return self.leftRotate(root)
        if balanceFactor > 1 and self.getBalance(root.left) < 0:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        if balanceFactor < -1 and self.getBalance(root.right) > 0:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y

    def rightRotate(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
        return x

    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

# 创建AVL树并插入节点
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
    root = avl.insert(root, key)

# 打印AVL树
print("Preorder traversal of the constructed AVL tree is")
avl.preOrder(root)

# 删除节点
root = avl.delete(root, 10)

# 打印AVL树
print("\nPreorder traversal after deletion of 10")
avl.preOrder(root)

总结

本文详细解析了AVL树的构建技巧，并通过实例展示了插入和删除操作。通过学习本文，读者可以轻松入门AVL树的构建。在实际应用中，AVL树因其高效的查找、插入和删除操作而被广泛应用于各种场景。

-- 展开阅读全文 --