• 每个节点或者是红色的，或者是黑色的
  • 根节点是黑色的 (2节点或3节点)
  • 每一个叶子节点(最后的空节点)是黑色的
  • 如果一个节点是红色的，那么他的孩子节点都是黑色的
    • 黑色节点的右孩子一定是黑色的
  • 从任意一个节点到叶子节点，经过的黑色节点是一样的

**

  • 红黑树是黑平衡的二叉树。严格意义不是平衡二叉树。
  • 最大高度2log n
  • 红黑树增加和删除节点的时间复杂度为log n
  • 红黑树的添加和删除操作会比AVL要快一些，AVL的查询操作要比红黑树要快一些
  • 如果需要经常增删数据，推荐使用红黑树
  • 如果数据基本保持不变，推荐使用AVL


image.png

2-3树与红黑树的等价关系

红色表示特殊的边，表示其在2-3树中属于同一个3节点
image.png
因为用红色边来表示不好维护，所以把这个信息放到b这个红色节点中，来表示它和它的父节点 在2-3树中属于同一个三节点。 :::tips 因为这个信息，红黑树中所有的**红色节点都是向左**倾斜的(是定义出来的，而不是推导出来的) ::: image.png

image.png

image.png

红黑树添加新元素

永远添加的是红色节点

添加第一个元素

image.png
由于要求根节点必须是黑色的，所以还需要将这个节点改成黑色。

image.png

1.左旋转

image.png
image.png

image.png
image.png
新的根节点要跟原来的根节点颜色一致。
image.png

2.颜色翻转

image.png
拆分后他们不再是一个三节点，所以不再是红色。
image.png
因为42要继续上浮去跟它的父节点融合，所以要标成红色
image.png

3.右旋转

image.png
image.png
新的根节点要跟原来的根节点颜色一致
image.png
又因为现在这三个节点还是融合在一起的，所以42要变成红色
image.png
继续颜色翻转，37上浮成红色，12，42断开成黑色
image.png

LR

image.png
image.png
image.png
image.png

添加元素总结

  • 维护的时机:和AVL树一样
  • 添加节点后回溯向上维护

image.png
image.png