红黑树 笔记

普通的二叉查找树在极端情况下可退化成链表,此时的增删查效率都会比较低下。红黑树基于二叉查找树,根据下面5个性质限制,达到平衡状态。


5条性质:

  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶节点(空节点)是黑色的。
  4. 所有路径上不能有两个连续的红色节点。
  5. 所有路径都包含相同数目的黑色节点。

注意:

  • 性质 4、5:有了这两个性质作为约束,即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的 2 倍
  • 最短路径:所有节点都是黑色
  • 最长路径:红黑相间
  • 基于二叉查找树,左旋右旋不会改变元素相对顺序
  • 在插入新节点时,节点应是红色,因为路径节点数应相等,不好调整
  • 为避免连续红色,需要染色,从下到上递归