二叉搜索树BST与平衡

算法二叉树 BST

算法

发布日期: 2024-09-07

作者: 小乐

文章字数: 839

阅读时长: 3 分

阅读次数:

一、二叉搜索树定义

1.1 核心性质

对于任意节点：

左子树所有节点值 < 当前节点值
右子树所有节点值 > 当前节点值
左右子树也是二叉搜索树

1.2 中序遍历特性

BST的中序遍历结果是有序序列。

二、BST基本操作

2.1 查找

public TreeNode search(TreeNode root, int target) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.val == target) return curr;
        if (target < curr.val) curr = curr.left;
        else curr = curr.right;
    }
    return null;
}

时间复杂度：( O(h) )，( h ) 为树高

2.2 插入

public TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    }
    return root;
}

2.3 删除（最复杂）

三种情况：

叶子节点：直接删除
只有一个子节点：子节点替代
有两个子节点：找后继（右子树最小值）或前驱（左子树最大值）替代

public TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        // 找到要删除的节点
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // 两个子节点：找后继
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = delete(root.right, minNode.val);
    }
    return root;
}

TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

三、BST的问题 - 退化成链表

3.1 最坏情况

按顺序插入 1, 2, 3, 4, 5：

树高 = ( n )，查找退化为 ( O(n) )

3.2 平均情况

随机插入，期望树高 ( O(\log n) )

四、平衡二叉树

4.1 平衡因子

[ \text{平衡因子} = \text{左子树高度} - \text{右子树高度} ]

平衡二叉树要求：( |平衡因子| \leq 1 )

4.2 为什么需要平衡

保持树高 ( O(\log n) )，确保操作效率。

五、AVL树

5.1 定义

严格的平衡二叉树，任何节点的平衡因子绝对值不超过1。

5.2 旋转操作

左旋（右右情况）：

  y              x
 / \            / \
T1  x    →     y  T3
   / \        / \
  T2 T3      T1 T2

右旋（左左情况）：

    x           y
   / \         / \
  y  T3  →   T1  x
 / \            / \
T1 T2          T2 T3

左右旋（左右情况）：先左旋再右旋
右左旋（右左情况）：先右旋再左旋

5.3 旋转的Java实现

// 右旋
TreeNode rightRotate(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;
    
    x.right = y;
    y.left = T2;
    
    // 更新高度
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    
    return x;
}

// 左旋
TreeNode leftRotate(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;
    
    y.left = x;
    x.right = T2;
    
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    
    return y;
}

六、Treap - 树堆

6.1 核心思想

结合BST和堆：

键值满足BST性质
优先级满足堆性质（随机生成）

6.2 期望树高

由于优先级随机，期望树高 ( O(\log n) )。

七、总结

特性	普通BST	AVL树
查找	( O(h) )	( O(\log n) )
插入	( O(h) )	( O(\log n) )
删除	( O(h) )	( O(\log n) )
平衡维护	无	旋转
实现复杂度	简单	较复杂
适用场景	数据随机	频繁增删查