红黑树本质是由2-3查找树演变而成的二叉树，由于2-3查找树需要维护两种节点，在实现上很不方便因此出现了红黑树这种演变。红黑树中的红色节点与其父节点即为2-3查找树中的3节点。黑色节点即为正常的节点。
红黑树的特性
①红节点均为左节点
②不存在拥有两个红子节点的节点
③红黑树是平衡二叉树，任意叶子结点到根节点的路径上黑色节点的个数相同
④根节点必为黑色
⑤如果节点是红色，则其子节点必为黑色
特性①红色节点为左节点个人理解是为了方便实现和画图理解。特性②和⑤其实是一回事，如果一个节点存在两个红色节点则他便是一个4节点，同样的红节点的子节点还是红节点也等价于一个4节点。
红黑树可将红节点横过来作为其父节点的兄弟节点看，就可以看出所有2、3节点。
实现
颜色表示
可以定义两个常量表示颜色：
public static final RED = true;
public static final BLACK = false;
节点数据结构
class Node {
private Key key;
private Value value;
private boolean color; //节点颜色
private int size; //以节点为根的树的节点个数
private Node right, left;
public Node(Key key, Value value, boolean color, int size){
this.key = key;
this.value = value;
this.color = color;
this.size = size;
}
}
红黑树的平衡实现
红黑树是平衡树，所以维持树的平衡很关键，但需要考虑节点颜色这一过程通过旋转和变色来实现。红黑树的旋转可分为左旋转和右旋转。变色其实就是当前节点和其左右节点颜色都变为相反的即可。
在此之前先定函数判断节点的颜色。
public boolean isRed(Node node){
if(node == null){
return false;
}
return node.color;
}
1.变色
变色发生在当前节点及其左右节点违反了特性②的基础上。
插入S后违反了特性②
插入操作在插入节点的时候都是创建一个键值对应的红色节点，并通过后续的平衡修正保证平衡。上图插入S后节点E有两个红色节点，变成了一个4节点，这种情况下使用变色方式调整平衡。
public void flipColors(Node node){
node.color = !node.color;
node.left.color = !node.left.color;
node.right.color = !node.right.color;
}
变换后的效果
变色后
2.左旋转
当节点的左节点为黑色，右节点是红节点的情况下需要左旋转。
需要左旋转
左旋转实现
public Node rorateLeft(Node node){
Node temp = node.right; //当前节点的右节点
node.right = temp.left; //当前节点的右节点变为其右节点的左节点
temp.left = node; //当前节点变为其右节点的左节点
//改变颜色
temp.color = temp.left.color;
temp.left.color = RED;
temp.size = temp.left.size;
//调整大小
temp.left.size = size(temp.left.left) + size(temp.left.right) + 1;
return temp;
}
旋转后的样子
左旋转完成
旋转函数以Node类型作为返回值，原因是旋转过后当前节点可能变为旋转后的子节点，如图h节点旋转后成为x节点的左子结点，h节点即被其原右子节点x替代。
旋转过程
3.右旋转
右旋转和左旋转方向相反，原节点的左子结点替换原节点，原节点变为其左子结点的右子节点。这种操作发生在当前节点的左节点和其左节点的左节点都是红色节点的情况下。
右旋转前
右旋转实现
public Node rorateRight(Node node){
Node temp = node.left; //记录当前节点的左节点
node.left = temp.right; //当前节点的左节点变为其左节点的右节点
temp.right = node; //当前节点变为其左节点的右节点
//调整颜色
temp.color = temp.right.color;
temp.right.color = RED;
//调整大小
temp.size = temp.right.size;
temp.right.size = size(temp.right.left) + size(temp.right.right) + 1;
return temp;
}
右旋转后
旋转后
旋转过程
旋转过程
补充
做旋转和右旋转中都有一个更新size的操作，函数如下给出
public int size(Node node){
if(null == node){
return 0;
}
return 1 + size(node.left) + size(node.right);
}
三种旋转和变色的操作在红黑树的插入和删除操作后起着维持红黑树平衡的作用。
红黑树插入操作
插入操作从根节点出发，当碰到Key值相等的节点时更新原值即结束。否则，若当前节点Key值大于插入的Key值，继续搜寻当前节点的左子树插入，否则右子树插入。当遇到空节点是创建新节点完成插入操作。
public void insert(Key key, Value value){
//key不可以为null
if(null == key){
throw new IllegalArgumentException("argument key of insert() can't be null");
}
//插入操作可能造成根节点变化
root = insert(root, key, value);
//保证根节点为BLACK
root.color = BLACK;
}
private Node insert(Node node, Key key, Value value){
//遇到null节点创建新节点
if(null == node){
node = new Node(key, value, RED, 1);
return node;
}
//否则进行比较
int cmp = key.compareTo(node.key);
if(cmp == 0){ //相等更新value即可
node.value = value;
}else if(cmp > 0){ //key大于node.key，右子树继续插入操作
node = insert(node.right, key, value);
}else{ //key小于node.key，左子树继续插入操作
node = insert(node.left, key, value);
}
//完成插入后，红黑树平衡可能被破坏，需要重新调整平衡
insertBalance(node);
}
public void insertBalance(Node node){
//当前节点左节点为黑节点，右节点为红节点——左旋转
if(!isRed(node.left) && isRed(node.right)){
node = rorateLeft(node);
}
//当前节点的左节点及其左节点的左节点为红色节点——右旋转
if(isRed(node.left) && isRed(node.right)){
node = rorateRight(node);
}
//当前节点左右节点都是红色节点——变色
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
插入过程相对比较简单，注意的是插入新结点后进行红黑树平衡调整的几个条件不是if...else if的关系，而是每部操作之后都需要进行一次判断，毕竟旋转过程中任何情况都可能发生。
每部插入操作后对当前节点进行调整，逐层向上递归，每层都调整平衡即可保证根节点处左右子树的平衡和红黑节点规范。
删除操作
红黑树删除操作相对复杂，对于删除的节点，如果节点是红色节点直接删除不会影响树的平衡性，如果是黑色节点，删除后会造成当前路径上黑色节点数少1，违反了红黑树特性③，因此在删除过程中需要对树的结构进行调整，删除后依旧需要对树的结构进行调整。
方便理解，由删除最小键值、删除最大键值和普通删除操作展看。
1.删除最小键值
如果最小键为红色节点，直接删除即可，不影响红黑树平衡。所以在递归删除的过程中，需要保证最小节点为红色节点，那么在递归删除的过程中，需要保证当前节点或者其左节点为红色。
原因：
①如果当前节点是红色且是最小键，直接删除即可
②当前节点是3节点中的黑色节点，继续递归，下一个节点定是红色节点，只需要判断红色节点是否是最小键即可
保证当前节点或者其左节点是红色节点的实现：从当前节点的父节点入手，如果不能保证左节点是3节点或4节点（即不是2节点）时，就需要从当前节点右子树中借一个节点，通过旋转和变色实现。
①借一个节点使得当前节点为红节点，对应2-3树中的4节点
当前节点变为红节点
！！！注意这里的h节点指的是当前节点的父节点
②借一个节点使得当前节点的左节点为红色节点，对应2-3树中的3节点
当前节点的左节点变为红色
！！！注意这里的h节点指的是当前节点的父节点
public void deleteMin(){
//空树无法删除
if(null == root){
throw new NoSuchElementException("tree is empty!");
}
//根节点左右节点都为黑色节点，置根节点为红色
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
root = deleteMin(root);
//树非空，根节点颜色置黑
if(!isEmpty()){
root.color = BLACK;
}
}
private Node deleteMin(Node node){
//当前节点的左节点为null，即为最小节点
if(null == node.left){
return null;
}
//保证当前节点或其左节点为红色，注意是从父节点入手
if(!isRed(node.left) && !isRed(node.left.left)){
//制造红色节点
node = moveRedLeft(node);
}
//递归删除最小键节点
node = deleteMin(node.left);
//调整平衡
return deleteBalance(node);
}
private Node moveRedLeft(Node node){
//先变色
flipColors(node);
//判断节点右节点的左节点是否红色，若是，按第二种方式操作
if(isRed(node.right.left)){
node.right = rorateRight(node.right);
node = rorateLeft(node);
flipColors(node);
}
return node;
}
private Node deleteBalance(Node node){
if(isRed(node.right)){
node = rorateLeft(node);
}
if(isRed(node.left) && isRed(node.right)){
node = rorateRight(node);
}
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
moveRedLeft()函数即上面两张图片对应的转换操作，当当前节点的右节点的左节点颜色为红色时按照第二种方式进行转换，将当前节点的左节点的左节点变成红色。否则当前节点左节点为红色，左节点的左节点为黑色。（看代码更好理解）
2.删除最大键值节点
最大键删除和最小键正好相反，删除最大键的过程就是保证当前节点或当前节点的右节点为红色节点，保证删除后不会破坏红黑树平衡。将当前节点或其右节点变为红色的过程也需要从其父节点入手。
①生成一个4节点
当前节点变成红色
！！！注意这里的h节点指的是当前节点的父节点
②借一个节点使得当前节点的右节点为红色节点，对应2-3树中的3节点
当前节点的右节点变为红色
！！！注意这里的h节点指的是当前节点的父节点
public void deleteMax(){
//检查二叉树非空
if(isEmpty()){
throw new NoSuchElementException("tree is empty!");
}
//当根节点左右节点都为黑色节点，将根节点变红
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
//删除最大键，删除过程根节点可能变化
root = deleteMax(root);
//树非空，保证根节点为黑色
if(!isEmpty()){
root.color = BLACK;
}
}
private Node deleteMax(Node node){
//当前节点存在红色左节点，进行右旋转创造红色的右节点
if(isRed(node.left)){
node = rorateRight(node);
}
//节点无右节点，即为最大键，删除
if(null == node.right){
return null;
}
//保证node或node.right为红节点，注意也是从父节点入手
//因为3节点是用红节点来模拟的，红节点不可能是右孩子，所以不可能是h.right.right
if(!isRed(node.right) && !isRed(node.right.left)){
node = moveRedRight(node);
}
node.right = deleteMax(node.right);
//注意删除后需要重新平衡红黑树
return deleteBalance(node);
}
private Node moveRedRight(Node node){
//变色
flipColors(node);
//相当于完成图2，将右节点的右节点变红，创造3节点操作
if(isRed(node.left.left)){
node = rorateRight(node);
flipColors(node);
}
return node;
}
3.删除操作
删除操作结合了1、2中所讲的两种制造红色节点的操作，直接看代码配合1、2中的图更方便理解。
public void delete(Key key){
//判断树非空
if(isEmpty()){
throw new NoSuchElementException("tree is empty!");
}
//key不得为null
if(null == key){
throw new IllegalArgumentException("argument of delete can't be null");
}
//检查键是否存在
if(!contains(key)){
return ;
}
//根节点左右节点都是黑色，根节点变红
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
root = delete(root, key);
//树非空，根节点为黑色
if(!isEmpty()){
root.color = BLACK;
}
}
private Node delete(Node node, Key key){
//当前节点的键大于待删除的键，需要在当前节点左子树中递归删除
//当前节点的左右节点都是黑色节点，通过moveRedLeft创造红色左节点
if(key.compareTo(node.key) < 0){
if(!isRed(node.left) && !isRed(node.left.left)){
node = moveRedLeft(node);
}
node.left = delete(node.left, key);
}else{ //待删除的键大于等于当前节点的键
//如果当前节点的左节点为红色——右旋转
//该步操作创造红色右节点
if(isRed(node.left)){
node = rorateRight(node);
}
//如果待删除key与当前节点key相等，切当前节点右节点为空——可以直接删除
if(key.compareTo(node.key) == 0 && node.right == null){
return null;
}
//当前节点key小于待删除的key，需要在其右子树中进行删除
//当前节点的左右节点都是黑色节点，通过moveRedRight创造红色右节点
if(!isRed(node.right) && !isRed(node.right.left)){
node = moveRedRight(node);
}
//旋转后的当前节点key若等于待删除key
//替换当前节点为其右子树的最小节点，之后删除其右子树的最小节点即可
if(key.compareTo(node.key) == 0){
Node temp = min(node.right);
node.key = temp.key;
node.value = temp.value;
node.right = deleteMin(node.right);
}else{ //若不相等，继续在右子树中执行删除操作
node.right = delete(node.right, key);
}
return deleteBalance(node);
}
！！！注意，这里不能再函数的开头使用一个int值记录当前节点key和待删除key的比较结果，因为在后续过程中，moveRedLeft和moveRedRight操作可能改变当前节点所指向的节点，因此，每次变换完都需要重新进行比较。
给出完整的红黑树操作
public class RedBlackTree <Key extends Comparable, Value>{
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{
private Key key;
private Value value;
private boolean color;
private int size;
public Node(Key key, Value value, boolean color, int size){
this.key = key;
this.value = value;
this.color = color;
this.size = size;
}
}
private boolean isRed(Node node){
if(null == node){
return false;
}
return node.color;
}
private int size(Node node){
if(null == node){
return 0;
}
return 1 + size(node.left) + size(node.right);
}
public boolean isEmpty(){
return null == root;
}
public Node min(){
if(isEmpty()){
return null;
}
return min(root);
}
private Node min(Node node){
if(null == node.left){
return node;
}
return min(node.left);
}
public Node max(){
if(isEmpty()){
return null;
}
return max(root);
}
private Node max(Node node){
if(null == node.right){
return node;
}
return node.right;
}
public Value get(Key key){
if(null == key){
throw new IllegalArgumentException("argument of get() can't be null!");
}
return get(root, key);
}
private Value get(Node node, Key key){
if(null == node){
return null;
}
int cmp = key.compareTo(node.key);
if(cmp == 0){
return node.value;
}else if(cmp > 0){
return get(node.right, key);
}else{
return get(node.left, key);
}
}
public boolean contains(Key key){
if(null == get(key)){
return false;
}
return true;
}
public void insert(Key key, Value value){
if(null == key){
throw new IllegalArgumentException("argument of get() can't be null!");
}
root = insert(root, key, value);
root.color = BLACK;
}
private Node insert(Node node, Key key, Value value){
if(null == node){
node = new Node(key, value, RED, 1);
return node;
}
int cmp = key.compareTo(node.key);
if(cmp == 0){
node.value = value;
}else if(cmp > 0){
node.right = insert(node.right, key, value);
}else{
node.left = insert(node.left, key, value);
}
return insertBalance(node);
}
public void deleteMin(){
if(isEmpty()){
throw new NoSuchElementException("tree is empty!");
}
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
root = deleteMin(root);
if(!isEmpty()){
root.color = BLACK;
}
}
private Node deleteMin(Node node){
if(null == node.left){
return null;
}
if(!isRed(node.left) && !isRed(node.left.left)){
node = moveRedLeft(node);
}
node.left = deleteMin(node.left);
return deleteBalance(node);
}
public void deleteMax(){
if(isEmpty()){
throw new NoSuchElementException("tree is empty!");
}
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
root = deleteMax(root);
if(isEmpty()){
root.color = BLACK;
}
}
private Node deleteMax(Node node){
if(null == node.right){
return null;
}
if(!isRed(node.right) && !isRed(node.right.left)){
node = moveRedRight(node);
}
node.right = deleteMax(node.right);
return deleteBalance(node);
}
public void delete(Key key){
if(!contains(key)){
return ;
}
if(null == key){
throw new IllegalArgumentException("argument of get() can't be null!");
}
if(!isRed(root.left) && !isRed(root.right)){
root.color = RED;
}
root = delete(root, key);
if(!isEmpty()){
root.color = BLACK;
}
}
private Node delete(Node node, Key key){
if(key.compareTo(node.key) < 0){
if(!isRed(node.left) && !isRed(node.left.left)){
node = moveRedLeft(node);
}
node.left = delete(node.left, key);
}else{
if(isRed(node.left)){
node = rorateRight(node);
}
if(key.compareTo(node.key) == 0 && null == node.right){
return null;
}
if(!isRed(node.right) && !isRed(node.right.left)){
node = moveRedRight(node);
}
if(key.compareTo(node.key) == 0){
Node temp = min(node.right);
node.key = temp.key;
node.value = temp.value;
node.right = deleteMin(node.right);
}else{
node.right = delete(node.right, key);
}
}
return deleteBalance(node);
}
private Node insertBalance(Node node){
if(!isRed(node.left) && isRed(node.right)){
node = rorateLeft(node);
}
if(isRed(node.left) && isRed(node.left.left)){
node = rorateRight(node);
}
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
private Node deleteBalance(Node node){
if(isRed(node.right)){
node = rorateLeft(node);
}
if(isRed(node.left) && isRed(node.left.left)){
node = rorateRight(node);
}
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
private void flipColors(Node node){
node.color = !node.color;
node.left.color = !node.left.color;
node.right.color = !node.right.color;
}
private Node rorateLeft(Node node){
Node temp = node.right;
node.right = temp.left;
temp.left = node;
temp.color = node.color;
node.color = RED;
temp.size = node.size;
node.size = 1 + size(node.left) + size(node.right);
return temp;
}
private Node rorateRight(Node node){
Node temp = node.left;
node.left = temp.right;
temp.right = node;
temp.color = node.color;
node.color = RED;
temp.size = node.size;
node.size = 1 + size(node.left) + size(node.right);
return temp;
}
private Node moveRedLeft(Node node){
flipColors(node);
if(isRed(node.right.left)){
node.right = rorateRight(node.right);
node = rorateLeft(node);
flipColors(node);
}
return node;
}
}
网友评论