平衡二叉搜索树（Balanced BST）全面详解

平衡二叉搜索树（Balanced BST）全面详解

一、引言：二叉搜索树的困境与平衡树的诞生

在计算机科学的数据结构与算法领域，二叉搜索树（Binary Search Tree, BST）是一种基础且核心的数据结构，它为数据的查找、插入、删除操作提供了一种高效的组织方式。二叉搜索树的核心性质可以概括为三点：

在理想情况下，二叉搜索树呈现完全二叉树的形态，此时树的高度为 $O(\log n)$（其中 $n$ 为树中节点的总数），查找、插入、删除这三大核心操作的时间复杂度也均为 $O(\log n)$。这一效率在大规模数据处理场景中至关重要，因为它意味着数据量翻倍时，操作的耗时仅会小幅增加，能够很好地支撑高并发、大数据量的业务需求。

但现实场景中，二叉搜索树的表现却极易出现“滑铁卢”——当我们依次插入一组有序数据（无论是升序如 1、2、3、4、5、6、7，还是降序如 7、6、5、4、3、2、1）时，二叉搜索树会直接退化为一条单链。此时树的高度不再是对数级，而是变为 $O(n)$，所有核心操作的时间复杂度也随之退化为 $O(n)$。这一情况下，二叉搜索树的性能不仅无法与哈希表等高效数据结构抗衡，甚至与普通的数组、链表相比也毫无优势可言，反而在删除操作中因为需要维护节点的父子指针关系，显得更为繁琐和低效。

举一个具体的场景例子：假设我们需要用二叉搜索树存储100万个有序用户ID，若直接依次插入，树会退化为单链。此时要查找最后一个用户ID，需要从根节点开始逐个遍历，直到链尾，需要执行100万次比较操作，这在实时响应的业务系统中是完全无法接受的。

为了解决二叉搜索树的“失衡”痛点，平衡二叉搜索树（Balanced Binary Search Tree，简称平衡树）应运而生。平衡树并不是一种单一的数据结构，而是一个具有共同特性的“数据结构家族”，其核心设计思想是：在严格遵守二叉搜索树核心性质的前提下，通过一套特定的自调整机制（核心为“旋转操作”，辅以节点颜色标记、优先级分配等辅助手段），在每次插入、删除操作导致树的形态发生变化后，主动检测树的平衡状态，若发现失衡则立即进行结构调整，始终将树的高度控制在 $O(\log n)$ 范围内，从而保证查找、插入、删除等核心操作的时间复杂度稳定在 $O(\log n)$，从根本上避免了二叉搜索树的退化问题。

平衡树家族中，最经典、最具代表性的成员包括以下四类，它们各自有着不同的平衡策略、性能特点和应用场景：

本文将以AVL树为核心讲解对象（因其严格平衡的特性，最易帮助读者理解平衡树的核心思想、平衡判定标准和自调整机制），同时辅以红黑树的核心概念和应用场景介绍，全面详解平衡树的定义、核心性质、平衡判定方法、自调整操作、核心流程以及实际应用，帮助读者从理论到认知，彻底掌握平衡树的核心逻辑。

二、平衡树的核心基础：AVL树的定义与平衡判定

2.1 AVL树的严格定义

AVL树是一种严格平衡的二叉搜索树，它在二叉搜索树的基础上，增加了额外的平衡约束条件：对于树中的任意一个节点，其左子树的高度与右子树的高度之差（称为“平衡因子”）的绝对值不超过1。

要理解这一定义，我们首先需要明确两个核心概念：节点的高度和平衡因子。

2.1.1 节点的高度

在AVL树中，节点的高度定义为：从该节点到其最远叶子节点的路径上的节点个数（包含该节点本身和叶子节点）。

这里需要注意区分“节点的高度”和“节点的深度”，这两个概念在数据结构中极易混淆：

• 节点的高度：从当前节点向下到最远叶子节点的路径长度，是一个“自下而上”的统计概念；
• 节点的深度：从根节点向上到当前节点的路径长度，是一个“自上而下”的统计概念，根节点的深度为1（或0，不同定义体系略有差异，本文统一采用节点个数统计，根节点深度为1）。

对于AVL树中的节点，有两个特殊情况需要明确：

举一个简单的例子：一棵仅有根节点的AVL树，根节点的高度为1；若根节点有一个左孩子（叶子节点），则根节点的高度为2，左孩子的高度为1，根节点的右孩子为空节点，高度为0。

2.1.2 平衡因子

AVL树中，节点的平衡因子（Balance Factor，简称BF）的定义为：节点的左子树高度减去右子树高度，即： $$BF(node)=height(left\_subtree)-height(right\_subtree)$$

根据AVL树的平衡约束条件，任意节点的平衡因子只能取三个值：-1、0、1。这三个值对应的节点状态分别为：

当某个节点的平衡因子的绝对值大于1（即$BF\ge 2$或$BF\le -2$）时，说明该节点的左右子树高度差过大，树在该节点附近出现了失衡，此时需要通过旋转操作来调整树的结构，恢复平衡状态。

2.2 AVL树的失衡类型

在AVL树的插入或删除操作中，新节点的插入或原有节点的删除会导致部分节点的子树高度发生变化，进而可能导致节点的平衡因子超出合法范围，引发失衡。根据失衡节点的子树形态，我们可以将AVL树的失衡分为四种基本类型，这四种类型是后续进行旋转调整的基础，必须准确理解和区分。

为了方便描述，我们先定义几个关键节点：

• 失衡节点：记为$A$，即平衡因子绝对值大于1的节点，是调整操作的核心节点；
• 失衡节点的直接子节点：记为$B$，即$A$的左孩子或右孩子，且$B$所在的子树是导致$A$失衡的“偏高子树”；
• 直接子节点的直接子节点：记为$C$，即$B$的左孩子或右孩子，且$C$所在的子树是导致$B$的子树偏高的核心原因。

基于这三个节点的位置关系，AVL树的四种失衡类型如下：

2.2.1 左左型（LL型）

左左型失衡是最基础、最简单的失衡类型，其核心特征为：

简单概括：$A$左偏，$B$也左偏，即失衡节点的左孩子的左子树偏高，因此称为左左型（LL型）。

例如：现有一棵AVL树，节点依次为3（根节点）、2（3的左孩子）、1（2的左孩子）。此时若插入节点0作为1的左孩子，节点1的高度变为2，节点2的高度变为3，节点3的左子树高度为3，右子树高度为1（空节点高度为0，无右孩子），平衡因子为2，节点3成为失衡节点，且满足$A$（3）左偏、$B$（2）左偏的特征，属于LL型失衡。

2.2.2 右右型（RR型）

右右型失衡是左左型失衡的镜像，其核心特征为：

简单概括：$A$右偏，$B$也右偏，即失衡节点的右孩子的右子树偏高，因此称为右右型（RR型）。

例如：现有一棵AVL树，节点依次为1（根节点）、2（1的右孩子）、3（2的右孩子）。此时若插入节点4作为3的右孩子，节点3的高度变为2，节点2的高度变为3，节点1的右子树高度为3，左子树高度为1，平衡因子为-2，节点1成为失衡节点，且满足AA