红黑树的前世今生

红黑树本质还是解决排序问题，并且它在插入和删除节点方面有效率优势。
线性结构搜索时间复杂度: O(n)
有序的线性结构搜索的时间复杂度是O(logn) 但是插入、删除的时候需要移动大量元素，比较费时。

• BST(binary search tree)二叉排序树: 查找时间复杂度为O(logn), 删除或添加不需要移动大量元素
  1）左子树不空，则左子树结点小于根节点
  2）右子树不空，右子树结点大于根节点
  3）左右子树也分别为二叉排序树

• AVL(平衡二叉树): 是在BST的基础上引入平衡性，即从根节点开始，建树的时候必须满足左右子树的高度差小于1. 这样AVL的查找时间复杂度一定是树的高度也就是O(logn), 而不会因为异常情况而退化为O(n)

• RBT(Red-Black Tree) 红黑树: 主要是为克服AVL树在插入元素的时候，当左右子树的高度差被破坏的时候就需要不停的左旋右旋，非常耗费时间，因此引入红黑树(又叫self-balanced search tree)。

• RBT和AVL的特点对比：
  

  对比.png
  当需要插入和删除节点的时候，RBT相较于AVL只需要更少的旋转。但是RBT在平衡性上并没有那么平衡，因此当处于搜索多而插入删除少的时候，适合用AVL；而当搜索没那么多插入删除多的时候适合用RBT。

• 红黑树定义

1. 每一个结点要么是红色，要么是黑色。
2. 根结点是黑色的。
3. 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信息，所有查询关键字都在非终结点上。
4. 每个红色结点的两个子节点必须是黑色的。换句话说：从每个叶子到根的所有路径上不能有两个连续的红色结点

5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

   
   image.png

• 相关定理
  1）从根到叶子的最长的可能路径不对于最短的可能路径的两倍长。
  2）红黑树的树高(h) 不大于两倍的红黑树的黑深度(bd), 即 h<=2bd;

3. 一颗拥有n个内部结点(不包括叶子结点)的红黑树的数高最多为2O(log(n+1)), 近似也为log(n)

参考:
1 红黑树相关定理证明
2 2021年最好懂的红黑树