前置知识：

二叉查找(搜索)树 BST

【特点】
1.根节点左边比根节点小，根节点右边比根节点大。
2.中序遍历有序。

【查找操作】
查找值比当前值大，则搜右子树
查找值比当前值小，则搜左子树

【插入操作】
要插入的节点必须先找到插入的位置，从根节点开始比较，小就和左子树比较，反之和右子树比较，知道左子树为空或者右子树为空，则插入到相应为空的位置。

【查找最小/大值】红黑树通用
沿着根节点一直查找左/右子树，直到最后一个不为空的节点。

【查找前驱结点】红黑树通用
小于当前节点的最大值

【查找后继节点】红黑树通用
大于当前节点的最小值

【删除操作】本质上是找前去或者后继节点来替代
叶子结点：直接删除。
只有一个子节点：用子节点代替。
有两个子节点的：需要找到替代节点(前驱节点或者后继节点)。
删除操作和红黑树一样，只不过红黑树多了着色和旋转的过程。

BST的最大问题：树的高度会变得非常高。可能会退化成链表。

平衡查找二叉树(Balanced BST)

在插入和删除的时候，会通过旋转操作将高度保持在logN。
两个代表性的平衡树分别为AVL树(左右子树高度差不超过1)和红黑树。

问：为什么不用AVL？
AVL条件苛刻，实现复杂，插入和删除引入的旋转操作开销非常大。红黑树只需保证黑色节点平衡。

红黑树来源于2-3-4树。

2-3-4树

2-3-4树是四阶的B树，
限制如下：

所有叶子结点都拥有相同的深度。
叶节点只能是2-节点、3-节点、4-节点之一。

  • 2-节点：包含1个元素的节点，有2个子节点；
  • 3-节点：包含2个元素的节点，有3个子节点；
  • 4-节点：包含3个元素的节点，有4个子节点；
  • 所有节点至少包含一个元素

一个2-3-4树对应多个红黑树。
image.png

红黑树

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

image.png
image.png

红黑树五大原性质：

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 所有叶子结点都是黑色(包括为null的节点)
  4. 每个红色节点必须有两个黑色子节点
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的查询、插入、删除操作时间复杂度为O(logN)。

常见操作
【右旋】
以某个节点作为旋转点，其左子节点变为旋转点的父节点，左子节点的有有右子节点变为旋转节点的左子节点，其他保持不变。

【左旋】
以某个节点作为旋转点，其右子节点变为旋转点的父节点，右子节点的左子节点变为旋转节点的右子节点，其他保持不变。

【新增】