发表文章

[最新] 从二叉查找树、2-3树彻底理解红黑树

u013565163 1月前 0

从二叉查找树、2-3树彻底理解红黑树

引言

在学习红黑树的时候,看了很多文章,发现都没有讲明白红黑树的原理,只是简单列了红黑树的几条规则,就开始讲解红黑树的插入,让人一直不知其所以然。也很难深刻的理解红黑树。
最后翻起了《算法》这本书,仔细了解了二叉树查找树、2-3树、红黑树,才明白了红黑树不是平白无故产生的,而是符合科学的发展观念是循序渐进,站在巨人的肩旁上发展起来的。

这也是我们从学生时代的填鸭式的学习方式的转变,不仅仅是只学习结论,并且要了解结论产生的历史及发展。
这样我们才能从搬砖、码农成长为工程师、科学家。

数据结构的演进

一位计算机科学的大牛说过:

程序 = 数据结构 + 算法

数据结构是为了减少查询、删除的时间复杂度和空间复杂度。

链表的一个节点是由:节点值、节点的下一个节点(字节点)的地址
二叉查找树一个节点:节点值、节点的左子节点的地址、节点的右子节点的地址
2-3树:由2节点、3节点组成

!图. 2节点 3节点

2节点:

3节点:

红黑树(平衡二叉查找树):节点值、节点的左子节点、节点的右子节点、节点颜色

二叉查找树

二叉查找树:是由2节点的树组成的,最坏的时间复杂度是O(N)

插入的几种情况:

  1. 树为空插入的节点作为根节点
  2. 插入的节点等于子树的值,则树不增加节点
  3. 插入的节点大于最终查询的子树则作为子树的右节点
  4. 插入的节点小于最终查询的子树则作为子树的左节点

根据以上的四种情况,我们可以看出,如果我们插入的值是从1开始逐渐递增的,那么树就最终生长得很像链表。

节点的实现

2节点

private Node<T> root = null;//根节点

private class Node<T>{

    public T value;//为了下面的简单演示设属性为 pubilc
    public Node<T> left;//真正使用的时候应该为private 用get、set方法访问
    public Node<T> right;
    public Node<T> parent;

    public Node(T value, Node<T> parent) {
        this.value = value;
        this.parent = parent;
    }
}

查找

如果查找的值等于根节点的值,那么查找命中,否则递归的在根的子树中(通过比较与根节点的值选择左/右节点)查找。

//返回null 树中没有此节点 ,递归的下左/右子节点查询
    public Node<T> get(T value){

        Node<T> node = root;

        while(true){
            if(node == null){
                return null;
            }
            if(node.value == value){
                return node;
            }else if(node.value > value){
                if(node.right == null){
                    return null;
                }else if(node.right.value == value){
                    return node.right;
                }
                node = node.right;
            }else if(node.value < value){
                if(node.left == null){
                    return null;
                }else if(node.left.value == value){
                    return node.left;
                }
                node = node.left;
            }
        }
    }

插入

插入和查找很像,如果树的根节点为空(空树)则插入到根节点,否则递归的在子树中判断,当子树为null的时候,插入。

public Node<T> put(T value){

    Node<T> node = root;

    while(true){
        if(node == null){
            Node<T> node1 = new Node<>(value,null);
            root = node1;//空树,插入的为根节点
            return node1;
        }
        if(node.value == value){
            return node;
        }else if(node.value > value){
            if(node.right == null){
                Node<T> node1 = new Node<>(value,node);
                node.right = node1;
                return  node1;
            }else if(node.right.value == value){
                return node.right;
            }
            node = node.right;
        }else if(node.value < value){
            if(node.left == null){
                Node<T> node1 = new Node<>(value,node);
                node.left  = node1;
                return node1;
            }else if(node.left.value == value){
                return node.left;
            }
            node = node.left;
        }
    }
}

2-3树

为了解决二叉查找树的不平衡,2-3树孕育而生,2-3树能够很好的实现树的平衡。
2-3树的节点不再是单一的2节点,节点可能是2节点、3节点。

2节点:有一个值,两个子节点
3节点:有两个值,三个子节点。

注意二叉查找树是向下生长,而2-3树是向上生长。
当2-3的根节点由3树生长为(红黑树中的旋转)2节点,树的高度增加。

查找

2-3树的查找和二叉查找树的思路是相同的都是迭代的思想。不过不同的是在判断节点是否相同时2-3树要判断是否相等于左值或右值,如果大于左值小于右值,则从中子节点开始递归。

插入

2-3树的插入有以下几种情况:

树为空

插入的节点作为根节点并且为2节点。
图

2节点中插入

插入的节点为2节点,2节点转化为3节点。

2节点生长为3节点

3节点中插入

插入的节点为3节点,则临时调整3节点为4节点(三个值),4节点中的中值变为左右值的父。

父节点为null

则4节点,转化为3个2节点。
3节点中插入

父为2节点

则4节点的中子转化为父节点的值,父节点转化为3节点。
3节点插入父为2节点

父为3节点

则3节点的中子节点转为父节点的值,父节点临时转化为4节点,此时就变成了插入的节点为3节点的情况上面的两种情况。

父为3节点1

父为3节点2

对比二叉树和2-3树,从1递增插入10,对比树的形状

二叉查找树

通过对比,2-3和二叉树的上图的插入,可以看到2-3最终是会自平衡的,而二叉查找树最坏会变成链表的形式(长的像链表).

红黑树

红黑树其实是2-3树的一种只含2节点的表现形式。还是二叉树节点大于左子节点,小于右子节点。

我们把2-3树中的2节点用黑色表示,3节点用红色表示(3节点的左节点为黑色、右节点为红色)

将红色链接画平就是2-3树。

2-3树红黑树变化图

红黑树的性质

  1. 每个节点要么是红色,要么是黑色(2-3树节点要么是2节点要么是3节点)
  2. 根节点必须是黑色
  3. 红色节点不能连续(红色节点的子和父不能为红)(不能有4节点。注意2-3的4节点是临时的)
  4. 对于每个节点,从该点至null(树的尾端)的任何路径,都含有相同个数的黑色节点。

左旋 右旋

左旋、右旋其实就是2-3树的3节点临时变为4节点,4节点的分解。

左旋

左旋

右旋

右旋

插入

把红黑树的插入看成是2-3树的插入,就能明白红黑树的节点插入,节点的旋转,及根据红黑树的

2-3树红黑树变化图

对比2-3的几种插入情况,就能理解红黑树的插入情况。

参考

http://github.com/CarpenterLee/JCFInternals/blob/master/markdown/5-TreeSet%20and%20TreeMap.md

一个红黑树生成过程: http://www.cs.usfca.edu/~galles/visualization/RedBlack.html

张无忌的回答:
http://www.zhihu.com/question/22774822/answer/46376239

建议看一下《算法》第四版红皮书。
其实理解红黑树起来也不是那么困难。

相关推荐
最新评论 (0)
返回
发表文章
u013565163
文章数
90
评论数
0
注册排名
708768