理解红黑树

以下全是根据视频学习后的个人理解和笔记。。。视频链接

红黑树可以理解为由234树演变而来，234树是由二叉查找树演变而来，二叉查找树由二叉树演变来，所以想要了解红黑树要了解二叉树和234树

二叉树

二叉树：即每个子节点只有两个节点的树
二叉查找树:也是一个二叉树，只不过二叉查找树的左节点都比其父节点小，右节点都比父节点大。其高度决定了他的效率
二叉查找树的效率也与插入顺序有关如：
插入顺序为 5、3 、2、4、7、6、8，可以如下所示

但是若插入顺序为 2、3、4、5、6、7、8，则是如下所示

插入的顺序决定了其深度，而深度又决定了查找的效率。(可以将所有的节点投影到X轴上会发现其已经是顺序排列(即将树压平)，如下：)

①查询：查找的时候从根节点开始，当前节点比查找的值小就向右搜索，比查找的值大就向左搜索
②插入：插入的时候也是，从根节点开始与左右子树进行比较，当左子树或右子树为空的时候插入到对应的空位置
③遍历：即左根右（前序遍历）、根左右（中序遍历，常用）、左右根（后序遍历）
前驱节点：当前节点左子树中的最大值
后驱节点：当前节点右子树中的最小值
如上图1所示，5的前驱节点是4，后驱节点是6
④删除：删除当前节点的话则使用该节点的前驱节点或者后驱节点代替(即将树压平后该节点相邻的节点)。若没有前驱节点和后驱节点直接删除即可

avl树

由上述的二叉查找树可知，其插入顺序不一样会导致其查找效率不同。最坏的情况下相当于一个链表。
基于该问题，出现了平衡查找二叉树，平衡树插入和删除的时候，会通过旋转来将高度保持在LogN。其中具有代表性的平衡树有avl树和红黑树
avl树 是高度平衡树，具备二叉搜索树的全部性质，其左右子树的高度差不超过 1 .
①如何旋转：当左右子树高度差高过一的时候进行左旋或者右旋，如下所示

旋转前

右旋后

旋转前

右旋后

2-3-4树

2-3-4树是四阶的B树,(即最多有四个子节点),属于一种多路查找树.
其所有的叶子结点都拥有相同的深度.节点只能是2节点,3节点,4节点之一
2节点:包含一个元素的节点,有两个子节点.

3节点:包含两个元素的节点.有三个子节点

4节点:包含三个元素的节点,有四个子节点

所有节点至少必须包含一个元素

二三四树保持着二叉查找树的性质,但是其用代码实现起来不方便,所以一般使用它同等的红黑树
典型的2-3-4树,如下所示

二三四树的插入和二叉查找树不同(二叉查找树是从顶部向下插入),二三四树是从底部向上插入.他会先满足四节点,再向三节点和二节点演化.
如:插入过程如下:
先插入2

再插入 3

再插入 4

这时候的 2,3,4已经满足了四节点
再插入5
由于当前已经满足四节点所以再次插入的时候会将以前的四节点从中间拆散,中间的数向上提,插入的数和并起来,如下图所示

再插入 6 , 现在会先根据二叉查找树的性质,即左子树小于当前节点,右子树大于当前节点,找到合适的位置后插入,如下

再插入 7 ,过程如下

再插入 8

再插入 9

再插入10

再插入 11

将其压平后

红黑树

红黑树起源于二三四树，本质就是二三四树
其对应关系如下所示：

概念：红黑树是一种节点带有颜色属性的二叉查找树。有如下性质

• 节点是红色或者黑色
• 根是黑色
• 所有叶子节点都是黑色
• 每个红色节点必须有两个黑色子节点
• 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点

常见操作：

• 变色 ：节点由黑变红或者由红变黑
• 旋转：
  1. 右旋：以某个节点A作为旋转点，A节点的左子节点变为父节点，左子节点的右子节点变为A节点的左子节点，右子节点保持不变。
     
  2. 左旋：以某个节点A作为旋转节点，A节点的右子节点作为父节点，右子节点的左子节点变为A节点的右子节点，左子节点保持不变。（图可以看作右旋反过来即可）
• 插入
  插入节点：
  情况以及对比2-3-4树图示：

1. 当是第一个节点，不需要合并的时候
   

2. 再新增一个节点，即为两个节点的时候
   

3. 再新增一个节点，即为三个节点的时候
   

4. 再新增一个节点，即为四个节点的时候，此时需要分裂
   

• 删除
  删除节点

删除节点就是将这个节点的前驱节点或者后驱节点的值赋给给节点，即替换该节点，然后再删除前驱节点或者后驱节点。