java实现红黑树(左旋,右旋,修复)

红黑树(左旋,右旋,修复)"/>

java实现红黑树(左旋,右旋,修复)

目录标题

• 1. 红黑树的介绍
• 2. 红黑树的变换规则
• 3. 红黑树的Java实现(代码说明)

1. 红黑树的介绍

红黑树(Red-Black Tree 简称 R-B Tree),它是一种它一种特殊的二叉查找树。
红黑树是一种特殊的二叉搜索树,意味着它满足二叉查找树的特征(简书):

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点

除了具备该特性之外，红黑树还包括许多额外的信息。
红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

这里大家要知道红黑树是平衡二叉树(AVL)的一种特殊实现,类似为平衡二叉树类似一个类,而红黑树是类的一个具体实例。他们的区别推荐几篇博客 : 红黑树和AVL树（平衡二叉树）区别，红黑树和AVL树区别
红黑树示意图如下：
![在这里插入图片描述](.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ5Mjgw,size_16,color_FFFFFF,t_70

2. 红黑树的变换规则

对于变换颜色来讲,无论是左子树还是右子树都是一样的,对于左旋和右旋,旋转的节点是有区别的
前提: 插入的节点的父亲是红色
情景1： 叔叔节点不存在, 或者叔叔节点为黑色,父节点为爷爷节点的左子树

• 插入的节点为父亲节点的左子树 (LL情况)
  将父亲染为黑色,爷爷染为红色,以爷爷节点右旋
  

• 插入的节点为父亲节点的右子树(LR情况)
  以爸爸节点左旋回到LL情况,然后指定爸爸节点为当前节点进行下一轮处理
  

情景2： 叔叔节点不存在, 或者叔叔节点为黑色,父节点为爷爷节点的右子树

• 插入的节点为父亲节点的右子树(RR情况)
  

• 插入的节点为父亲节点的左子树 (RL情况)
  以爸爸节点右旋回到RR情况,然后指定爸爸节点为当前节点进行下一轮处理
  

3. 红黑树的Java实现(代码说明)

红黑树的基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。
旋转包括两种：左旋 和 右旋。下面分别对红黑树的基本操作进行介绍。

• 基本节点定义

1. 颜色 : boolean color
2. 键值key : T key
3. 左孩子 : RBNode left
4. 右孩子 : RBNode right
5. 父节点 : RBNode parent;

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;}}...
}

