二叉树怎么转化为红黑树,红黑树和平衡二叉树区别

5.2 4- 节点插入

如果待插入的节点是个 4- 节点，那么应该先分裂该节点然后再插入。一个 4- 节点可以分裂成一个根节点和两个子节点（这三个节点各含一个 key ）然后在子节点中插入，我们把分裂形成的根节点中的 key 看成向上层插入的 key ，然后重复 5.1 和 5.2 。

图解：

5.3 根节点分裂

如果是在 4 节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则 2-3-4 树会生长一层。

图解：