完整代码:https://github.com/nicktming/code/blob/dev/data_structure/RedBlackTree.java
前言
红黑树就是一棵2-3树(如果不了解2-3树的话,可以移步先看一下我的另一篇博客2-3树)的实现,红链接是将两个2-节点连接起来构成一个3-节点,而黑链接是2-3树中的普通链接.
先看一下红黑树是啥样的.
说明一下:E是红节点意味着E到E的父亲节点J之间的链接是红色的,还有就是根节点M永远是黑色的.
rbt_1.jpeg
它是完美平衡的,所以对应上面的图我们先看一下红黑树的定义.
- 红链接都是左链接
- 没有任何一个节点同时与两个红链接相连
- 该树是完美黑色平衡的,即任意空链接到根节点的路径上的黑链接数量相同.
解释一下我的理解:
关于定义1:红链接也可以都是右链接,都是如果都可以的话就会比较混乱了.
关于定义2:因为两个红链接相连起来会构成一个3-节点,同理如果三个红链接相连就会构成一个4-节点,因此不能有任何一个节点与两个红链接同时相连,其实等同于红节点的两个孩子必须是黑节点.
关于定义3:这是2-3树的性质,从上面的图中也可以看到这个性质.
先定义一下红黑树
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; //头节点
private class Node {
Key key; //用来比较的键
Value value; //用来保存真正的值
Node left, right; //左右子节点
/* 是否是红节点 true表示红节点(与父亲节点的链接为红色链接) false表示黑节点(与父亲节点的链接为黑色链接) */
boolean color;
Node(Key key, Value value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
}
private boolean isRed(Node h) {
if (h == null) return false;
return h.color == RED;
}
}
介绍平衡红黑树的几种方式
左旋转
image.png
与二叉平衡树的左旋转类似,区别在于二叉平衡树需要改变节点的树高,而这里需要改变节点的颜色.
/* 左旋 */
private Node rotateLeft(Node h) {
/*旋转Node h,x*/
Node x = h.right;
h.right = x.left;
x.left = h;
/*交换Node h,x的颜色*/
boolean h_color = h.color;
h.color = x.color;
x.color = h_color;
/*返回旋转后新的取代h的节点*/
return x;
}
右旋转
image.png
/* 右旋 */
private Node rotateRight(Node h) {
/*旋转Node h,x*/
Node x = h.left;
h.left = x.right;
x.right = h;
/*交换Node h,x的颜色*/
boolean h_color = h.color;
h.color = x.color;
x.color = h_color;
/*返回旋转后新的取代h的节点*/
return x;
}
颜色转换
image.png
image.png
/* 颜色转换 */
private void flipColors(Node h) {
h.color = !h.color;
if(h.left != null) h.left.color = !h.left.color;
if(h.right != null) h.right.color = !h.right.color;
}
颜色转换其实就是转换成几-节点(3-节点,4-节点)的问题,并且因为是局部变化,不会影响整棵树的黑色平衡性.
插入
鉴于学习红黑树,其实应该就已经有了二叉查找树,2-3树等的基础,因此我们先不要去分那么多情况讨论,直接看一下往红黑树里面插入一系列节点,并关注它是如何一步步生成红黑树的.
插入新节点的颜色总是红色的,为什么呢？因为插入红色节点不会影响树的黑色平衡性
性质3,但是有可能会破坏性质1,2,不过可以通过旋转和颜色转换来消除插入新节点对树的影响.
redblacktree_5.png
redblacktree_6(1).png
相信通过上面的图我们心里可能也就总结出来这些平衡的情况了.
情况1. 如果右子树是红色但是左子树是黑色,需要进行左旋.
情况2. 如果左子树是红色并且左子树的左子树也是红色,需要进行右旋.
情况3. 如果左右子树都是红色,需要进行颜色转换.
情况1可能会造成情况2,情况2可能会造成情况3.(上面的图中就有例子)
那插入新节点什么时候会对性质2,3构成影响呢？如果确实构成了影响,那也就是以下三种情况.
总结如下:(在1,2,3处插入了新节点)
redblacktree_7.png
private Node balance(Node h) {
if (h == null) return null;
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); //情况1
if (isRed(h.left) && (h.left != null && isRed(h.left.left))) h = rotateRight(h); //情况2
if (isRed(h.left) && isRed(h.right)) flipColors(h); //情况3
return h;
}
public void put(Key key, Value value) {
root = put(root, key, value);
root.color = BLACK;
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, value); // 一定要用h.left接受返回值,因为字树可能旋转更换了节点
else if (cmp > 0) h.right = put(h.right, key, value); // 一定要用h.right接受返回值,因为字树可能旋转更换了节点
else h.value = value; // 更新value值
return balance(h); //每一层都需要检查是否对当前节点有影响
}
验证代码
public void layerTraverse() {
layerTraverse(root);
}
/*
* 横向遍历
*/
private void layerTraverse(Node h) {
if (h == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(h);
while (!queue.isEmpty()) {
Queue<Node> tmp = new LinkedList<Node>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur + " ");
if (cur != null) {
tmp.add(cur.left);
tmp.add(cur.right);
}
}
queue = tmp;
System.out.println();
}
}
public static void main(String[] args) {
RedBlackTree<Character, Integer> rbt = new RedBlackTree<Character, Integer>();
char[] inserts = "SEARCHXMPL".toCharArray();
for (int i = 0; i < inserts.length; i++) {
rbt.put(inserts[i], i);
}
rbt.layerTraverse();
}
输出:
image.png
删除
删除最小键
最小键的性质:在删除最小键的时候,我们先看看最小键有什么性质,显而易见的是最小键的左孩子为空,那最小键的右孩子呢？其实最小键的右孩子也为空. 那试图往最小键的右侧中插入新的键,总共有三种情况如图所示,最终插入后局部调整完还是会构成那三种情况(局部调整不会影响整个树的黑色平衡)
redblacktree_deleteMin(1).png
删除最小键:因为删除红色节点对于树的黑色平衡性没有影响,但是如果最小键是一个黑色节点,直接删除这个最小键树(即使是删除后如果有影响往上调整也不行)就会受到影响.看下图.
redblacktree_10.png
那既然要保证最终的最小键是3-节点或者4-节点,我们需要自上而下保证左孩子是3-节点或者4-节点.删除后再依次从下自上调整红黑树.
至于为什么需要自上而下保证左孩子是3-节点或者4-节点,而不是找
到最小键的父亲节点直接局部构造,看下面一个例子或许你很明白.
redblacktree_11(1).png
那现在来说明一下是如何自上而下构建3-节点和4-节点的？
redblacktree_12.png
接下来看看是如何一步步把前面生成的红黑树通过删除最小键一直到空的. (根节点的颜色不用太在意,因为会总是保持黑色同时也不会对 树产生影响.)
redblacktree_deleteMin_2.png
redblacktree_3(1).png
private Node moveRedLeft(Node h) {
flipColors(h); // 构建4-节点有可能会产生5-节点
if (h.right != null && isRed(h.right.left)) { //生成了5-节点
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h); //分解5-节点 分解成2个2-节点和一个3-节点
}
return h;
}
public void deleteMin() {
root = deleteMin(root);
if (root != null) root.color = BLACK;
}
private Node deleteMin(Node h) {
if (h == null) return null;
if (h.left == null) return null;
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) { //如果左孩子和左孙子都是黑节点 需要构造节点
h = moveRedLeft(h);
}
h.left = deleteMin(h.left);
return balance(h);
}
测试例子
public static void main(String[] args) {
RedBlackTree<Character, Integer> rbt = new RedBlackTree<Character, Integer>();
char[] inserts = "SEARCHXMPL".toCharArray();
for (int i = 0; i < inserts.length; i++) {
rbt.put(inserts[i], i);
}
rbt.layerTraverse();
while (rbt.root != null) {
rbt.deleteMin();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
}
删除最大键
之前已经说过一棵红黑树要求只能左链接是红链接,同样的如果只能右链接是红链接的话也是可以表达一棵黑色平衡的红黑树的.
如果对前面的删除最小键已经理解的话,删除最大键也就是同样的道理了,也是非常好理解的,同样是自上而下构造,只是需要把链接移到右侧.直接看代码吧.
private Node moveRedRight(Node h) {
flipColors(h); // 构建4-节点有可能会产生5-节点
if (h.left != null && isRed(h.left.left)) { //生成了5-节点
h = rotateRight(h);
flipColors(h); //分解5-节点 分解成2个2-节点和一个3-节点
}
return h;
}
public void deleteMax() {
root = deleteMax(root);
if (root != null) root.color = BLACK;
}
private Node deleteMax(Node h) {
if (h == null) return null;
if (isRed(h.left)) h = rotateRight(h);
if (h.right == null) {
if (h.left == null) System.out.println("h.left is null");
return null;
}
if (!isRed(h.right) && (h.right != null && !isRed(h.right.left))) {
h = moveRedRight(h);
}
h.right = deleteMax(h.right);
return balance(h);
}
public static void main(String[] args) {
RedBlackTree<Character, Integer> rbt = new RedBlackTree<Character, Integer>();
char[] inserts = "SEARCHXMPL".toCharArray();
for (int i = 0; i < inserts.length; i++) {
rbt.put(inserts[i], i);
}
rbt.layerTraverse();
while (rbt.root != null) {
rbt.deleteMax();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
}
效果:
redblacktree-15.png
redblacktree_16.png
删除任意键
如果理解了删除最小键和删除最大键,删除任意键也就会比较好理解.
同样在查找路径上进行和删除最小键相同的变换同样可以保证在查找过程中任意当前节点均不是2-节点.1.如果被查找的键在树的底部,我们可以直接删除它.
2.如果不在,我们需要将它和它的后继节点交换,和二叉查找树一样.因为当前节点必然不是2-节点,问题已经转化在一棵根节点不是2-节点的子树中删除最小键.
private Node min (Node h) {
if (h == null) return null;
while (h.left != null) h = h.left;
return h;
}
public void delete(Key key) {
root = delete(root, key);
if (root != null) root.color = BLACK;
}
private Node delete(Node h, Key key) {
if (h == null) return null;
if (key.compareTo(h.key) < 0) {
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) {
h = moveRedLeft(h);
}
h.left = delete(h.left, key);
} else { // 不管是否是要删除的节点 为右侧构造红链接
if (isRed(h.left)) h = rotateRight(h); // 先把红链接调整到右侧
if (key.compareTo(h.key) == 0 && h.right == null) { //在根节点 类似于删除最大键
return null;
}
if (!isRed(h.right) && !isRed(h.right.left)) { //为右侧构造3-节点或4-节点
h = moveRedRight(h);
}
if (key.compareTo(h.key) == 0) {
Node min_of_h_right = min(h.right);
h.key = min_of_h_right.key;
h.value = min_of_h_right.value;
h.right = deleteMin(h.right);
} else {
h.right = delete(h.right, key);
}
}
return balance(h);
}
这是算法4中的写法,它主要思路是自上而下构造3-节点或者4-节点,并且把要删除的节点都旋转到右侧.
测试代码
public static void main(String[] args) {
RedBlackTree<Character, Integer> rbt = new RedBlackTree<Character, Integer>();
char[] inserts = "SEARCHXMPL".toCharArray();
for (int i = 0; i < inserts.length; i++) {
rbt.put(inserts[i], i);
}
rbt.layerTraverse();
/*
while (rbt.root != null) {
rbt.deleteMin();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
while (rbt.root != null) {
rbt.deleteMax();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
*/
char[] dels = "MXCEHA".toCharArray();
for (int i = 0; i < dels.length; i++) {
rbt.delete(dels[i]);
System.out.println("\n---------------------");
rbt.layerTraverse();
}
}
redblacktree_17.png
正常来说按照前面写的二叉树的写法,我自己写了一种.
public void another_delete(Key key) {
root = another_delete(root, key);
if (root != null) root.color = BLACK;
}
private Node another_delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) {
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) {
h = moveRedLeft(h);
}
h.left = another_delete(h.left, key);
} else if (cmp > 0) {
if (isRed(h.left)) h = rotateRight(h); // 先把红链接调整到右侧
if (!isRed(h.right) && !isRed(h.right.left)) { //为右侧构造3-节点或4-节点
h = moveRedRight(h);
}
h.right = another_delete(h.right, key);
} else {
if (h.left == null) {
/*那h.right必然要么是一个红链接,要么为null,因为需要保持黑色平衡性
* 如果出现两个节点,那就必然两个红链接连一起不可能出现
* 如果一个
*/
if (h.right != null) h.right.color = h.color;
h = h.right;
} else if (h.right == null) {
if (h.left != null) h.left.color = h.color;
h = h.left;
} else {
Node min_of_h_right = min(h.right);
h.key = min_of_h_right.key;
h.value = min_of_h_right.value;
h.right = deleteMin(h.right);
}
}
return balance(h);
}
对应的结果：
redblacktree_18(4).png
差别:
从代码中可以看到当找到节点后少了这部分代码
if (isRed(h.left)) h = rotateRight(h); // 先把红链接调整到右侧
if (!isRed(h.right) && !isRed(h.right.left)) { //为右侧构造3-节点或4-节点
h = moveRedRight(h);
}
图中可以看到算法4中会将红链接尽量保持在树的底层节点中,自己的代码是为了让大家更好的明白为什么需要往右侧移动,当然你往左侧移动也是可以.不过还是推荐使用算法4书中的代码.
搜索
搜索是和二叉树一模一样的,就直接放到代码中了.
完整代码
import java.util.LinkedList;
import java.util.Queue;
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; //头节点
private class Node {
Key key; //用来比较的键
Value value; //用来保存真正的值
Node left, right; //左右子节点
/* 是否是红节点 true表示红节点(与父亲节点的链接为红色链接) false表示黑节点(与父亲节点的链接为黑色链接) */
boolean color;
Node(Key key, Value value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
public String toString() {
return "[" + key + "," + value + "," + (color?"RED":"BLACK") + "]";
}
}
private boolean isRed(Node h) {
if (h == null) return false;
return h.color == RED;
}
/* 左旋 */
private Node rotateLeft(Node h) {
/*旋转Node h,x*/
Node x = h.right;
h.right = x.left;
x.left = h;
/*交换Node h,x的颜色*/
boolean h_color = h.color;
h.color = x.color;
x.color = h_color;
/*返回旋转后新的取代h的节点*/
return x;
}
/* 右旋 */
private Node rotateRight(Node h) {
/*旋转Node h,x*/
Node x = h.left;
h.left = x.right;
x.right = h;
/*交换Node h,x的颜色*/
boolean h_color = h.color;
h.color = x.color;
x.color = h_color;
/*返回旋转后新的取代h的节点*/
return x;
}
/* 颜色转换 */
private void flipColors(Node h) {
h.color = !h.color;
if (h.left != null) h.left.color = !h.left.color;
if (h.right != null) h.right.color = !h.right.color;
}
private Node balance(Node h) {
if (h == null) return null;
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); //情况1
if (isRed(h.left) && (h.left != null && isRed(h.left.left))) h = rotateRight(h); //情况2
if (isRed(h.left) && isRed(h.right)) flipColors(h); //情况3
return h;
}
public void put(Key key, Value value) {
root = put(root, key, value);
root.color = BLACK;
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, value); // 一定要用h.left接受返回值,因为字树可能旋转更换了节点
else if (cmp > 0) h.right = put(h.right, key, value); // 一定要用h.right接受返回值,因为字树可能旋转更换了节点
else h.value = value; // 更新value值
return balance(h); //每一层都需要检查是否对当前节点有影响
}
private Node moveRedLeft(Node h) {
flipColors(h); // 构建4-节点有可能会产生5-节点
if (h.right != null && isRed(h.right.left)) { //生成了5-节点
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h); //分解5-节点 分解成2个2-节点和一个3-节点
}
return h;
}
public void deleteMin() {
root = deleteMin(root);
if (root != null) root.color = BLACK;
}
private Node deleteMin(Node h) {
if (h == null) return null;
if (h.left == null) return null;
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) { //如果左孩子和左孙子都是黑节点 需要构造节点
h = moveRedLeft(h);
}
h.left = deleteMin(h.left);
return balance(h);
}
private Node moveRedRight(Node h) {
flipColors(h); // 构建4-节点有可能会产生5-节点
if (h.left != null && isRed(h.left.left)) { //生成了5-节点
h = rotateRight(h);
flipColors(h); //分解5-节点 分解成2个2-节点和一个3-节点
}
return h;
}
public void deleteMax() {
root = deleteMax(root);
if (root != null) root.color = BLACK;
}
private Node deleteMax(Node h) {
if (h == null) return null;
if (isRed(h.left)) h = rotateRight(h);
if (h.right == null) {
if (h.left == null) System.out.println("h.left is null");
return null;
}
if (!isRed(h.right) && (h.right != null && !isRed(h.right.left))) {
h = moveRedRight(h);
}
h.right = deleteMax(h.right);
return balance(h);
}
private Node min (Node h) {
if (h == null) return null;
while (h.left != null) h = h.left;
return h;
}
public void delete(Key key) {
root = delete(root, key);
if (root != null) root.color = BLACK;
}
private Node delete(Node h, Key key) {
if (h == null) return null;
if (key.compareTo(h.key) < 0) {
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) {
h = moveRedLeft(h);
}
h.left = delete(h.left, key);
} else { // 不管是否是要删除的节点 为右侧构造红链接
if (isRed(h.left)) h = rotateRight(h); // 先把红链接调整到右侧
if (key.compareTo(h.key) == 0 && h.right == null) { //在根节点 类似于删除最大键
return null;
}
if (!isRed(h.right) && !isRed(h.right.left)) { //为右侧构造3-节点或4-节点
h = moveRedRight(h);
}
if (key.compareTo(h.key) == 0) {
Node min_of_h_right = min(h.right);
h.key = min_of_h_right.key;
h.value = min_of_h_right.value;
h.right = deleteMin(h.right);
} else {
h.right = delete(h.right, key);
}
}
return balance(h);
}
public void another_delete(Key key) {
root = another_delete(root, key);
if (root != null) root.color = BLACK;
}
private Node another_delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) {
if (!isRed(h.left) && (h.left != null && !isRed(h.left.left))) {
h = moveRedLeft(h);
}
h.left = another_delete(h.left, key);
} else if (cmp > 0) {
if (isRed(h.left)) h = rotateRight(h); // 先把红链接调整到右侧
if (!isRed(h.right) && !isRed(h.right.left)) { //为右侧构造3-节点或4-节点
h = moveRedRight(h);
}
h.right = another_delete(h.right, key);
} else {
if (h.left == null) {
/*那h.right必然要么是一个红链接,要么为null,因为需要保持黑色平衡性
* 如果出现两个节点,那就必然两个红链接连一起不可能出现
* 如果一个
*/
if (h.right != null) h.right.color = h.color;
h = h.right;
} else if (h.right == null) {
if (h.left != null) h.left.color = h.color;
h = h.left;
} else {
Node min_of_h_right = min(h.right);
h.key = min_of_h_right.key;
h.value = min_of_h_right.value;
h.right = deleteMin(h.right);
}
}
return balance(h);
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) return get(h.left, key);
else if (cmp > 0) return get(h.right, key);
return h.value;
}
public void layerTraverse() {
layerTraverse(root);
}
/*
* 横向遍历
*/
private void layerTraverse(Node h) {
if (h == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(h);
while (!queue.isEmpty()) {
Queue<Node> tmp = new LinkedList<Node>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur + " ");
if (cur != null) {
tmp.add(cur.left);
tmp.add(cur.right);
}
}
queue = tmp;
System.out.println();
}
}
public static void main(String[] args) {
RedBlackTree<Character, Integer> rbt = new RedBlackTree<Character, Integer>();
char[] inserts = "SEARCHXMPL".toCharArray();
for (int i = 0; i < inserts.length; i++) {
rbt.put(inserts[i], i);
}
rbt.layerTraverse();
/*
while (rbt.root != null) {6
rbt.deleteMin();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
while (rbt.root != null) {
rbt.deleteMax();
System.out.println("\n---------------------");
rbt.layerTraverse();
}
*/
char[] dels = "MXCEHA".toCharArray();
for (int i = 0; i < dels.length; i++) {
rbt.another_delete(dels[i]);
System.out.println("\n---------------------");
rbt.layerTraverse();
}
System.out.println(rbt.get('L'));
System.out.println(rbt.get('A'));
}
}
参考
1. 算法4 java描述
