平衡二叉树

平衡二叉树也叫做AVL树，任意一个节点的左右子树高度之差不超过1

2-3-4树

2-3-4树不属于二叉树 一个2-3-4树可以对应多个红黑树，但一个红黑树只对应一个2-3-4树

性质：

  • 所有叶子结点的高度相同

  • 节点的类型必须是2节点、3节点、4节点

    • 2节点就是节点中只有1个元素，有2个子节点

    • 3节点就是节点中只有2个元素，有3个子节点

    • 4节点就是节点中只有3个元素，有4个子节点

2-3-4树的构造

2-3-4树是从下往上生长。这里我们以数组{1,2,3,4,5,6,7,8,9}为例子，来描述一下构造的主要过程。新节点的插入都是进行结合操作，结合后进行调整。

  1. 最开始元素1成为根节点，节点类型属于2节点。
  2. 元素2寻找插入位置，是元素1的右边，那么元素2就会元素1结合，此处由于结合后是3节点类型，不需要进行其他操作。
  3. 元素3寻找插入位置，是元素2的右边，那么元素3与元素1和元素2结合形成了一个4节点类型，也是不需要进行其他操作。
  4. 元素4也来了，他也要与元素1、2、3结合在一起，那么这时候就是一个4节点了，不符合2-3-4树，因此进行一次“提升”操作，将原来的4节点中的中间元素往上提升，变成一个2节点左连一个2节点，右连一个3节点。
  5. 元素5也来了，要与元素3、4结合，结合成功。
  6. 元素6也来了，要与元素3、4、5结合，结合和对元素4进行提升，提升的元素4与元素1进行 结合。
  7. ….

image-20230803153020368

image-20230803152954496

image-20230803153059658

image-20230803153304704

image-20230803153348719

image-20230803153633873

image-20230803153736448

image-20230803154247579

image-20230803154321726

image-20230803154850998

总结：

在构造的过程中，就是先一直结合，结合成一个4节点类型，当再过来元素想要结合时，就要将4节点类型进行分裂。分裂的操作就是将原来中间元素提升，剩下的两部分形成一个2型节点和3型节点，而被提升的元素会尝试与它同层的节点也进行相同的结合操作。

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

image-20230803161442907

第四种状态是裂变时的状态，对于红黑树而言，新插入进来的节点都是红节点。

红黑树

红黑树也叫做RBT树，是一种自平衡树，没有平衡树二叉树那样严格的平衡条件。红黑树从2-3-4树演变而来。可以根据2-3-4树倒推红黑树的5条性质

性质推导

因为红黑树可以由2-3-4树演变得来，也就是说2-3-4树满足的性质，也就是红黑树满足的性质。首先，根据2-3-4树的 “叶子节点高度相同”，所以可以推出“从每一个根节点到其所有的叶子节点的路径长度相同”，然后根据我们的上图中2-3-4树节点的等价关系，每一个2-3-4树节点的等价关系都包含了一个黑色节点，由于路径相等，所以每一个根节点到叶子节点的路径上黑色节点个数相等。其他性质也能根据推出，这里不再推了

相互转换

把下面这个红黑树转换成2-3-4树，（N是代表空指针，作为一个黑色叶子节点，一般是不画出来的）

image-20230803163203632

就是找出等价关系中匹配的子树形状，其中14和5是符合3节点类型，所以就是{5,14}，20和25也是符合3节点类型，所以也是{20,25}，所以就

红黑树的删除操作

红黑树的删除操作一定要与2-3-4树进行对应，不然是非常难理解的。这里先再次说明一下2-3-4树的性质

2-3-4树的重要性质

  • 2-3-4树的节点必须是 2节点\3节点\4节点中的类型

  • 2-3-4树一定是一颗完全树，每个节点必须满足它的要求（除开叶子结点外），即2节点就必须有两个孩子，3节点就必须有三个孩子….。且叶子节点全部在同一高度

  • 2-3-4树与红黑树的对应关系 中，一个2-3-4树节点有且仅有一个黑色节点。
  • 2-3-4树与红黑树的对应关系中，黑色节点一定是在红色节点之上
  • 2-3-4树的插入操作一定是在叶子节点上插入，因为它是往上长的，只有底下先变成4节点类型，才会把节点中间元素往上挤

思路（有重点）

黑红树节点的删除是通过寻找被删除节点的前驱节点或者后继节点 ，是用前驱或后继节点替代被删除的节点。但是我们需要先对被删除节点进行以下情况分析。包括以下情况

  • 被删除节点没有左右孩子。
  • 被删除节点只有一个孩子
  • 被删除节点有两个孩子

前两种的删除操作其实并不难，没有孩子的节点直接删除。有一个孩子的节点，把节点删了后，用子节点顶替被删了的父节点即可。而有两个孩子就不好搞了，这就要找前驱或者后继了。而前驱节点或者后继节点有什么性质？显然前驱节点和后继节点就是前两种情况！所以我们需要先将有两个孩子的情况处理一下，找到后继节点其实情况就统一了，就是删除没有孩子的节点或者有一个孩子的节点。

最开始提到过，红黑树的删除操作是要对比2-3-4树的。既然我们明确了要删什么节点，那么我们可以在进一步分析一下下面这个问题。

红黑树中只有一个孩子的节点，在2-3-4树中是个什么情况？ 没有孩子的节点呢？

根据我最开始说的2-3-4树的性质，2-3-4树中除了叶子节点，每个节点的孩子数量满足节点类型，所以，红黑树中没有孩子的节点只可能出现在2-3-4树叶子节点的2型、3型、4型节点中。而一个孩子的节点，只能出现在2-3-4树叶子结点的3型节点中。

如果实在想不明白，你就自己画一个2-3-4树，然后转换成红黑树，很明显叶子结点的2型、3型和4型都会出现单独的一个节点，而3型才会出现只有一个孩子的节点的情况。

单纯删掉节点删除容易，但是要确保红黑树平衡却不简单，我们继续分析以下问题

没有孩子的节点，颜色有哪些情况？

这个其实还简单，根据上一个问题的分析，1型和4型才会出现无孩子节点的情况，其中1型节点本就规定是黑色，而4型节点是上面一个黑色，两边各一个且都是红色。所以没有孩子的节点 有红黑两种情况

只有一个孩子的节点，颜色情况有哪些？

这个同理，只有3型节点，上黑下红，肯定就是上面那个黑的了，所以只有黑色情况

删掉哪种类型节点破坏平衡？

红黑树平衡是指黑色节点的平衡，删掉了黑色节点属于破坏平衡。

分析到这里就差不多可以开始写代码了 再补充一个其他知识，要把红黑树变成2-3-4树，只需要把红色节点提到它的父节点上就行

待续。。。

后继：

  • 没有孩子
    • 红色叶子 不用修改
    • 黑夜叶子 找兄弟借
  • 有孩子 （只能是右孩子，但是不重要 重要的是与2-3-4数进行对应）
    • 只有一个孩子的节点

原来：

  • 有孩子

    • 左孩子
  • 右边孩子