红黑树 - 橙子加的分享

红黑树简介

红黑树一种自平衡的二叉树，先了解一下什么是二叉树把。

二叉树的性质

在二叉树的第I层上最多有2^i-1(i>=1)

二叉树中如果深度为K，那么该二叉树最多有2^k-1个节点（k>=1）

n₀ = n₁+1 其中n₀表示度数为0的节点数，n₁表示度数为2的节点数

在完全二叉树中，具有n个节点的完全二叉树的深度为[log₂n]+1，其中[log₂n]是向下取整

若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

在了解二叉树的性质后，再来了解一下红黑树的性质

红黑树性质

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树是自平衡的二叉树，由上图可以看出来虽然左右子树的层数不一样，但是从任一节点到每个子节点都包含相同数量的黑色节点。

红黑树的自平衡操作

红黑树通过三种操作来实现自平衡分别是
左旋:以X做为支点(旋转节点)，其右子结点变为旋转节点的父结点，右子节点的左子节点变为旋转节点的右子节点，左节结点保持不变。
右旋:以X做为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
变色：红变黑，黑变红

左旋

右旋

从上图可以发现
左旋只影响旋转节点和其右子节点的结构。
右旋只影响旋转节点和其左子节点的结构。

红黑树查找

因为红黑树就只是能够自平衡的二叉树，它与二叉树的区别主要在于插入，因此它的查找于二叉树是一样一样的。

把根节点设为当前节点，从根节点开始查找。
如果当前节点为空，直接返回null
如果当前节点与查找key相等，直接返回当前节点
如果当前节点大于查找key，则设置当前节点的左子节点为当前节点，重复步骤2
如果当前节点小于查找key，则设置当前节点的右子节点为当前节点，重复步骤2

红黑树插入

红黑树的插入分为两部分，第一部分于一般的二叉树插入一样，第二部分就是自平衡。

从根节点开始查找。
若根节点为空，那么插入节点作为根节点，结束。
若根节点不为空，那么把根节点作为当前节点。
若当前节点为null，返回当前节点的节结点，结束。
若当前节点key等于查找key，那么该key所在节点就是插入节点，更新节点的值，结束。
若当前节点key大于查找key，把当前节点的左子节点设置为当前节点，重复步骤4
若当前节点key小于查找key，把当前结点的右子结点设置为当前节点，重复步骤4

插入的节点默认都是红色的，因为为红色不见得会破坏红黑树平衡，但是如果为黑色，那么黑节点多1，打破平衡，就必须要做自平衡了。

红黑树自平衡

红黑树代码实现

package com.czj.shiro.redblcaktree;

import java.util.Random;
import java.util.Stack;

/**
 * 创建在 2020/3/30 22:41
 */
public class RBTree<T extends Comparable>{

    public static final boolean RED=false;

    public static final boolean BLACK=true;

    private RBNode<T> headNode;



    public static class RBNode<T extends Comparable>{
        private T key; //键

        private boolean color; //颜色

        private RBNode<T> leftNode; //左子节点

        private RBNode<T> rightNode; //右子节点

        private RBNode<T> parentNode; //父亲节点

    }

    public void insert(RBNode<T> node){
        int tmp=0;
        RBNode<T> x=this.headNode;
        RBNode<T> y=null;

        while(x!=null){
            y=x;
            tmp=x.key.compareTo(node.key);
            if (tmp==1){
                x=x.leftNode;
            }else if(tmp==-1){
                x=x.rightNode;
            }else {
                return;
            }
        }
        node.parentNode=y;
        if (y!=null){
            tmp=y.key.compareTo(node.key);
            if (tmp==1){
                y.leftNode=node;
            }else if(tmp==-1){
                y.rightNode=node;
            }else {
                return;
            }
        }else {
            this.headNode=node;
        }

        node.color=RED;

    }


