红黑树（一）

红黑树是一种经典的数据结构，相对于初学者来说是比较复杂的，但是不难理解，有点背书的感觉。

首先红黑树的几个定义：
1.根节点必须为黑色；
2.树中节点不是黑色就是红色；
3.红色节点的子节点必须为黑色（黑色节点的子节点或红或黑）
4.叶子节点都为黑色
5.每个节点到子孙节点路径上的黑节点相同（每个节点到末端节点的黑节点个数相同）

  根据这几条定义定义的二叉树被称作为红黑树，对于红黑树有两个复杂的操作：添加和删除节点

这两个操作必须完成后仍满足以上五个性质；
（1）我们可以利用代码先定义一个红黑树（java版）

public class RBTree<T extends Comparable<T>> {
    private RBTNode<T> mRoot;    // 根结点
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public class RBTNode<T extends Comparable<T>> {
        boolean color;        // 颜色
        T key;                // 关键字(键值)
        RBTNode<T> left;    // 左孩子
        RBTNode<T> right;    // 右孩子
        RBTNode<T> parent;    // 父结点

        public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
}

RBTree树的类，有一个根节点，和两种被声明的静态常量颜色属性RBTNode为节点类是RBTree的内部类提供点实现代码，包括颜色，key值，左右孩子节点和父亲节点，，因为红黑树是排序树需要每个节点能够比较大小，所以要定义一个实现了Comparable接口的泛型T；

（二）接下来编写搜索方法：

private RBTNode<T> search(T key) {
        RBTNode<T> node = mRoot;
        Comparable<? super T> k = (Comparable<? super T>) key;

        while (node != null){
            int a = k.compareTo(node.key);
            if (a>0) {
                node = node.right;
            } else if (a<0) {
                node = node.left;
            } else {
                return node;
            }
        }
        return null;
    }

从根节点依次向下查找，并通过Comparable接口的compareTo方法进行比较查找key值所在节点位置。

（三）接下来是左右旋：
1.左旋

左旋

代码如下：

private void leftRotate(RBTNode<T> x) {
        RBTNode<T> y = x.right;    // 设置x的右孩子为y
        x.right = y.left;    // 将 “y的左孩子” 设为 “x的右孩子”；
        if (y.left != null)    // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
            y.left.parent = x;
        y.parent = x.parent;     // 将 “x的父亲” 设为 “y的父亲”
        if (x.parent == null) {
            this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
        } else {
            if (x.parent.left == x)
                x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
            else
                x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
        }
        y.left = x;      // 将 “x” 设为 “y的左孩子”
        x.parent = y;        // 将 “x的父节点” 设为 “y”
    }

2.右旋

右旋

private void rightRotate(RBTNode<T> y) {
        RBTNode<T> x = y.left;   // 设置x是当前节点的左孩子。
        y.left = x.right;     // 将 “x的右孩子” 设为 “y的左孩子”；
        if (x.right != null)     // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
            x.right.parent = y;
        x.parent = y.parent;    // 将 “y的父亲” 设为 “x的父亲”
        if (y.parent == null) {
            this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
        } else {
            if (y == y.parent.right)
                y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
            else
                y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
        }
        x.right = y;       // 将 “y” 设为 “x的右孩子”
        y.parent = x;    // 将 “y的父节点” 设为 “x”
    }