平衡树
红黑树本质是对2-3-4树的一种实现。
2-3-4树是阶数为4的B树，B树，全名BalanceTree，平衡树。平衡树主要用来进行查找操作。
平衡树最重要的特性在于平衡，这使得我们能够在最坏情况下也保持O(LogN)的时间复杂度实现查找（一个不具备平衡性的查找树可能退化成单链表，时间复杂度会到O（N））
Note: 平衡的定义是说从空链接到根节点距离相等
2-3-4树存在2节点，3节点和4节点
2-3-4树到平衡树的转化
黄黑树是2-3-4树的一种实现，以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。
2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。
以下的研究都是是基于2-3树，并且是2-3树中较为特殊的一种转化—左倾红黑树。顾名思义，左倾红黑树限制了如果在树中出现了红色节点，那么这个节点必须是左儿子。
以下是转换过程
Reference
若有收获，就点个赞吧
0 人点赞
