定义

我们希望有一种数据结构，既能保持有序性（方便范围查询），又能支持高效率的动态插入和删除。

利用了二叉树的层级结构分割搜索空间。每一步比较键值后，只需进入左或右子树，像二分搜索一样缩小范围。因此，查找、插入、删除的时间复杂度与树高h成正比。理想情况下，h约为log n，操作复杂度为O(log n)。

2. BST 的核心思想

利用二叉树的层级结构分割搜索空间。

每一步比较键值后，只需进入左或右子树，像二分搜索一样缩小范围。

因此查找、插入、删除的时间复杂度与树高 h 成正比。

理想情况：h ≈ log₂n，操作复杂度 O(log n)。

3. 不平衡问题 → 平衡树的出现

若插入顺序不当（如升序），树退化为链表，h = n，复杂度退化为 O(n)。

为防止退化，出现了平衡二叉搜索树（AVL、红黑树、Treap、Splay等）。

这些树的共同目标：保持树高为 O(log n)，从而保证性能稳定。

平衡

BST 的性能取决于树高 h：

理想：树高 ≈ log₂n → 操作 O(log n)

最坏：退化为链表 → 操作 O(n)

因此，控制树的高度 成为关键目标。 为此出现了“平衡二叉搜索树”（Balanced BST）。

2. 平衡树的思想

平衡树的核心思想：

在插入或删除节点后，通过一定的“调整机制”保持树结构的近似对称，使得高度保持在 O(log n)。

不同平衡树的区别就在于平衡标准与调整方式。

3. 主要平衡二叉树类型对比 树种类 平衡标准 调整方式 特点 AVL树 任意节点左右子树高度差 ≤ 1 旋转（单旋/双旋） 严格平衡，查找快，插删慢 红黑树 基于颜色的黑高平衡 颜色翻转 + 旋转 近似平衡，插删快 Treap 利用随机优先级平衡 类堆性质旋转 简单、随机平衡 Splay树 通过访问频率“自调整” 旋转到根 无需显式平衡，常用于缓存