紅黑樹（Red Black Tree）

• 紅黑樹也是一種自平衡的二叉搜索樹，
  
• 以前也叫做平衡二叉B樹（Symmetric Binary B-tree）
• 紅黑樹必須滿足以下 5 條性質
  ①、節點是RED或者BLACK
  ②、根節點是BLACK
  ③、葉子節點（外部節點，空節點）都是 BLACK
  ④、RED節點的子節點都是BLACK
  ? RED節點的parent都是BLACK
  ? 從根節點到葉子節點的所有路徑上不能有 2 個連續的RED節點
  ⑤、從任一節點到葉子節點的所有路徑都包含相同數目的BLACK節點

（一）紅黑樹的等價變換

• 紅黑樹 和 4階B樹（2-3-4樹）具有等價性
• BLACK節點與它的 RED 子節點融合在一起，形成1個B樹節點
• 紅黑樹的 BLACK 節點個數 與 4階B樹的節點總個數 相等
• 網上有些教程：用 2-3樹 與 紅黑樹 進行類比，這是極其不嚴謹的，2-3樹 并不能完美匹配 紅黑樹 的所有情況
• 注意：后面展示的紅黑樹都會省略 NULL 節點

（二）紅黑樹 vs 2-3-4樹

• 思考：如果上圖最底層的 BLACK 節點是不存在的，在B樹中是什么樣的情形？
  整棵B樹只有1個節點，而且是超級節點

（三）紅黑樹單詞對應

• parent：父節點
• sibling：兄弟節點
• uncle：叔父節點（ parent 的兄弟節點）
• grand：祖父節點（ parent 的父節點）

1.輔助函式

import java.util.Comparator;

public class RBTree<E> extends BST<E> {
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	
	public RBTree() {
		this(null);
	}
	public RBTree(Comparator<E> comparator) {
		super(comparator);
	}
	//染色(給誰染色就回傳誰)
	private Node<E> color(Node<E> node,boolean color) {
		if (node == null) return node;
		((RBNode<E>)node).color = color;//染色 
		return node;
	}
	//將其染成紅色
	private Node<E> red(Node<E> node){
		return color(node, RED);
	}
	//將其染成黑色
	private Node<E> black(Node<E> node){
		return color(node, BLACK);
	}
	//判斷某個節點當前是什么顏色
	private boolean colorOf(Node<E> node) {
		return node == null ? BLACK : ((RBNode<E>)node).color;
	}
	//判斷是否為黑色
	private boolean isBlack(Node<E> node) {
		return colorOf(node) == BLACK;
	}
	//判斷是否為黑色
	private boolean isRed(Node<E> node) {
		return colorOf(node) == RED;
	}
	private static class RBNode<E> extends Node<E>{
		boolean color = RED;
		public RBNode(E element, Node<E> parent) {
			super(element, parent);
		}
	}
}

（四）添加

• 已知
  ①、B樹中，新元素必定是添加到葉子節點中
  ②、4階B樹所有節點的元素個數 x 都符合 1 ≤ x ≤ 3
• 建議新添加的節點默認為 RED，這樣能夠讓紅黑樹的性質盡快滿足（性質 1、2、3、5 都滿足，性質 4 不一定）
  
• 如果添加的是根節點，染成BLACK 即可

1、添加的所有情況

• 有 4 種情況滿足紅黑樹的性質 4 ：parent為 BLACK
  ①、同樣也滿足 4階B樹 的性質
  ②、因此不用做任何額外處理
  
• 有 8 種情況不滿足紅黑樹的性質 4 ：parent為 RED（ Double Red ）
  ①、其中前 4 種屬于B樹節點上溢的情況
  

（1）、添加 – 修復性質4 – LL\RR

• 判定條件：uncle不是RED
  ①、parent染成 BLACK，grand 染成 RED
  ②、grand進行單旋操作
• LL：右旋轉
• RR：左旋轉

（2）、添加 – 修復性質4 – LR\RL

• 判定條件：uncle不是 RED
  ①、自己染成 BLACK，grand染成 RED
  ②、進行雙旋操作
• LR：parent 左旋轉， grand 右旋轉
• RL：parent 右旋轉， grand 左旋轉

（3）、添加 – 修復性質4 – 上溢 – LL

