红黑树的应用

  • 10亿数据不到30次比较就可以查找到目标
  • C++ map set
  • JDK1.8 HashMap 冲突的链表长度超过8时，自动转为红黑树
  • Linux底层的CFS进程调度算法，vruntime使用红黑树进行存储
  • 多路复用技术的Epoll，核心结构是红黑树+双向链表

二叉查找树BST

  • 左子树上所有结点的值均小于或等于它的根结点的值
  • 右子树上所有结点的值均大于或等于它的根节点的值
  • 左、右子树也分别为二叉排序树

平衡二叉树AVL

  • AVL树中任何节点的两个子树的高度最大差别为1

红黑树

  • 牺牲部分平衡性，以换取插入/删除操作时较少的旋转操作
  • 节点被标记为红色和黑色

红黑树特性

  1. 节点非黑即红
  2. 根节点一定是黑色的
  3. 叶子节点一定是黑色
  4. 每个红色节点的两个子节点都黑色 -> 每个叶子到根的所有路径上不能有两个连续的红色节点
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 -> 如果一个结点存在黑色结点，那么该结点一定有两个子节点

红黑树的插入

一般插入红黑树节点时，会将节点设置为红色，因为红色破坏原则的可能性最小。

  1. 红黑树为空树
    直接把插入结点作为根节点，将插入节点设置为黑色

  2. 插入节点的Key已经存在
    更新当前节点的值为插入节点的值

  3. 插入节点的父节点为黑色
    直接插入无需做自平衡

  4. 插入节点的父节点为红色
    此时，因为因为根节点必须是黑色节点，所以父节点一定不是根节点。此时会出现两种情况。

4.1 父亲和叔叔为红色
将P和S设置为黑色，将PP设置为红色，把PP设置为当前插入结点

4.2 父亲为红色，叔叔为黑色
4.2.1 父亲结点是祖父结点的左子结点 & 插入结点是父节点的左子结点
将P设置为黑色，将PP设置为红色，对PP进行右旋
4.2.2 父亲结点是祖父结点的左子结点 & 插入结点是父节点的左子结点
对P进行左旋，把P设置为插入结点，得到情景4.2.1，进行4.2.1的处理

红黑树恢复平衡的三个操作

  • 变色
  • 左旋
  • 右旋