小皮博客 | Xiaopi's Blog

57-从2-3-4树的角度理解红黑树-1

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树示意图

图1 2-3-4树的示意图

2-3-4树查找

和BST树类似,递归找到所在子树即可。

  • Compare search key against keys in node.(与节点中的key比较)
  • Find interval containing search key.(查找包含待查找关键字的区间)
  • Follow associated link (recursively).(递归直到找到值为止)
    2-3-4树查找示意图

    图2 2-3-4树的查找

2-3-4树插入

先查找到树的底部


图3 2-3-4树的插入-先查找到底部

在底部插入key。


图4 2-3-4树的插入-插入数据 2-Node变为3-Node

同理,3-Node转换为4-Node即可。(后面删除的时候同样会逆向得出,4-Node直接删成3-Node即可,3-Node直接删成2-Node即可)。这里不演示图片了。

向4-Node插入,则变换,将4-Node的中间节点向上移动到父节点。假如父节点也是4-Node呢?继续上移吗?为了性质简单器件,目前的做法是保证不会连续出现两个连续的4-Node。即一个4-Node节点不会有一个4-Node的儿子。


图5 2-3-4树的插入-插入数据 4-Node

简单的情况,将4-Node的中间节点向上移动。


图6 2-3-4树的插入-插入数据 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,好像也是可以的。但是仍然要递归操作的样子。


图7 2-3-4树的插入-插入数据 4-Node情形下的预先准备工作

先看简单的情况,is a local transformation that works anywhere in the tree


图8 2-3-4树的插入-插入数据 4-Node的父节点是2-Node

图9 2-3-4树的插入-插入数据 4-Node的父节点是3-Node

2-3-4树的构建过程

  • 参考前面的插入逻辑.

    图10 2-3-4树的简单构建过程
    .

图11 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树的优点,同时便于实现,也就出现了红黑树。


图12 红黑树的简图

图13 用一条特殊的边,将3,4节点之间内部用连线链接起来,放到树里面

这样,原来本来黑色的边并没有变,所以每条路径上黑色的边都是一样多的。

关键点:
• 仍然保持二叉查找树(BST)的特性。
• easy to maintain a correspondence with 2-3-4 trees
(and several other types of balanced trees)


图14 一个稍微复杂点的情况

由于3-Node节点有两种选择,如前文提到的,我们这里约束为,Left-leaning,这样也就确定了2-3-4树转换为红黑树的形态。同时还需要做的是将同一个路径上连续两个连续的红边调整好。


图15 连续两条红边的情况

红黑树节点的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。


图16 2-Node和3-Node插入及调整的情况说明

重点待解决问题: 这里是用红色或者黑色描述边,但是实际上最后颜色属性是在Node也就是点上,考虑到一个父节点对应两个字节点,也就是说,每个节点的Color决定的是其到父亲的那条边的颜色。
应该叫做toParentLineColor,而不是NodeColor.
更加引申的推论是,如果父节点只有一个儿子的情况,那就可以把儿子由红色变成黑色,父亲变成红色(这样黑色路径的数量才不会变)。而如果父节点有两个儿子,则他变成红色的情况,有且只有两个儿子都为红色的变成黑色的情况,这样才能维护黑色边的balance。

当插入到一个4-Node中时,需要分析其父节点的情况。

父节点为2-Node:


图17 要插入位置为4-Node且父节点为2-Node时插入及调整的情况说明

父节点为3-Node:


图18 要插入位置为4-Node且父节点为3-Node时插入及调整的情况说明

所以整个插入流程归纳一下:
待插入位置为2-Node或者3-Node的时候,直接插入,待插入节点为4-Node的时候,经过上述调整后,进行操作。


图19 要插入位置为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

盛领 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!