引自：https://zhuanlan.zhihu.com/p/24367771
Java代碼實(shí)現(xiàn)
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();
}
}
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());
}
}
紅黑樹是平衡二叉查找樹的一種。為了深入理解紅黑樹，我們需要從二叉查找樹開始講起。
BST
二叉查找樹（Binary Search Tree，簡稱BST）是一棵二叉樹，它的左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值要小，右節(jié)點(diǎn)的值要比父節(jié)點(diǎn)的值大。它的高度決定了它的查找效率。
在理想的情況下，二叉查找樹增刪查改的時間復(fù)雜度為O(logN)（其中N為節(jié)點(diǎn)數(shù)），最壞的情況下為O(N)。當(dāng)它的高度為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;
從程序中可以看出，當(dāng)BST查找的時候，先與當(dāng)前節(jié)點(diǎn)進(jìn)行比較：
- 如果相等的話就返回當(dāng)前節(jié)點(diǎn)；
- 如果少于當(dāng)前節(jié)點(diǎn)則繼續(xù)查找當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)；
- 如果大于當(dāng)前節(jié)點(diǎn)則繼續(xù)查找當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)。
直到當(dāng)前節(jié)點(diǎn)指針為空或者查找到對應(yīng)的節(jié)點(diǎn)，程序查找結(jié)束。
BST的插入操作
Node node = create a new node with specify value
Node root = point the root node of a BST
Node parent = null;
//find the parent node to append the new node
while(true){
if(root==null)break;
parent = root;
if(node.value.compareTo(root.value)<=0){
root = root.left;
}else{
root = root.right;
}
}
if(parent!=null){
if(node.value.compareTo(parent.value)<=0){//append to left
parent.left = node;
}else{//append to right
parent.right = node;
}
}
插入操作先通過循環(huán)查找到待插入的節(jié)點(diǎn)的父節(jié)點(diǎn)，和查找父節(jié)點(diǎn)的邏輯一樣，都是比大小，小的往左，大的往右。找到父節(jié)點(diǎn)后，對比父節(jié)點(diǎn)，小的就插入到父節(jié)點(diǎn)的左節(jié)點(diǎn)，大就插入到父節(jié)點(diǎn)的右節(jié)點(diǎn)上。
BST的刪除操作
刪除操作的步驟如下：
- 查找到要刪除的節(jié)點(diǎn)。
- 如果待刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則直接刪除。
- 如果待刪除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則先找到待刪除節(jié)點(diǎn)的中序遍歷的后繼節(jié)點(diǎn)，用該后繼節(jié)點(diǎn)的值替換待刪除的節(jié)點(diǎn)的值，然后刪除后繼節(jié)點(diǎn)。
BST存在的問題
BST存在的主要問題是，數(shù)在插入的時候會導(dǎo)致樹傾斜，不同的插入順序會導(dǎo)致樹的高度不一樣，而樹的高度直接的影響了樹的查找效率。理想的高度是logN，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上，這樣的樹的高度為N。
RBTree
基于BST存在的問題，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了。平衡樹在插入和刪除的時候，會通過旋轉(zhuǎn)操作將高度保持在logN。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹。AVL樹由于實(shí)現(xiàn)比較復(fù)雜，而且插入和刪除性能差，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹。
紅黑樹（Red-Black Tree，以下簡稱RBTree）的實(shí)際應(yīng)用非常廣泛，比如Linux內(nèi)核中的完全公平調(diào)度器、高精度計時器、ext3文件系統(tǒng)等等，各種語言的函數(shù)庫如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。
RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，在計算幾何中也有重要作用。值得一提的是，Java 8中HashMap的實(shí)現(xiàn)也因?yàn)橛肦BTree取代鏈表，性能有所提升。
RBTree的定義
RBTree的定義如下:
- 任何一個節(jié)點(diǎn)都有顏色，黑色或者紅色
- 根節(jié)點(diǎn)是黑色的
- 父子節(jié)點(diǎn)之間不能出現(xiàn)兩個連續(xù)的紅節(jié)點(diǎn)
- 任何一個節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)，所經(jīng)過的黑節(jié)點(diǎn)個數(shù)必須相等
- 空節(jié)點(diǎn)被認(rèn)為是黑色的
數(shù)據(jù)結(jié)構(gòu)表示如下：
class Node<T>{
public T value;
public Node<T> parent;
public boolean isRed;
public Node<T> left;
public Node<T> right;
}
RBTree在理論上還是一棵BST樹，但是它在對BST的插入和刪除操作時會維持樹的平衡，即保證樹的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN，但實(shí)際上很難遇到）。這樣RBTree的查找時間復(fù)雜度始終保持在O(logN)從而接近于理想的BST。RBTree的刪除和插入操作的時間復(fù)雜度也是O(logN)。RBTree的查找操作就是BST的查找操作。
RBTree的旋轉(zhuǎn)操作
旋轉(zhuǎn)操作(Rotate)的目的是使節(jié)點(diǎn)顏色符合定義，讓RBTree的高度達(dá)到平衡。
Rotate分為left-rotate（左旋）和right-rotate（右旋），區(qū)分左旋和右旋的方法是：待旋轉(zhuǎn)的節(jié)點(diǎn)從左邊上升到父節(jié)點(diǎn)就是右旋，待旋轉(zhuǎn)的節(jié)點(diǎn)從右邊上升到父節(jié)點(diǎn)就是左旋。
RBTree的查找操作
RBTree的查找操作和BST的查找操作是一樣的。請參考BST的查找操作代碼。
RBTree的插入操作
RBTree的插入與BST的插入方式是一致的，只不過是在插入過后，可能會導(dǎo)致樹的不平衡，這時就需要對樹進(jìn)行旋轉(zhuǎn)操作和顏色修復(fù)（在這里簡稱插入修復(fù)），使得它符合RBTree的定義。
新插入的節(jié)點(diǎn)是紅色的，插入修復(fù)操作如果遇到父節(jié)點(diǎn)的顏色為黑則修復(fù)操作結(jié)束。也就是說，只有在父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的時候是需要插入修復(fù)操作的。
插入修復(fù)操作分為以下的三種情況，而且新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)都是紅色的：
- 叔叔節(jié)點(diǎn)也為紅色。
- 叔叔節(jié)點(diǎn)為空，且祖父節(jié)點(diǎn)、父節(jié)點(diǎn)和新節(jié)點(diǎn)處于一條斜線上。
- 叔叔節(jié)點(diǎn)為空，且祖父節(jié)點(diǎn)、父節(jié)點(diǎn)和新節(jié)點(diǎn)不處于一條斜線上。
插入操作-case 1
case 1的操作是將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)與祖父節(jié)點(diǎn)的顏色互換，這樣就符合了RBTRee的定義。即維持了高度的平衡，修復(fù)后顏色也符合RBTree定義的第三條和第四條。下圖中，操作完成后A節(jié)點(diǎn)變成了新的節(jié)點(diǎn)。如果A節(jié)點(diǎn)的父節(jié)點(diǎn)不是黑色的話，則繼續(xù)做修復(fù)操作。
插入操作-case 2
case 2的操作是將B節(jié)點(diǎn)進(jìn)行右旋操作，并且和父節(jié)點(diǎn)A互換顏色。通過該修復(fù)操作RBTRee的高度和顏色都符合紅黑樹的定義。如果B和C節(jié)點(diǎn)都是右節(jié)點(diǎn)的話，只要將操作變成左旋就可以了。
插入操作-case 3
case 3的操作是將C節(jié)點(diǎn)進(jìn)行左旋，這樣就從case 3轉(zhuǎn)換成case 2了，然后針對case 2進(jìn)行操作處理就行了。case 2操作做了一個右旋操作和顏色互換來達(dá)到目的。如果樹的結(jié)構(gòu)是下圖的鏡像結(jié)構(gòu)，則只需要將對應(yīng)的左旋變成右旋，右旋變成左旋即可。
插入操作的總結(jié)
插入后的修復(fù)操作是一個向root節(jié)點(diǎn)回溯的操作，一旦牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義，修復(fù)操作結(jié)束。之所以會向上回溯是由于case 1操作會將父節(jié)點(diǎn)，叔叔節(jié)點(diǎn)和祖父節(jié)點(diǎn)進(jìn)行換顏色，有可能會導(dǎo)致祖父節(jié)點(diǎn)不平衡(紅黑樹定義3)。這個時候需要對祖父節(jié)點(diǎn)為起點(diǎn)進(jìn)行調(diào)節(jié)（向上回溯）。
祖父節(jié)點(diǎn)調(diào)節(jié)后如果還是遇到它的祖父顏色問題，操作就會繼續(xù)向上回溯，直到root節(jié)點(diǎn)為止，根據(jù)定義root節(jié)點(diǎn)永遠(yuǎn)是黑色的。在向上的追溯的過程中，針對插入的3中情況進(jìn)行調(diào)節(jié)。直到符合紅黑樹的定義為止。直到牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義，修復(fù)操作結(jié)束。
如果上面的3中情況如果對應(yīng)的操作是在右子樹上，做對應(yīng)的鏡像操作就是了。
RBTree的刪除操作
刪除操作首先需要做的也是BST的刪除操作，刪除操作會刪除對應(yīng)的節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)就直接刪除，如果是非葉子節(jié)點(diǎn)，會用對應(yīng)的中序遍歷的后繼節(jié)點(diǎn)來頂替要刪除節(jié)點(diǎn)的位置。刪除后就需要做刪除修復(fù)操作，使的樹符合紅黑樹的定義，符合定義的紅黑樹高度是平衡的。
刪除修復(fù)操作在遇到被刪除的節(jié)點(diǎn)是紅色節(jié)點(diǎn)或者到達(dá)root節(jié)點(diǎn)時，修復(fù)操作完畢。
刪除修復(fù)操作是針對刪除黑色節(jié)點(diǎn)才有的，當(dāng)黑色節(jié)點(diǎn)被刪除后會讓整個樹不符合RBTree的定義的第四條。需要做的處理是從兄弟節(jié)點(diǎn)上借調(diào)黑色的節(jié)點(diǎn)過來，如果兄弟節(jié)點(diǎn)沒有黑節(jié)點(diǎn)可以借調(diào)的話，就只能往上追溯，將每一級的黑節(jié)點(diǎn)數(shù)減去一個，使得整棵樹符合紅黑樹的定義。
刪除操作的總體思想是從兄弟節(jié)點(diǎn)借調(diào)黑色節(jié)點(diǎn)使樹保持局部的平衡，如果局部的平衡達(dá)到了，就看整體的樹是否是平衡的，如果不平衡就接著向上追溯調(diào)整。
刪除修復(fù)操作分為四種情況(刪除黑節(jié)點(diǎn)后)：
- 待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色的節(jié)點(diǎn)。
- 待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的。
- 待調(diào)整的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)是紅色的，右節(jié)點(diǎn)是黑色的(兄弟節(jié)點(diǎn)在右邊)，如果兄弟節(jié)點(diǎn)在左邊的話，就是兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)是紅色的，左節(jié)點(diǎn)是黑色的。
- 待調(diào)整的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且右子節(jié)點(diǎn)是是紅色的(兄弟節(jié)點(diǎn)在右邊)，如果兄弟節(jié)點(diǎn)在左邊，則就是對應(yīng)的就是左節(jié)點(diǎn)是紅色的。
刪除操作-case 1
由于兄弟節(jié)點(diǎn)是紅色節(jié)點(diǎn)的時候，無法借調(diào)黑節(jié)點(diǎn)，所以需要將兄弟節(jié)點(diǎn)提升到父節(jié)點(diǎn)，由于兄弟節(jié)點(diǎn)是紅色的，根據(jù)RBTree的定義，兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)是黑色的，就可以從它的子節(jié)點(diǎn)借調(diào)了。
case 1這樣轉(zhuǎn)換之后就會變成后面的case 2，case 3，或者case 4進(jìn)行處理了。上升操作需要對C做一個左旋操作，如果是鏡像結(jié)構(gòu)的樹只需要做對應(yīng)的右旋操作即可。
之所以要做case 1操作是因?yàn)樾值芄?jié)點(diǎn)是紅色的，無法借到一個黑節(jié)點(diǎn)來填補(bǔ)刪除的黑節(jié)點(diǎn)。
刪除操作-case 2
case 2的刪除操作是由于兄弟節(jié)點(diǎn)可以消除一個黑色節(jié)點(diǎn)，因?yàn)樾值芄?jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的，所以可以將兄弟節(jié)點(diǎn)變紅，這樣就可以保證樹的局部的顏色符合定義了。這個時候需要將父節(jié)點(diǎn)A變成新的節(jié)點(diǎn)，繼續(xù)向上調(diào)整，直到整顆樹的顏色符合RBTree的定義為止。
case 2這種情況下之所以要將兄弟節(jié)點(diǎn)變紅，是因?yàn)槿绻研值芄?jié)點(diǎn)借調(diào)過來，會導(dǎo)致兄弟的結(jié)構(gòu)不符合RBTree的定義，這樣的情況下只能是將兄弟節(jié)點(diǎn)也變成紅色來達(dá)到顏色的平衡。當(dāng)將兄弟節(jié)點(diǎn)也變紅之后，達(dá)到了局部的平衡了，但是對于祖父節(jié)點(diǎn)來說是不符合定義4的。這樣就需要回溯到父節(jié)點(diǎn)，接著進(jìn)行修復(fù)操作。
刪除操作-case 3
case 3的刪除操作是一個中間步驟，它的目的是將左邊的紅色節(jié)點(diǎn)借調(diào)過來，這樣就可以轉(zhuǎn)換成case 4狀態(tài)了，在case 4狀態(tài)下可以將D，E節(jié)點(diǎn)都階段過來，通過將兩個節(jié)點(diǎn)變成黑色來保證紅黑樹的整體平衡。
之所以說case-3是一個中間狀態(tài)，是因?yàn)楦鶕?jù)紅黑樹的定義來說，下圖并不是平衡的，他是通過case 2操作完后向上回溯出現(xiàn)的狀態(tài)。之所以會出現(xiàn)case 3和后面的case 4的情況，是因?yàn)榭梢酝ㄟ^借用侄子節(jié)點(diǎn)的紅色，變成黑色來符合紅黑樹定義4.
刪除操作-case 4
Case 4的操作是真正的節(jié)點(diǎn)借調(diào)操作，通過將兄弟節(jié)點(diǎn)以及兄弟節(jié)點(diǎn)的右節(jié)點(diǎn)借調(diào)過來，并將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)變成紅色來達(dá)到借調(diào)兩個黑節(jié)點(diǎn)的目的，這樣的話，整棵樹還是符合RBTree的定義的。
Case 4這種情況的發(fā)生只有在待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑，且子節(jié)點(diǎn)不全部為黑，才有可能借調(diào)到兩個節(jié)點(diǎn)來做黑節(jié)點(diǎn)使用，從而保持整棵樹都符合紅黑樹的定義。
刪除操作的總結(jié)
紅黑樹的刪除操作是最復(fù)雜的操作，復(fù)雜的地方就在于當(dāng)刪除了黑色節(jié)點(diǎn)的時候，如何從兄弟節(jié)點(diǎn)去借調(diào)節(jié)點(diǎn)，以保證樹的顏色符合定義。由于紅色的兄弟節(jié)點(diǎn)是沒法借調(diào)出黑節(jié)點(diǎn)的，這樣只能通過選擇操作讓他上升到父節(jié)點(diǎn)，而由于它是紅節(jié)點(diǎn)，所以它的子節(jié)點(diǎn)就是黑的，可以借調(diào)。
對于兄弟節(jié)點(diǎn)是黑色節(jié)點(diǎn)的可以分成3種情況來處理，當(dāng)所以的兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色節(jié)點(diǎn)時，可以直接將兄弟節(jié)點(diǎn)變紅，這樣局部的紅黑樹顏色是符合定義的。但是整顆樹不一定是符合紅黑樹定義的，需要往上追溯繼續(xù)調(diào)整。
對于兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)為左紅右黑或者 (全部為紅，右紅左黑)這兩種情況，可以先將前面的情況通過選擇轉(zhuǎn)換為后一種情況，在后一種情況下，因?yàn)樾值芄?jié)點(diǎn)為黑，兄弟節(jié)點(diǎn)的右節(jié)點(diǎn)為紅，可以借調(diào)出兩個節(jié)點(diǎn)出來做黑節(jié)點(diǎn)，這樣就可以保證刪除了黑節(jié)點(diǎn)，整棵樹還是符合紅黑樹的定義的，因?yàn)楹谏?jié)點(diǎn)的個數(shù)沒有改變。
紅黑樹的刪除操作是遇到刪除的節(jié)點(diǎn)為紅色，或者追溯調(diào)整到了root節(jié)點(diǎn)，這時刪除的修復(fù)操作完畢。
引用：https://zhuanlan.zhihu.com/p/31805309
https://juejin.im/entry/58371f13a22b9d006882902d
https://blog.csdn.net/v_JULY_v/article/details/6285620
