平衡查找树

一、2-3 查找树

1. 定义：
   • 2-结点：含1个键和2条链接。
   • 3-结点：含2个键和3条链接（左、中、右链接分别对应键区间）。
   • 2-3树是完美平衡的，所有空链接到根结点的距离相等。
2. 查找：
   • 将键与根结点比较，命中则返回，未命中则根据区间递归查找子树。
3. 插入：
   • 向2-结点插入：直接替换为3-结点，保持平衡。
   • 向3-结点插入：
     • 创建临时4-结点（3键4链接），分解为3个2-结点（树高+1）或将中键插入父结点。
     • 若父结点为2-结点，变为3-结点；若为3-结点，继续分解并向上传递。
   • 分解根结点：若根为4-结点，分解为3个2-结点，树高+1。
4. 局部变换：
   • 分解4-结点的6种情况（根、2-结点的左右子、3-结点的左中右子）。
   • 变换局部，不影响全局有序性和平衡性。
5. 性能：
   • 大小为N的2-3树，查找和插入访问结点不超过lgN。

二、红黑二叉查找树

1. 基本思想：
   • 用标准二叉查找树（2-结点）表示2-3树，红链接连接两个2-结点表示3-结点，黑链接为普通链接。
2. 定义：
   • 红链接为左链接，无结点连两条红链接，树完美黑色平衡（黑链接路径数相同）。
   • 与2-3树一一对应。
3. 操作：
   • 旋转：
     • 左旋转：将红色右链接转为左链接。
     • 右旋转：将红色左链接调整方向。
     • 保持有序性和平衡性，返回新根链接。
   • 颜色转换：左右子结点红变黑，父结点黑变红，局部变换不影响黑色平衡。
   • 根结点：插入后始终设为黑色，黑色高度可能+1。
4. 插入：
   • 向2-结点插入：新键用红链接连接，若为右链接则左旋转。
   • 向3-结点插入：
     • 形成临时4-结点，根据新键位置（最小、介中、最大）进行旋转和颜色转换。
     • 红链接向上传递至2-结点或根。
   • 核心步骤：
     • 右红左黑 → 左旋转。
     • 左红且左子红 → 右旋转。
     • 左右皆红 → 颜色转换。
5. 实现：
   • 算法3.4：递归插入后执行旋转和颜色转换，代码简洁但需理解2-3树和红黑树的对应。

三、删除操作

1. 概述：
   • 删除比插入复杂，需沿路径向下构造4-结点，向上分解剩余4-结点。
2. 2-3-4树：
   • 允许4-结点，插入时向下分解4-结点，向上配平。
   • 红黑树实现：4-结点用红链接表示，调整颜色转换位置。
3. 删除最小键：
   • 确保不删2-结点，沿左链接向下变换：
     • 根为2-结点且子为2-结点，合并为4-结点。
     • 左子为2-结点，从兄弟借键或合并为4-结点。
   • 删除后向上分解4-结点。
4. 通用删除：
   • 查找路径上避免2-结点，键不在底部则与后继交换，转化为删除最小键。

四、红黑树性质

1. 性能分析：
   • 命题G：高度不超过2lgN（最坏情况：最左路径全3-结点）。
   • 命题H：平均路径长度~1.00lgN，查找成本比BST低约40%。
   • 实验验证：随机键下比较次数约为1.00lgN-0.5。
2. 符号表API：
   • 命题I：所有操作（除范围查询外）最坏情况为对数级别。
   • 得益于近乎完美平衡，查找、插入、删除等均高效。
3. 对比：
   • 红黑树结合BST的简洁查找和2-3树的平衡插入，是首个保证对数级别查找和插入的紧凑实现。