    private void fix(RBNode<T> node){
        RBNode<T> parent,uncle,gParent;
        //1-3情况 不需要修正..
        while ((parent=parentOf(node))!=null&&isRed(node)){
            gParent=parentOf(parent);
            //处理当父亲结点为红色和叔叔结点存在且为红色的情况4.1
            if((uncle=isUncle(node))!=null&&isRed(uncle)){
                parent.color=BLACK;
                uncle.color=BLACK;
                gParent.color=RED;
                node=gParent;
                continue;
            }

            //如果父亲结点为祖父结点的左子结点4.2
            if(gParent.leftNode==parent){

                //如果当前结点为父亲结点的右子结点4.2.2
                if (parent.rightNode==node){
                    leftRotate(parent);//左旋
                    RBNode<T> tmp=node;
                    node=parent;       //把父类结点设为当前结点
                    parent=tmp;
                }

                gParent.color=RED;//4.2.1情景
                parent.color=BLACK;
                rightNode(gParent);
            //如果父类结点为祖父结点的右子结点
            }else {
                //如果当前结点为父类结点的左子结点
                if (parent.leftNode==node){
                    rightNode(parent);
                    RBNode<T> tmp=node;
                    node=parent;       //把父类结点设为当前结点
                    parent=tmp;
                }

                gParent.color=RED;
                parent.color=BLACK;
                leftRotate(gParent);
            }
        }
        this.headNode.color=BLACK;
    }

    public RBNode<T> parentOf(RBNode<T> node){
        return node.parentNode;
    }

    public boolean isRed(RBNode<T> node){
        return node.color==RED;
    }

    /**
     * @author czj
     * 返回叔叔节点 如果父亲结点不存在或叔叔结点不存在 返回null
     * @date 2020/3/31 10:18
     * @param [node]
     * @return com.czj.shiro.redblcaktree.RBTree.RBNode<T>
     */
    public RBNode<T> isUncle(RBNode<T> node){
        RBNode<T> parentNode=node.parentNode;
        if (parentNode==null){
            return null;
        }

        if (parentNode.leftNode==null||parentNode.rightNode==null){
            return null;
        }
        if (parentNode.leftNode==node){
            return parentNode.rightNode;
        }else{
            return parentNode.leftNode;
        }
    }

    //左旋
    public void leftRotate(RBNode<T> node){
        RBNode<T> rightNode=node.rightNode;//获得右子结点
        node.rightNode=rightNode.leftNode;

        //如果右子结点的左子结点不为空
        if (rightNode.leftNode!=null)
            rightNode.leftNode.parentNode=node;
        //祖父结点设置
        rightNode.parentNode=node.parentNode;

        //判断是不是为根节点
        if (node.parentNode==null){
            this.headNode=rightNode;
        }else {
            if (node.parentNode.leftNode==node){
                node.parentNode.leftNode=rightNode;
            }else {
                node.parentNode.rightNode=rightNode;
            }
        }

        rightNode.leftNode=node;
        node.parentNode=rightNode;
    }

    //右旋
    public void rightNode(RBNode<T> node){
        RBNode<T> leftNode=node.leftNode;
        node.leftNode=leftNode.rightNode;
        if (leftNode.rightNode!=null){
            leftNode.rightNode.parentNode=node;
        }

        leftNode.parentNode=node.parentNode;

        if (node.parentNode==null){
            this.headNode=leftNode;
        }else {
            if (node.parentNode.leftNode==node){
                node.parentNode.leftNode=leftNode;
            }else {
                node.parentNode.rightNode=leftNode;
            }
        }
        leftNode.rightNode=node;
        node.parentNode=leftNode;
    }

    //中序遍历（非递归）
    public void inOrder(){
        Stack<RBNode<T>> stack=new Stack<>();
        RBNode<T> node=this.headNode;
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node=node.leftNode;
            }
            if (!stack.isEmpty()){
                RBNode<T> nNode=stack.pop();
                System.out.println("值:"+nNode.key);
                node=nNode.rightNode;
            }
        }
    }

    public static void main(String[] args) {
        RBTree<Integer> rbTree=new RBTree<>();
        Random random=new Random();
        RBNode<Integer> rbNode=null;
        for (int i=0;i<=100;i++){
            rbNode = new RBNode<>();
            rbNode.key=random.nextInt(1000);
            rbTree.insert(rbNode);
        }
        rbTree.inOrder();
    }
}