游牧学院

3.2 二叉树及其遍历方法
3.4 图的表示方法（邻接矩阵与邻接表）

树与图：平衡树（AVL树与红黑树）详解

在数据结构中，树和图是非常重要的概念。树是一种层次结构的数据结构，而图则是一种更为复杂的结构。平衡树是树的一种特殊形式，旨在保持树的高度平衡，以确保在最坏情况下的操作效率。本文将详细介绍两种常见的平衡树：AVL树和红黑树，包括它们的定义、性质、实现、优缺点以及注意事项。

1. AVL树

1.1 定义

AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树。它的特点是对于每个节点，左子树和右子树的高度差（平衡因子）最多为1。通过这种方式，AVL树能够保持较低的高度，从而保证基本操作（插入、删除、查找）的时间复杂度为O(log n)。

1.2 性质

  • 平衡因子：对于每个节点，定义其平衡因子为左子树高度减去右子树高度。平衡因子只能为-1、0或1。
  • 高度平衡：AVL树的高度始终保持在O(log n)的范围内。

1.3 操作

1.3.1 插入

插入操作需要遵循二叉搜索树的性质，并在插入后检查每个节点的平衡因子。如果某个节点的平衡因子变为2或-2，则需要进行旋转操作以恢复平衡。

旋转操作：

  • 单右旋（LL旋转）
  • 单左旋（RR旋转）
  • 左右旋（LR旋转）
  • 右左旋（RL旋转）

示例代码（Python）

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.get_height(root.left), self.get_height(root.right)))
        balance = self.get_balance(root)

        # LL Rotation
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        # RR Rotation
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # LR Rotation
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # RL Rotation
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

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

    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right)))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right)))
        return y

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

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

1.4 优缺点

优点

  • AVL树在查找操作上比红黑树更快，因为它更严格地保持平衡。
  • 在频繁查找的应用场景中，AVL树表现更佳。

缺点

  • 插入和删除操作相对复杂，且需要多次旋转，导致性能下降。
  • 在插入和删除频繁的场景中，AVL树的性能可能不如红黑树。

1.5 注意事项

  • 在实现AVL树时，确保每次插入和删除后都更新节点的高度和进行必要的旋转。
  • 适合查找频繁而插入删除较少的场景。

2. 红黑树

2.1 定义

红黑树是一种自平衡的二叉搜索树，每个节点都有一个颜色属性（红色或黑色），并且遵循以下性质：

  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL或空节点）是黑色。
  4. 如果一个节点是红色，则它的两个子节点必须是黑色（即没有两个红色节点相连）。
  5. 从任何节点到其每个叶子节点的路径都包含相同数量的黑色节点。

2.2 性质

红黑树的性质确保了树的高度不会超过2 * log(n)，从而保证了基本操作的时间复杂度为O(log n)。

2.3 操作

2.3.1 插入

插入操作与普通的二叉搜索树相同，但在插入后需要调整树的结构和颜色以保持红黑树的性质。

调整操作：

  • 重新着色：改变节点的颜色。
  • 旋转：与AVL树类似，红黑树也使用左旋和右旋来调整树的结构。

示例代码（Python）

class RBNode:
    def __init__(self, key):
        self.key = key
        self.color = 'red'  # 新插入的节点是红色
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(0)  # 哨兵节点
        self.NIL.color = 'black'
        self.root = self.NIL

    def insert(self, key):
        new_node = RBNode(key)
        new_node.left = self.NIL
        new_node.right = self.NIL
        self.insert_node(new_node)

    def insert_node(self, node):
        parent = None
        current = self.root

        while current != self.NIL:
            parent = current
            if node.key < current.key:
                current = current.left
            else:
                current = current.right

        node.parent = parent

        if parent is None:
            self.root = node
        elif node.key < parent.key:
            parent.left = node
        else:
            parent.right = node

        node.color = 'red'
        self.fix_insert(node)

    def fix_insert(self, node):
        while node != self.root and node.parent.color == 'red':
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.right:
                        node = node.parent
                        self.left_rotate(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self.right_rotate(node.parent.parent)
            else:
                uncle = node.parent.parent.left
                if uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self.right_rotate(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self.left_rotate(node.parent.parent)

        self.root.color = 'black'

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.NIL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

2.4 优缺点

优点

  • 红黑树的插入和删除操作相对简单，且旋转次数较少。
  • 在插入和删除频繁的场景中，红黑树的性能优于AVL树。

缺点

  • 查找操作的效率略低于AVL树，因为红黑树的平衡性不如AVL树严格。
  • 实现相对复杂，尤其是在处理颜色和旋转时。

2.5 注意事项

  • 在实现红黑树时，确保遵循红黑树的性质，特别是在插入和删除后进行必要的调整。
  • 适合插入和删除频繁的场景。

3. 总结

AVL树和红黑树都是自平衡的二叉搜索树，各有优缺点。AVL树在查找操作上表现更好，而红黑树在插入和删除操作上更为高效。选择合适的平衡树结构应根据具体应用场景的需求来决定。理解它们的实现细节和操作过程是掌握数据结构与算法的关键。希望本文能为你提供深入的理解和实践的基础。

3.2 二叉树及其遍历方法
3.4 图的表示方法（邻接矩阵与邻接表）