当前位置: 代码迷 >> 综合 >> 红黑树学习tips
  详细解决方案

红黑树学习tips

热度:13   发布时间:2024-01-15 21:14:02.0

内存中的索引通常采用BST、红黑树,外存中通常采用B树、B+树

BST对于检索来说,有个大的缺点是它不一定平衡。如果对于一个已排序的数列建BST,BST会退化成一个斜着的链表。为了解决“平衡”的问题,比较常见的有AVL树和红黑树。

红黑树 即是一棵 平衡的 扩充 二叉搜索树


颜色特征:结点 红 或 黑;根和扩充的外部空叶结点都是黑色

内部特征:红 结点的两个子节点都是 黑 的,不允许连续的 红 结点

深度特征:任何结点到其叶子结点的每条简单路径都包含相同数目的 黑 结点


阶为k的红黑树路径长度 最短是k ,最长是2k (阶 : 黑色高度)

黑色 起到一个阶的控制作用


插入算法

· 先调用BST的插入算法

- 把新纪录着色为 红

- 若父结点是黑色,则算法结束

· 否则,双红调整


插入算法调整1:重构

· 情况1:新增结点 X 的 叔叔 是 黑色

以祖父结点为轴旋转父结点

插入算法调整2:换色

· 情况2:新增结点X的 叔叔 也是 红色

父祖换色