2-3-4树是一个不太广泛应用的数据结构，但是可以帮助我们更好的理解红黑树。
参考来自于普林斯顿大学计算机学院资料-红黑树.pdf
2-3-4树说明
BST是二叉查找树,每个节点只能有一个Key, 而2-3-4树则是将节点的key增加,可以有多个key。(2-3-4树可以保持完美平衡，每个节点到叶节点的高度一致)。
2-3-4树的节点种类
2-Node: one key, two child.左孩子比key小,右孩子比key大。
3-Node: two keys, three children. 左孩子比左key小，中孩子大于左key小于右key(显然右key大于左key)，右孩子大于右key。
4-Node: three keys, four children. 同理。
2-3-4树查找
和BST树类似,递归找到所在子树即可。
- Compare search key against keys in node.(与节点中的key比较)
- Find interval containing search key.(查找包含待查找关键字的区间)
- Follow associated link (recursively).(递归直到找到值为止)
图2 2-3-4树的查找
2-3-4树插入
先查找到树的底部
在底部插入key。
同理，3-Node转换为4-Node即可。(后面删除的时候同样会逆向得出,4-Node直接删成3-Node即可,3-Node直接删成2-Node即可)。这里不演示图片了。
向4-Node插入，则变换,将4-Node的中间节点向上移动到父节点。假如父节点也是4-Node呢?继续上移吗?为了性质简单器件，目前的做法是保证不会连续出现两个连续的4-Node。即一个4-Node节点不会有一个4-Node的儿子。
简单的情况,将4-Node的中间节点向上移动。
参考文献中提到如何解决4-Node插入的问题。
Bottom-up solution (Bayer, 1972).
• Use same method to split parent
• Continue up the tree while necessary.
Top-down solution (Guibas-Sedgewick, 1978).
• Split 4-nodes on the way down.
• Insert at bottom.
论文原文的字面含义应该是说遇到4-Node的情况就先变换掉。但是好像还是略过了父节点是4-Node,子节点是3-Node的情况应该怎么变换。也许是说递归的,2-4的父子结构转换成3-2/2的父子结构,3-4的父子结构转换成4-2/2的父子结构,转换完了之后递归往上，看转换后的4是不是需要调整吧。
当然，理论上其实如果保证叶子节点不会出现4-Node，好像也是可以的。但是仍然要递归操作的样子。
先看简单的情况,is a local transformation that works anywhere in the tree
2-3-4树的构建过程
- 参考前面的插入逻辑.
图10 2-3-4树的简单构建过程 .
所有根节点的高度始终在保持一致。其实相当于把不一致的可能性糅合到了2-3-4节点当中。
树的高度:
• 最坏情况: lgN [都是2-Node,退化成2叉树].
• 最好的情况: log4 N = 1/2 lg N [都是4-Node].
• 100万数据的情况下高度在10~20之间。
• 10亿数据的高度在15~30之间。
可以保证保证搜索和插入的对数性能。
RedBlackTree和2-3-4树的关系
由于2-3-4树实现起来较为复杂，所以将其表示为二叉树并且做更多的约束以使其具备2-3-4树的优点，同时便于实现，也就出现了红黑树。
这样，原来本来黑色的边并没有变，所以每条路径上黑色的边都是一样多的。
关键点:
• 仍然保持二叉查找树(BST)的特性。
• easy to maintain a correspondence with 2-3-4 trees
(and several other types of balanced trees)
由于3-Node节点有两种选择，如前文提到的，我们这里约束为，Left-leaning,这样也就确定了2-3-4树转换为红黑树的形态。同时还需要做的是将同一个路径上连续两个连续的红边调整好。
红黑树节点的ADT定义
public class BST, Value> { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; private class Node { Key key; Value val; Node left, right; ***boolean color;*** Node(Key key, Value val, boolean color) { this.key = key; this.val = val; this.color = color; } } public Value get(Key key) // Search method. public void put(Key key, Value val) // Insert method. }
为了保证与2-3-4树一一对应产生红黑树(不会出现二义性).
红黑树的插入操作
添加新节点时和普通BST一致，并且将添加的点和插入的父节点之间的边用红色标记(类似于之前2-3-4树中插入的逻辑).
有必要的时候旋转以获得正确的3-Node或者4-Node。
重点待解决问题: 这里是用红色或者黑色描述边，但是实际上最后颜色属性是在Node也就是点上，考虑到一个父节点对应两个字节点，也就是说，每个节点的Color决定的是其到父亲的那条边的颜色。
应该叫做toParentLineColor,而不是NodeColor.
更加引申的推论是，如果父节点只有一个儿子的情况，那就可以把儿子由红色变成黑色，父亲变成红色(这样黑色路径的数量才不会变)。而如果父节点有两个儿子，则他变成红色的情况，有且只有两个儿子都为红色的变成黑色的情况，这样才能维护黑色边的balance。
当插入到一个4-Node中时,需要分析其父节点的情况。
父节点为2-Node:
父节点为3-Node:
所以整个插入流程归纳一下:
待插入位置为2-Node或者3-Node的时候，直接插入,待插入节点为4-Node的时候，经过上述调整后，进行操作。
private Node insert(Node h, Key key, Value val)
{
if (h == null)
return new Node(key, val, RED);
if (isRed(h.left) && isRed(h.right))
colorFlip(h);
int cmp = key.compareTo(h.key);
if (cmp == 0) h.val = val;
else if (cmp < 0)
h.left = insert(h.left, key, val);
else
h.right = insert(h.right, key, val);
if (isRed(h.right))
h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left))
h = rotateRight(h);
return h;
}
版权声明
本文标题:57-从2-3-4树的角度理解红黑树-1
文章作者:盛领
发布时间:2018年08月22日 - 13:09:54
原始链接:http://blog.xiaoyuyu.net/post/52ccaeec.html
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。
如您有任何商业合作或者授权方面的协商，请给我留言：sunsetxiao@126.com
