红黑树
前言
红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。
下面主要以下几个方面学习一下红黑树。 1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。
二叉查找树BST
二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。
二叉查找树（BST）具备什么特性呢？
1、左子树上所有结点的值均小于或等于它的根结点的值。 2、右子树上所有结点的值均大于或等于它的根结点的值。 3、左、右子树也分别为二叉排序树。
在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。至于这结论如何得出来的，那就继续往下看。
BST的查找操作
T key = a search key
Node root = point to the root of a BST
while(true){
if(root==null){
break;
}
if(root.value.equals(key)){
return root;
}
else if(key.compareTo(root.value)<0){
root = root.left;
}
else{
root = root.right;
}
}
return null;下图中这棵树，就是一颗典型的二叉查找树：
比如我们现在要查询数值10，从上图就可以看出，10位于叶子节点，所以查询（二分查找）的次数就是树的高度，也就是说时间复杂度为O(logN)。
但是它还是有个缺陷的。假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12，接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成下图这个样子。
从图中可以看到，BST存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
基于这个问题的，那么就有了红黑树的诞生。
红黑树RBTree
基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。
特征
除了符合二叉查找树的特征以外，红黑树还有以下特征：
1、节点是红色或黑色。 2、根节点是黑色。 3、每个叶子节点都是黑色的空节点（NIL节点）。 4、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图中这棵树，就是一颗典型的红黑树：
什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：
添加节点
1.向原红黑树插入值为14的新节点：
由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。
2.向原红黑树插入值为21的新节点：
由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。
变色：为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：
但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：
左旋转：
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：
图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。
右旋转：
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：
图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。
我们以刚才插入节点21的情况为例：
首先，我们需要做的是变色，把节点25及其下方的节点变色：
此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。
变色已无法解决问题，我们把节点13看做X，把节点17看做Y，像刚才的示意图那样进行左旋转：
由于根节点必须是黑色节点，所以需要变色，变色结果如下：
这样就结束了吗？并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。
这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转：
最后根据规则来进行变色：
如此一来，我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂，经历了如下步骤： 变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色
RBTree的查找操作
RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。
关于红黑树自平衡的调整，插入和删除节点的时候都涉及到很多种Case，由于篇幅原因无法展开来一一列举，有兴趣的朋友可以参考维基百科，里面讲的非常清晰。
RBTree的Java实现
RBTreeNode 的定义
public class RBTreeNode <T extends Comparable<T>> {
private T value;//node value
private RBTreeNode<T> left;//left child pointer
private RBTreeNode<T> right;//right child pointer
private RBTreeNode<T> parent;//parent pointer
private boolean red;//color is red or not red
public RBTreeNode(){}
public RBTreeNode(T value){this.value=value;}
public RBTreeNode(T value,boolean isRed){this.value=value;this.red = isRed;}
public T getValue() {
return value;
}
void setValue(T value) {
this.value = value;
}
RBTreeNode<T> getLeft() {
return left;
}
void setLeft(RBTreeNode<T> left) {
this.left = left;
}
RBTreeNode<T> getRight() {
return right;
}
void setRight(RBTreeNode<T> right) {
this.right = right;
}
RBTreeNode<T> getParent() {
return parent;
}
void setParent(RBTreeNode<T> parent) {
this.parent = parent;
}
boolean isRed() {
return red;
}
boolean isBlack(){
return !red;
}
/**
* is leaf node
**/
boolean isLeaf(){
return left==null && right==null;
}
void setRed(boolean red) {
this.red = red;
}
void makeRed(){
red=true;
}
void makeBlack(){
red=false;
}
@Override
public String toString(){
return value.toString();
}
}RBTree 的增、删、查等操作
public class RBTree <T extends Comparable<T>> {
private final RBTreeNode<T> root;
//node number
private java.util.concurrent.atomic.AtomicLong size =
new java.util.concurrent.atomic.AtomicLong(0);
//in overwrite mode,all node's value can not has same value
//in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.
private volatile boolean overrideMode = true;
public RBTree() {
this.root = new RBTreeNode<T>();
}
public RBTree(boolean overrideMode) {
this();
this.overrideMode = overrideMode;
}
public boolean isOverrideMode() {
return overrideMode;
}
public void setOverrideMode(boolean overrideMode) {
this.overrideMode = overrideMode;
}
/**
* number of tree number
*
* @return
*/
public long getSize() {
return size.get();
}
/**
* get the root node
*
* @return
*/
private RBTreeNode<T> getRoot() {
return root.getLeft();
}
/**
* add value to a new node,if this value exist in this tree,
* if value exist,it will return the exist value.otherwise return null
* if override mode is true,if value exist in the tree,
* it will override the old value in the tree
*
* @param value
* @return
*/
public T addNode(T value) {
RBTreeNode<T> t = new RBTreeNode<T>(value);
return addNode(t);
}
/**
* find the value by give value(include key,key used for search,
* other field is not used,@see compare method).if this value not exist return null
*
* @param value
* @return
*/
public T find(T value) {
RBTreeNode<T> dataRoot = getRoot();
while (dataRoot != null) {
int cmp = dataRoot.getValue().compareTo(value);
if (cmp < 0) {
dataRoot = dataRoot.getRight();
} else if (cmp > 0) {
dataRoot = dataRoot.getLeft();
} else {
return dataRoot.getValue();
}
}
return null;
}
/**
* remove the node by give value,if this value not exists in tree return null
*
* @param value include search key
* @return the value contain in the removed node
*/
public T remove(T value) {
RBTreeNode<T> dataRoot = getRoot();
RBTreeNode<T> parent = root;
while (dataRoot != null) {
int cmp = dataRoot.getValue().compareTo(value);
if (cmp < 0) {
parent = dataRoot;
dataRoot = dataRoot.getRight();
} else if (cmp > 0) {
parent = dataRoot;
dataRoot = dataRoot.getLeft();
} else {
if (dataRoot.getRight() != null) {
RBTreeNode<T> min = removeMin(dataRoot.getRight());
//x used for fix color balance
RBTreeNode<T> x = min.getRight() == null ? min.getParent() : min.getRight();
boolean isParent = min.getRight() == null;
min.setLeft(dataRoot.getLeft());
setParent(dataRoot.getLeft(), min);
if (parent.getLeft() == dataRoot) {
parent.setLeft(min);
} else {
parent.setRight(min);
}
setParent(min, parent);
boolean curMinIsBlack = min.isBlack();
//inherit dataRoot's color
min.setRed(dataRoot.isRed());
if (min != dataRoot.getRight()) {
min.setRight(dataRoot.getRight());
setParent(dataRoot.getRight(), min);
}
//remove a black node,need fix color
if (curMinIsBlack) {
if (min != dataRoot.getRight()) {
fixRemove(x, isParent);
} else if (min.getRight() != null) {
fixRemove(min.getRight(), false);
} else {
fixRemove(min, true);
}
}
} else {
setParent(dataRoot.getLeft(), parent);
if (parent.getLeft() == dataRoot) {
parent.setLeft(dataRoot.getLeft());
} else {
parent.setRight(dataRoot.getLeft());
}
//current node is black and tree is not empty
if (dataRoot.isBlack() && !(root.getLeft() == null)) {
RBTreeNode<T> x = dataRoot.getLeft() == null
? parent : dataRoot.getLeft();
boolean isParent = dataRoot.getLeft() == null;
fixRemove(x, isParent);
}
}
setParent(dataRoot, null);
dataRoot.setLeft(null);
dataRoot.setRight(null);
if (getRoot() != null) {
getRoot().setRed(false);
getRoot().setParent(null);
}
size.decrementAndGet();
return dataRoot.getValue();
}
}
return null;
}
/**
* fix remove action
*
* @param node
* @param isParent
*/
private void fixRemove(RBTreeNode<T> node, boolean isParent) {
RBTreeNode<T> cur = isParent ? null : node;
boolean isRed = isParent ? false : node.isRed();
RBTreeNode<T> parent = isParent ? node : node.getParent();
while (!isRed && !isRoot(cur)) {
RBTreeNode<T> sibling = getSibling(cur, parent);
//sibling is not null,due to before remove tree color is balance
//if cur is a left node
boolean isLeft = parent.getRight() == sibling;
if (sibling.isRed() && !isLeft) {//case 1
//cur in right
parent.makeRed();
sibling.makeBlack();
rotateRight(parent);
} else if (sibling.isRed() && isLeft) {
//cur in left
parent.makeRed();
sibling.makeBlack();
rotateLeft(parent);
} else if (isBlack(sibling.getLeft()) && isBlack(sibling.getRight())) {//case 2
sibling.makeRed();
cur = parent;
isRed = cur.isRed();
parent = parent.getParent();
} else if (isLeft && !isBlack(sibling.getLeft())
&& isBlack(sibling.getRight())) {//case 3
sibling.makeRed();
sibling.getLeft().makeBlack();
rotateRight(sibling);
} else if (!isLeft && !isBlack(sibling.getRight())
&& isBlack(sibling.getLeft())) {
sibling.makeRed();
sibling.getRight().makeBlack();
rotateLeft(sibling);
} else if (isLeft && !isBlack(sibling.getRight())) {//case 4
sibling.setRed(parent.isRed());
parent.makeBlack();
sibling.getRight().makeBlack();
rotateLeft(parent);
cur = getRoot();
} else if (!isLeft && !isBlack(sibling.getLeft())) {
sibling.setRed(parent.isRed());
parent.makeBlack();
sibling.getLeft().makeBlack();
rotateRight(parent);
cur = getRoot();
}
}
if (isRed) {
cur.makeBlack();
}
if (getRoot() != null) {
getRoot().setRed(false);
getRoot().setParent(null);
}
}
//get sibling node
private RBTreeNode<T> getSibling(RBTreeNode<T> node, RBTreeNode<T> parent) {
parent = node == null ? parent : node.getParent();
if (node == null) {
return parent.getLeft() == null ? parent.getRight() : parent.getLeft();
}
if (node == parent.getLeft()) {
return parent.getRight();
} else {
return parent.getLeft();
}
}
private boolean isBlack(RBTreeNode<T> node) {
return node == null || node.isBlack();
}
private boolean isRoot(RBTreeNode<T> node) {
return root.getLeft() == node && node.getParent() == null;
}
/**
* find the successor node
*
* @param node current node's right node
* @return
*/
private RBTreeNode<T> removeMin(RBTreeNode<T> node) {
//find the min node
RBTreeNode<T> parent = node;
while (node != null && node.getLeft() != null) {
parent = node;
node = node.getLeft();
}
//remove min node
if (parent == node) {
return node;
}
parent.setLeft(node.getRight());
setParent(node.getRight(), parent);
//don't remove right pointer,it is used for fixed color balance
//node.setRight(null);
return node;
}
private T addNode(RBTreeNode<T> node) {
node.setLeft(null);
node.setRight(null);
node.setRed(true);
setParent(node, null);
if (root.getLeft() == null) {
root.setLeft(node);
//root node is black
node.setRed(false);
size.incrementAndGet();
} else {
RBTreeNode<T> x = findParentNode(node);
int cmp = x.getValue().compareTo(node.getValue());
if (this.overrideMode && cmp == 0) {
T v = x.getValue();
x.setValue(node.getValue());
return v;
} else if (cmp == 0) {
//value exists,ignore this node
return x.getValue();
}
setParent(node, x);
if (cmp > 0) {
x.setLeft(node);
} else {
x.setRight(node);
}
fixInsert(node);
size.incrementAndGet();
}
return null;
}
/**
* find the parent node to hold node x,if parent value equals x.value return parent.
*
* @param x
* @return
*/
private RBTreeNode<T> findParentNode(RBTreeNode<T> x) {
RBTreeNode<T> dataRoot = getRoot();
RBTreeNode<T> child = dataRoot;
while (child != null) {
int cmp = child.getValue().compareTo(x.getValue());
if (cmp == 0) {
return child;
}
if (cmp > 0) {
dataRoot = child;
child = child.getLeft();
} else if (cmp < 0) {
dataRoot = child;
child = child.getRight();
}
}
return dataRoot;
}
/**
* red black tree insert fix.
*
* @param x
*/
private void fixInsert(RBTreeNode<T> x) {
RBTreeNode<T> parent = x.getParent();
while (parent != null && parent.isRed()) {
RBTreeNode<T> uncle = getUncle(x);
if (uncle == null) {//need to rotate
RBTreeNode<T> ancestor = parent.getParent();
//ancestor is not null due to before before add,tree color is balance
if (parent == ancestor.getLeft()) {
boolean isRight = x == parent.getRight();
if (isRight) {
rotateLeft(parent);
}
rotateRight(ancestor);
if (isRight) {
x.setRed(false);
parent = null;//end loop
} else {
parent.setRed(false);
}
ancestor.setRed(true);
} else {
boolean isLeft = x == parent.getLeft();
if (isLeft) {
rotateRight(parent);
}
rotateLeft(ancestor);
if (isLeft) {
x.setRed(false);
parent = null;//end loop
} else {
parent.setRed(false);
}
ancestor.setRed(true);
}
} else {//uncle is red
parent.setRed(false);
uncle.setRed(false);
parent.getParent().setRed(true);
x = parent.getParent();
parent = x.getParent();
}
}
getRoot().makeBlack();
getRoot().setParent(null);
}
/**
* get uncle node
*
* @param node
* @return
*/
private RBTreeNode<T> getUncle(RBTreeNode<T> node) {
RBTreeNode<T> parent = node.getParent();
RBTreeNode<T> ancestor = parent.getParent();
if (ancestor == null) {
return null;
}
if (parent == ancestor.getLeft()) {
return ancestor.getRight();
} else {
return ancestor.getLeft();
}
}
private void rotateLeft(RBTreeNode<T> node) {
RBTreeNode<T> right = node.getRight();
if (right == null) {
throw new java.lang.IllegalStateException("right node is null");
}
RBTreeNode<T> parent = node.getParent();
node.setRight(right.getLeft());
setParent(right.getLeft(), node);
right.setLeft(node);
setParent(node, right);
if (parent == null) {//node pointer to root
//right raise to root node
root.setLeft(right);
setParent(right, null);
} else {
if (parent.getLeft() == node) {
parent.setLeft(right);
} else {
parent.setRight(right);
}
//right.setParent(parent);
setParent(right, parent);
}
}
private void rotateRight(RBTreeNode<T> node) {
RBTreeNode<T> left = node.getLeft();
if (left == null) {
throw new java.lang.IllegalStateException("left node is null");
}
RBTreeNode<T> parent = node.getParent();
node.setLeft(left.getRight());
setParent(left.getRight(), node);
left.setRight(node);
setParent(node, left);
if (parent == null) {
root.setLeft(left);
setParent(left, null);
} else {
if (parent.getLeft() == node) {
parent.setLeft(left);
} else {
parent.setRight(left);
}
setParent(left, parent);
}
}
private void setParent(RBTreeNode<T> node, RBTreeNode<T> parent) {
if (node != null) {
node.setParent(parent);
if (parent == root) {
node.setParent(null);
}
}
}
/**
* debug method,it used print the given node and its children nodes,
* every layer output in one line
*
* @param root
*/
public void printTree(RBTreeNode<T> root) {
java.util.LinkedList<RBTreeNode<T>> queue = new java.util.LinkedList<RBTreeNode<T>>();
java.util.LinkedList<RBTreeNode<T>> queue2 = new java.util.LinkedList<RBTreeNode<T>>();
if (root == null) {
return;
}
queue.add(root);
boolean firstQueue = true;
while (!queue.isEmpty() || !queue2.isEmpty()) {
java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2;
RBTreeNode<T> n = q.poll();
if (n != null) {
String pos = n.getParent() == null ? "" : (n == n.getParent().getLeft()
? " LE" : " RI");
String pstr = n.getParent() == null ? "" : n.getParent().toString();
String cstr = n.isRed() ? "R" : "B";
cstr = n.getParent() == null ? cstr : cstr + " ";
System.out.print(n + "(" + (cstr) + pstr + (pos) + ")" + "\t");
if (n.getLeft() != null) {
(firstQueue ? queue2 : queue).add(n.getLeft());
}
if (n.getRight() != null) {
(firstQueue ? queue2 : queue).add(n.getRight());
}
} else {
System.out.println();
firstQueue = !firstQueue;
}
}
}
public static void main(String[] args) {
RBTree<String> bst = new RBTree<String>();
bst.addNode("d");
bst.addNode("d");
bst.addNode("c");
bst.addNode("c");
bst.addNode("b");
bst.addNode("f");
bst.addNode("a");
bst.addNode("e");
bst.addNode("g");
bst.addNode("h");
bst.remove("c");
bst.printTree(bst.getRoot());
// 代码调试的时候，printTree输出格式如下:
// d(B)
// b(B d LE) g(R d RI)
// a(R b LE) e(B g LE) h(B g RI)
// f(R e RI)
//
// 括号左边表示元素的内容。括号内的第一个元素表示颜色，B表示black，R表示red；第二个元素表示父元素的值；第三个元素表示左右，LE表示在父元素的左边。RI表示在父元素的右边。
//
// 第一个元素d是root节点，由于它没有父节点，所以括号内只有一个元素。
}
}参考文章
https://www.zhihu.com/tardis/sogou/art/24367771 https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 《漫画：什么是红黑树？》-- 程序员小灰
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录