• 左旋
  注意: 对 x 进行左旋 就是将 x变换为一个左节点
  左旋的实现代码(java）

/* * 对红黑树的节点(x)进行左旋转** 左旋示意图(对节点x进行左旋)：*      px                              px*     /                               /*    x                               y                *   /  \      --(左旋)-.           / \                *  lx   y                          x  ry     *     /   \                       /  \*    ly   ry                     lx  ly  ***/
private void leftRotate(RBTNode<T> x) {// 设置x的右孩子为yRBTNode<T> y = x.right;// 将 “y的左孩子” 设为 “x的右孩子”；// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”x.right = y.left;if (y.left != null)y.left.parent = x;// 将 “x的父亲” 设为 “y的父亲”y.parent = x.parent;if (x.parent == null) {this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点} else {if (x.parent.left == x)x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”elsex.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”}// 将 “x” 设为 “y的左孩子”y.left = x;// 将 “x的父节点” 设为 “y”x.parent = y;
}

• 右旋
  对y进行右旋，意味着将y变成一个右节点。
  
  右旋的实现代码(java）

/* * 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)：*            py                               py*           /                                /*          y                                x                  *         /  \      --(右旋)-.            /  \                     *        x   ry                           lx   y  *       / \                                   / \                   *      lx  rx                                rx  ry* */
private void rightRotate(RBTNode<T> y) {// 设置x是当前节点的左孩子。RBTNode<T> x = y.left;// 将 “x的右孩子” 设为 “y的左孩子”；// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”y.left = x.right;if (x.right != null)x.right.parent = y;// 将 “y的父亲” 设为 “x的父亲”x.parent = y.parent;if (y.parent == null) {this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点} else {if (y == y.parent.right)y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”elsey.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”}// 将 “y” 设为 “x的右孩子”x.right = y;// 将 “y的父节点” 设为 “x”y.parent = x;
}

• 添加节点
  首先红黑树是一颗特殊的二查搜索树,插入一个节点的时候我们将红黑树当作一棵二叉搜索树,插入节点,其次为了满足红黑树的特性,我们将插入的节点颜色着色为红色,最后为了保证插入节点之后,该树还是满足红黑树的特性,我们需要通过进行树的修正,例如变色或者是旋转。
  这里说一下为什么要将节点着色为红色,而不是黑色,回顾一下之前的红黑树的特性(5）

  从一个节点出发到该节点的任意子孙节点上的所有路径上包含数目相同的黑节点 
  

  将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。

  添加操作的实现代码(Java语言)

/* 
* 将结点插入到红黑树中
*
* 参数说明：
*     node 插入的结点        // 对应《算法导论》中的node
*/
private void insert(RBTNode<T> node) {int cmp;RBTNode<T> y = null;RBTNode<T> x = this.mRoot;// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。while (x != null) {y = x;cmp = node.keypareTo(x.key);if (cmp < 0)x = x.left;elsex = x.right;}node.parent = y;if (y!=null) {cmp = node.keypareTo(y.key);if (cmp < 0)y.left = node;elsey.right = node;} else {this.mRoot = node;}// 2. 设置节点的颜色为红色node.color = RED;// 3. 将它重新修正为一颗二叉查找树insertFixUp(node);
}/* 
* 新建结点(key)，并将其插入到红黑树中
*
* 参数说明：
*     key 插入结点的键值
*/
public void insert(T key) {RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);// 如果新建结点失败，则返回。if (node != null)insert(node);
}

添加修正操作的实现代码(Java语言)

/** 红黑树插入修正函数** 在向红黑树中插入节点之后(失去平衡)，再调用该函数；* 目的是将它重新塑造成一颗红黑树。** 参数说明：*     node 插入的结点        // 对应《算法导论》中的z*/
private void insertFixUp(RBTNode<T> node) {RBTNode<T> parent, gparent;// 若“父节点存在，并且父节点的颜色是红色”while (((parent = parentOf(node))!=null) && isRed(parent)) {gparent = parentOf(parent);//若“父节点”是“祖父节点的左孩子”if (parent == gparent.left) {// Case 1条件：叔叔节点是红色 变色RBTNode<T> uncle = gparent.right;if ((uncle!=null) && isRed(uncle)) {setBlack(uncle);setBlack(parent);setRed(gparent);node = gparent;continue;}// Case 2条件：叔叔是黑色，且当前节点是右孩子 lr以父节点左旋if (parent.right == node) {RBTNode<T> tmp;leftRotate(parent);tmp = parent; //将子节点作为父亲 交换一下parent = node;node = tmp;}// Case 3条件：叔叔是黑色，且当前节点是左孩子。setBlack(parent);setRed(gparent);rightRotate(gparent);} else {    //若“z的父节点”是“z的祖父节点的右孩子”// Case 1条件：叔叔节点是红色RBTNode<T> uncle = gparent.left;if ((uncle!=null) && isRed(uncle)) {setBlack(uncle);setBlack(parent);setRed(gparent);node = gparent;continue;}// Case 2条件：叔叔是黑色，且当前节点是左孩子if (parent.left == node) {RBTNode<T> tmp;rightRotate(parent);tmp = parent;parent = node;node = tmp;}// Case 3条件：叔叔是黑色，且当前节点是右孩子。setBlack(parent);setRed(gparent);leftRotate(gparent);}}// 将根节点设为黑色setBlack(this.mRoot);
}