数据结构和算法(九)--红黑树

一、红黑树

1、红黑树

    前面介绍了2-3树，可以看到2-3树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点都是2-结点，树的高度为IgN，相比于我们普通的二叉查找树，最坏情况下树的高度为N,确实保证了最坏情况下的时间复杂度，但是2-3树实现起来过于复杂，所以我们介绍一种2-3树思想的简单实现：红黑树。
    红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：
        红链接：将两个2-结点连接起来构成一个3-结点，

        黑链接：则是2-3树中的普通链接。
    确切的说，我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。

1.1、红黑树的定义

红黑树是含有红黑链接并满足下列条件的二叉查找树：
    1、红链接均为左链接;
    2、没有任何一个结点同时和两条红链接相连;
    3、该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同;
下面是红黑树与2-3树的对应关系:

1.2、红黑树结点API

    因为每个结点都只会有一条指向自己的链接(从它的父结点指向它)，我们可以在之前的Node结点中添加一个布尔类型的变量color来表示链接的颜色。如果指向它的链接是红色的，那么该变量的值为true，如果链接是黑色的，那么该变量的值为false。

API设计：

类名	Node<Key,Value>
构造方法	Node(Key key, Value value, Node left, Node right , boolean color):创建Node对象
成员变量	1.public Node left:记录左子结点 2.public Node right:记录右子结点 3.public Key key:存储键 4.public Value value:存储值 5.public boolean color:由其结点指向它的链接的颜色

代码：

public class Node<Key, Value> {//存储键public key key;//存储值private value value;//记录左子结点public Node left;//记录右子结点public Node right;//由其父结点指向它的链接的颜色public boolean color;public Node(Key key, Value value, Node left, Node right, boolean color) {this.key = key;this.value = value;this.left = left;this.right = right;this.color = color;}
}

1.3、平衡化

    在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

1.3.1、左旋

    当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。

前提：当前结点为h，它的右子结点为x;

左旋过程：
    1、让x的左子结点变为h的右子结点：h.right=x.left;
    2、让h成为x的左子结点：x.left=h;
    3、让h的color属性变为x的color属性值：x.color=h.color;
    4、让h的color属性变为RED：h.color=true;

1.3.2、右旋

    当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋。

前提：当煎结点为h，它的左子结点为x;

右旋过程：
    1、让x的右子结点成为h的左子结点：h.left=x.right;
    2、让h成为x的右子结点：x.right=h;
    3、让x的color变为h的color属性值：x.color =h.color;
    4、让h的color为RED ;

数据结构和算法(一)

数据结构和算法(八)--2-3查找树

数据结构--栈、队列、链表、散列表、排序二叉树

再小的努力，乘以365都很明显！
每天⽤⼼记录⼀点点。内容也许不重要，但习惯很重要！
一个程序员最重要的能力是：写出高质量的代码！！
有道无术，术尚可求也，有术无道，止于术。
无论你是年轻还是年长，所有程序员都需要记住：时刻努力学习新技术，否则就会被时代抛弃！