• 判定條件：uncle是 RED
  ①、parent、uncle染成 BLACK
  ②、grand向上合并
• 染成 RED，當做是新添加的節點進行處理
  
• grand向上合并時，可能繼續發生上溢
• 若上溢位續到根節點，只需將根節點染成 BLACK

（4）、添加 – 修復性質4 – 上溢 – RR

• 判定條件：uncle是RED
  ①、parent、uncle染成 BLACK
  ②、grand向上合并
• 染成 RED，當做是新添加的節點進行處理
  

（5）、添加 – 修復性質4 – 上溢 – LR

• 判定條件：uncle是RED
  ①、parent、uncle染成 BLACK
  ②、grand向上合并
• 染成 RED，當做是新添加的節點進行處理

（6）、添加 – 修復性質4 – 上溢 – RL

• 判定條件：uncle是RED
  ①、parent、uncle染成 BLACK
  ②、grand向上合并
• 染成 RED，當做是新添加的節點進行處理

public class RBTree<E> extends BBST<E> {
	private static final boolean RED = false;
	private static final boolean BLACK = true;

	@Override
	protected void afterAdd(Node<E> node) {
		Node<E> parent = node.parent;
	
		//添加的是根節點
		if (parent == null) {
			black(node);
			return;
		}
		
		//如果父節點是黑色，直接回傳
		if(isBlack(parent)) return;
		//叔父節點
		Node<E> uncle = parent.sibling();
		//祖父節點
		Node<E> grand = parent.parent;
		if (isRed(uncle)) {//叔父節點是紅色
			black(parent);
			black(uncle);
			//把祖父節點當做是新添加的節點
			afterAdd(red(grand));
			return;
		}
		//叔父節點不是紅色
		if (parent.isLeftChild()) {//  L
			red(grand);
			if (node.isLeftChild()) {// LL
				black(parent);
			}else {// LR
				black(node);
				rotateLeft(parent);
			}
			rotateRight(grand);
		}else {// R
			red(grand);
			if (node.isLeftChild()) {// RL
				black(node);
				rotateRight(parent);
			}else {// RR
				black(parent);
			}
			rotateLeft(grand);
		}
	}
	//染色(給誰染色就回傳誰)
	private Node<E> color(Node<E> node,boolean color) {
		if (node == null) return node;
		((RBNode<E>)node).color = color;//染色 
		return node;
	}
	//將其染成紅色
	private Node<E> red(Node<E> node){
		return color(node, RED);
	}
	//將其染成黑色
	private Node<E> black(Node<E> node){
		return color(node, BLACK);
	}
	//判斷某個節點當前是什么顏色
	private boolean colorOf(Node<E> node) {
		return node == null ? BLACK : ((RBNode<E>)node).color;
	}
	//判斷是否為黑色
	private boolean isBlack(Node<E> node) {
		return colorOf(node) == BLACK;
	}
	//判斷是否為黑色
	private boolean isRed(Node<E> node) {
		return colorOf(node) == RED;
	}
	@Override
	protected Node<E> createNode(E element, Node<E> parent) {
		return new RBNode<>(element, parent);
	}
	private static class RBNode<E> extends Node<E>{
		boolean color = RED;
		public RBNode(E element, Node<E> parent) {
			super(element, parent);
		}
		
		@Override
		public String toString() {
			String str = "";
			if (color == RED) {
				str = "R_";
			}
			return str + element.toString();
		}
	}
}

import com.mj.printer.BinaryTrees;
import com.mj.tree.BinaryTree;
import com.mj.tree.RBTree;
public class Main {
	
	static void test3() {
		Integer data[] = new Integer[] {
				55,87,56,74,96,22,62,20,70,68,90,50
		};
		RBTree<Integer> rb = new RBTree<>();
		for (int i = 0; i < data.length; i++) {
			rb.add(data[i]);
		}
		BinaryTrees.println(rb);
	}
	public static void main(String[] args) {
		test3();
	}
}

        ┌────70───┐
        │         │
     ┌─56─┐     ┌─87─┐
     │    │     │    │
 ┌─R_22─┐ 62─┐ 74  ┌─96
 │      │    │     │
20    ┌─55  R_68 R_90
      │
    R_50