数据结构与算法-红黑树的java实现-构建红黑树

红黑树

红黑树是一种二分查找树，与普通的二分查找树不同的一点是，红黑树的每个节点都有一个颜色（color）属性。该属性的值要么是红色，要么是黑色。

通过限制从根到叶子的任何简单路径上的节点颜色，红黑树确保没有比任何其他路径长两倍的路径，从而使树近似平衡。

节点

红黑树的节点记录父节点、左子节点、右子节点、数据和颜色（红色或黑色)

红黑树特性

红黑树节点关系图

红黑树中涉及： 父节点，爷节点（parent.parent）， 叔父节点（parent.parent.right或 parent.parent.left), 兄弟节点(parent.right 或 parent.left)

构建一颗二叉树（添加节点)

使用循环先构建一颗二叉搜索树(BST),

/**
 * 添加节点
 *
 * @param data
 */
public void add(int data) {

    if (root == null) {
        root = new Node(data);
        root.color = Color.BLACK;
        return;
    }

    Node curr = root; //记录根节点
    Node parent = null;  //记录父节点

    /*
      遍历到要插入新节点的位置，类似BST
     */
    while (curr != null) {
        parent = curr;  //记录父节点
        if (data < curr.data) {//走左侧位置
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    Node newNode = new Node(data);
    newNode.parent = parent;
    if (data < parent.data) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
     adjustTree(newNode); //调整红黑树
}

调整二叉树为红黑树

记录当前节点的父节点: Node parent = curr.parent;

在调整红黑树有以下几种可能：

1. 要插入的节点的父节点是根节点
2. 要插入的节点的父节点的颜色为黑色
3. 要插入的节点的父节点颜色为红色，叔父节(父节点的兄弟节点)点为红色。
4. 要插入的节点的父节点颜色为红色，叔父节(父节点的兄弟节点)点为黑色。
   • LL型: 父节点为左侧，插入节点在父节点左侧
   • LR型: 父节点为左侧，插入节点在父节点右侧
   • RR型: 父节点为右侧，插入节点在父节点右侧
   • RL型: 父节点为右侧，插入节点在父节点左侧

当前节点的父节点为根节点

当前节点的父节点为空，那么当前节点为根节点。将当前节点的颜色变成黑色。

if (parent == null) {
    curr.color = Color.BLACK;
    return;
}

当前节点的父节点为黑色

如果当前节点的父节点为黑色，不做调整,直接返回。

if(parent.color = Color.BLACK){
    return;
}

当前节点的父节点为红色，叔父节点为红色

当插入节点的父亲节点为红色，叔父节点也为红色。需要将父节点、叔父节点变成黑色，将爷节点变为红色。

Node uncleNode = uncle(parent);
    Node grandfatherNode = parent.parent;
    if (uncleNode.color == Color.RED) {
        parent.color = Color.BLACK;
        uncleNode.color = Color.BLACK;
        grandfatherNode.color = Color.RED;
        adjustTree(grandfatherNode);
        return;
    }

当前节点的父节点为红色，叔父节点为黑色

这种情况需要修改父亲的颜色为黑色，爷节点颜色为红色，然后进行节点的旋转，由于父节点的位置和新插入节点位置不同，操作过程也不相同。我们把此种情况分为四类

LL型

LL型: 当前节点的父节点在爷节点的左侧，要插入的当前节点在父节点的左侧 ，即Left Left(LL型)。

if (grandfatherNode.left == parent && curr == parent.left) {
    parent.color = Color.BLACK;
    grandfatherNode.color = Color.RED;
    //右旋
}

LR型

LR型: 当前节点父节点在爷节点的左侧，当前要添加的节点在父节点的右侧

else if (grandfatherNode.left == parent && curr == parent.right) {
    //parent在左侧，当前插入的节点在右侧(LR)

    //左旋
    curr.color = Color.BLACK;
    grandfatherNode.color = Color.RED;
    //右旋
 }

RR型

RR型: 当前节点的父节点在爷节点右侧，当前添加节点在父节点的右侧

else if (grandfatherNode.right == parent && curr == parent.right) {
    //RR
    parent.color = Color.BLACK;
    grandfatherNode.color = Color.RED;
    //左旋
}

RL型

RL型： 当前节点的父节点在爷节点右侧，当前添加节点在父节点的左侧

else {
    //RL
    //右旋
    curr.color = Color.BLACK;
    grandfatherNode.color = Color.RED;
    //左旋
}

右旋

此处的当前节点是传入的要插入节点的爷节点。

找到X节点

1. 记录当(curr)前节点（实际上是指要插入节t3的爷节点）的左节点X。
2. 记录t3节点，即X节点的右子节点

Node x = curr.left;
Node t3 = x.right;

修改t3的父节点引用

如果t3节点不为空,将t3节点的父节点引用指向当前节点(curr)

if(t3!=null) t3.parent =  curr;

当前节点左节点连接t3

当前节点断开与X的连接，左侧连接t3。

curr.left = t3;

curr成为X的右子节点

1. X节点的右节点连接curr；
2. X的父节点为原curr的节点的父节点；
3. curr节点的父节点为X

x.right = curr;
x.parent = parent;
curr.parent = x;

parent节点连接X

1. 如果parent为空，X节点为根节点
2. 如果parent.left == curr , parent左侧连接X
3. 如果parent.right = curr, parent右侧连接 X

if(parent == null){
    this.root= x;
}else if(parent.left == curr){
    parent.left = x;
}else{
    parent.right = x;
}

左旋

/**
 * 左旋
 *
 * @param curr 当前节点
 */
private void leftRotate(Node curr) {
    Node parent = curr.parent;
    Node x = curr.right;

    Node t2 = x.left;
    if (t2 != null) {
        t2.parent = curr;
    }
    curr.right = t2;
    x.left = curr;
    x.parent = parent;
    curr.parent = x;

    if (parent == null) {
        this.root = x;
    } else if (parent.left == curr) {
        parent.left = x;
    } else {
        parent.right = x;
    }
}

parent = curr;
}
curr.right = t2;
x.left = curr;
x.parent = parent;
curr.parent = x;

if (parent == null) {
    this.root = x;
} else if (parent.left == curr) {
    parent.left = x;
} else {
    parent.right = x;
}

}