前言

紅黑樹是自平衡的二叉查詢樹，在許多地方都有實際應用比如JAVA的HashMap，在連結串列長度大於8就會轉化為紅黑樹；在linux經典的epoll中也使用了紅黑樹來儲存檔案描述符的插入刪除操作。++如果頻繁地對資料進行插入刪除，還要保證效率，使用紅黑樹是比較好的選擇。++

紅黑樹在實際表現上，還是一顆二叉樹。在許多性質上和二叉樹一樣，所以要從二叉樹查詢開始講起。

二叉查詢樹

二叉查詢樹是最簡單的實現，規定左子節點一定小於右子節點。

插入情況只需要對當前節點比大小，不斷的遞迴直到遇到空節點插入。

查詢和插入相同，不斷比大小即可，在這一點上紅黑樹和二叉查詢樹是一致的。

//最小值func min(x *node) *node {	if x.left == nil {		return x	}	return Min(x.left)}//最大值func max(x *node) *node {	if x.right == nil {		return x	}	return Max(x.right)}//刪除最小值func deleteMin(x *node) *node {	if x.left == nil {		return nil	}	x.left = deleteMin(x.left)	x.n = size(x.left) + size(x.right) + 1}//刪除最大值只需要改變程式碼中left為right

刪除最大值或最小值就是找到那個節點然後斷開，再把那個節點的子節點連線上它的父節點，因為最小值那個節點的子節點只可能有一個

 public Node delete(Node x, Key key) {        if (x == null) {            return null;        }        int cmp = key.compareTo(x.key);        if (cmp > 0) {            x.right = delete(x.right, key);        } else if (cmp < 0) {            x.left = delete(x.left, key);        } else {            Node t = x;            x = min(t.right);            x.right = deleteMin(t.right);            x.left = t.left;        }        x.n = size(x.left) + size(x.right) + 1;        return x;    }

不斷遞迴找到需要刪除的點，然後斷開該點的前後連線，刪除它右子節點的最小節點來替代原來的位置

2-3樹

普通二叉查詢樹無法適應最壞情況，如果有一種樹能夠適應各種不同的資料情況，讓執行情況都在對數級別，就能夠解決二叉樹查詢樹不穩定的缺點。

為了解決這種情況，保證樹的平衡性，適當地改造一下二叉樹，普通的二叉樹只儲存一個值和兩個左右節點，現在將樹改造成一個節點能夠儲存2個值，而有三條指標指向其他節點，形成左-中-右節點，這樣的節點稱為3-節點

如圖，一棵樹存在以上兩種節點，3-節點中間的節點表示：左值<中節點<右值

對於這樣的節點，在插入節點的時候需要一些變換才能保證樹的平衡性

情況1：插入的節點是2-節點

直接將2-節點變成3-節點

情況2：插入的節點是個3-節點

如圖，重新構造3-節點，浮動到父節點

情況3：父節點是3-節點，對父節點插入

父節點是3-節點，對其進行插入，會使得父節點分裂成3個2-節點

++上面只是展示了幾種情況，實際上如果在樹中間插入一個節點，在節點變換的時候還要考慮子節點的情況，新增一個新的3-節點，需要將原有的2-節點進行復制，維護兩種不同的節點，增加了額外的開銷，實在是有些得不償失++

紅黑樹

對於2-3樹需要新增3-節點的資料結構，雖然有缺點，但是理解實現起來並不複雜，完全可以用標準二叉樹的結構，只需要增加額外的資訊就可以來表示3-節點。

在內部使用一條紅色的節點來表示3-節點，a這個節點的為紅節點

//節點表示程式碼 go語言實現，後面方一個java版本const (	BLACK = false	RED   = true)//節點type node struct {	key         int	val         interface{}	left, right *node	n           int	color       bool}func newRedNode(key int, val interface{}) *node {	return &node{		key:   key,		val:   val,		n:     1,		color: RED,	}}//紅黑樹結構type RedBlackTree struct {	root *node}func (b *RedBlackTree) size(x *node) int {	if x == nil {		return 0	}	return x.n}func (b *RedBlackTree) Size() int {	return b.size(b.root)}

n表示該節點下面還有多少節點，插入新節點總是紅色，用布林型別來表示紅黑

把紅黑樹比作2-3樹的表示方式，那麼紅黑樹是平衡的，紅黑樹滿足以下條件：

紅連結均為左邊（ps：方便3-節點的表示）任何一個節點不能同時和紅連結連線（ps：不然一個節點變成了4-樹）跟節點不能是紅連結

以上這三條規則共同組成了紅黑樹的規則：++任意一條空連結到root節點的距離都是相等的。（只算黑連結的距離，不計算紅連結）++

紅黑樹的插入情況和上面圖片中2-3樹的三種情況一樣，但是隻需要維護紅連結的規則即可，規則3很容易解決，只需要將root節點的連線設定為BLACK就行了，主要是考慮另外兩種情況

違反規則1

對於（1）情況，只需要將節點插入就行了，不需要做其他操作，因為插入總是在樹底插入，而且紅連結也是在左邊，符合規則。

對於（2）情況，插入是在右邊，就違背了規則1，需要將（2）變為（1）相同的結構，需要一個操作叫旋轉。

左旋程式碼很簡單，只需改變一下連線關係

func (b *RedBlackTree) rotateLeft(h *node) *node {	x := h.right	h.right = x.left	x.left = h	x.color = h.color	h.color = RED	x.n = h.n	h.n = b.size(h.left) + b.size(h.right) + 1	return x}

注意旋轉要改變節點的數量，目標節點會增加

違反規則2

違反規則2在插入時候可能會出現(1)(2)兩種情況，最終是要變為（3）這種情況（如果3情況是跟節點，只需要將頭部的紅色連結變為黑色）,如果是（1）情況，需要轉變為（2），再轉換為（3），這個時候需要與剛才相反的操作——右旋

與左旋完全相反的操作

func (b *RedBlackTree) rotateRight(h *node) *node {	x := h.left	h.left = x.right	x.right = h	x.color = h.color	h.color = RED	x.n = h.n	h.n = b.size(h.left) + b.size(h.right) + 1	return x}

++注意：左旋和右旋都是對子節點的判斷++

總結一下插入操作只需要在插入節點後遞歸向上處理是否違反規則情況，在規則1處理後有可能會違反規則2，所以順序處理：

如果左邊不是為紅連結，右節點為紅————>左旋如果左節點為紅，左節點的左節點為紅————>右旋轉如果左右都為紅節點————> 變成黑色

程式碼：

//判斷節點顏色func isRed(x *node) bool {	if x == nil {		return false	}	return x.color == RED}//變換反色func reverseColor(x *node) {	x.color = !x.color}//如果跟節點為紅，子節點為黑或者跟節點為黑子節點為紅就取反色func flipColor(x *node) {	rootRed := isRed(x) && !isRed(x.left) && !isRed(x.right)	rootBlack := !isRed(x) && isRed(x.left) && isRed(x.right)	if rootRed || rootBlack {		reverseColor(x)		reverseColor(x.left)		reverseColor(x.right)	}}//插入方法的平衡樹方法，基於上面敘述翻譯func (b *RedBlackTree) balance(x *node) *node {	if isRed(x.right) && !isRed(x.left) {		x = b.rotateLeft(x)	}	if isRed(x.left) && isRed(x.left.left) {		x = b.rotateRight(x)	}	if isRed(x.left) && isRed(x.right) {		flipColor(x)	}	return x}

插入方法

//跟節點永遠都是黑色，key用int表示方便一點func (b *RedBlackTree) Put(key int, val interface{}) {	b.root = b.put(b.root, key, val)	b.root.color = BLACK}func (b *BlackReadTree) put(x *node, key int, val interface{}) *node {	if x == nil {		return newRedNode(key, val)	}	compare := x.key - key	if compare > 0 {		x.left = b.put(x.left, key, val)	} else if compare < 0 {		x.right = b.put(x.right, key, val)	} else {		x.val = val	}	return b.balance(x)}

插入方法和普通二叉樹查詢樹一致的，只是最後需要平衡樹操作，所以需要遞迴自下而上平衡每個節點，這一個平衡操作不管是插入刪除都需要用到。

如果可以借到節點呢？

如果右邊有一個紅色的節點，可以經過兩次旋轉操作就借到了節點，也不會破壞樹的平衡性。

這種情況說明了一個問題，在刪除最小節點時候不能在找到了該節點的時候再做變換，而是從一開始就要準備刪除節點時候的變換。換句話來說：++借一個節點要趁早，不要等到找到了最小節點才去右邊借，而是一開始能借就借，借不到就變為4-節點++，節點怎麼變化只要符合二叉樹原理即可。這時候你會問，如果後面能借到節點，前面借的節點怎麼辦？

沒關係，用balance還回去就行了，一個借4-節點如果沒有被使用，只需要把連結都變為黑色就變回了4-節點，這一點和插入使用的balance方法是一樣的。

流程為：

判斷左子是不是2-節點（當前節點的left和left.left是不是黑色，空節點為黑色）如果是一個2-節點，就判斷能不能從右邊借一個節點（right.left是不是紅連結）如果能借到節點就進過兩次旋轉，如果借不到就變成一個4-節點，等待下面刪除不斷遞迴呼叫balance方法平衡樹

其中需要注意的一點就是，為了保證平衡操作能夠正常執行，不管有沒有++借++到節點，都將他們變為4-節點（左右子節點都是紅連結），這樣可以保證balance操作的時候能夠正確平衡節點

那麼整個操作流程圖為：

從跟節點c開始，判斷是需要借一個節點的，先把節點變為4-節點，但是沒有借到，繼續向下走到了e節點，判斷是需要借一個節點，先把節點變為4-節點（需要將自己的連結變為黑色，不然就是5-節點）,發現借不到，繼續向下找到了a節點，發現a節點的連結已經是紅色了，直接刪除即可遞迴到b節點開始平衡，按照平衡規則右邊不能出現紅連結，左旋遞迴到e節點開始平衡，按照平衡規則右邊不能出現紅連結，左旋

++除此之外，刪除一個最小節點並沒有太多情況，因為如果一顆完美平衡的紅黑樹，在每一層往下走的時候，就只有能借到節點、借不到節點、不需要借的情況，仔細思考一下。從右子節點拿一個紅連結的節點對樹的平衡沒有什麼影響，能拿就拿，不能拿就降低樹的層數（變為3-節點），反正如果借用的節點沒有用到，balance會還回去，這就是刪除最小節點的思路++

程式碼

func (b *RedBlackTree) borrowLeft(x *node) *node {	//節點變換為4-節點 	flipColor(x)	//能借到節點就經過兩次旋轉	if !isRed(x.left) && isRed(x.right.left) {		x.right = b.rotateRight(x.right)		x = b.rotateLeft(x)	}	return b.balance(x)}func (b *BlackReadTree) DeleteMin() {	if !isRed(b.root.left) && !isRed(b.root.right) {		b.root.color = BLACK	}	b.root = b.deleteMin(b.root)	if !b.Empty() {		b.root.color = RED	}}//主要邏輯func (b *RedBlackTree) deleteMin(x *node) *node {	if x.left == nil {		return nil	}	//判斷是否需要借一個節點	if !isRed(x.left) && !isRed(x.left.left) {		x = b.borrowLeft(x)	}	x.left = b.deleteMin(x.left)	return b.balance(x)}func (b *RedBlackTree) Empty() bool {	return b.root == nil}

刪除最大值和刪除最小值類似，刪除最小值需要向右邊借用一個節點，而刪除最大值向左邊借節點，向左邊借節點只需要一次循轉，但是左邊有兩種情況

func (b *RedBlackTree) borrowRight(x *node) *node {	flipColor(x)	//如果左邊能借向左邊借	if isRed(x.left.left) {		x = b.rotateRight(x)	}	return b.balance(x)}func (b *RedBlackTree) DeleteMax() {	if !isRed(b.root.left) && !isRed(b.root.right) {		b.root.color = BLACK	}	b.root = b.deleteMax(b.root)	if !b.Empty() {		b.root.color = RED	}}func (b *RedBlackTree) deleteMax(x *node) *node {	//自己左邊是紅連結直接旋轉	if isRed(x.left) {		x = b.rotateRight(x)	}	if x.right == nil {		return nil	}	if !isRed(x.right) && !isRed(x.right.left) {		x = b.borrowRight(x)	}	x.right = b.deleteMax(x.right)	return b.balance(x)}

刪除最大和最小鍵可以得出一個思路，不斷的借用一個節點來保證當前節點不是2-節點，而是一個3-節點或者4-節點，這樣可以安全的刪除一個節點而不用擔心刪除一個2-節點導致樹平衡問題，然後自底向上平衡樹。

func (b *RedBlackTree) delete(x *node, key int) *node {	//借右節點	if key <x.key {		if !isRed(x.left) && !isRed(x.left.left) {			x = b.borrowLeft(x)		}		x.left = b.delete(x.left, key)	} else {		//借右邊第一種情況		if isRed(x.left) {			x = b.rotateRight(x)		}		//二叉查詢樹無右節點刪除情況		if key == x.key && x.right == nil {			return nil		}		//借右邊第二種情況		if !isRed(x.right) && !isRed(x.right.left) {			x = b.borrowRight(x)		}		//二叉查詢樹刪除方法		if key == x.key {			x.key = min(x.right).key			x.val = min(x.right).val			x.right = b.deleteMin(x.right)		//繼續遞迴		} else {			x.right = b.delete(x.right, key)		}	}	return b.balance(x)}

完整刪除方法

func (b *RedBlackTree) Delete(key int) {	if !isRed(b.root.left) && !isRed(b.root.right) {		b.root.color = BLACK	}	b.root = b.delete(b.root, key)	if !b.Empty() {		b.root.color = RED	}}func min(x *node) *node {	if x.left != nil {		return min(x.left)	}	return x}

最後貼一個JAVA程式碼

public class RedBlackTreeMap<Key extends Comparable<Key>, Value> {    private final boolean RED = true;    private final boolean BLACK = false;    private Node root;    private class Node {        Key key;        Value val;        Node left, right;        boolean color;        int n;        public Node(Key key, Value val, boolean color, int n) {            this.key = key;            this.val = val;            this.color = color;            this.n = n;        }    }    public void put(Key key, Value val) {        root = put(root, key, val);        root.color = BLACK;    }    private Node put(Node x, Key key, Value val) {        if (x == null) {            return new Node(key, val, RED, 1);        }        int cmp = key.compareTo(x.key);        if (cmp < 0) {            x.left = put(x.left, key, val);        } else if (cmp > 0) {            x.right = put(x.right, key, val);        } else {            x.val = val;        }        if (isRed(x.right) && !isRed(x.left)) {            x = rotateLeft(x);        }        if (isRed(x.left) && isRed(x.left.left)) {            x = rotateRight(x);        }        if (isRed(x.left) && isRed(x.right)) {            flipColor(x);        }        return x;    }    public Value get(Key key) {        return get(root, key);    }    private Value get(Node x, Key key) {        while (x != null) {            int cmp = key.compareTo(x.key);            if (cmp < 0) {                x = x.left;            } else if (cmp > 0) {                x = x.right;            } else {                return x.val;            }        }        return null;    }    public void deleteMin() {        if (isEmpty()) {            throw new RuntimeException();        }        if (!isRed(root.left) && !isRed(root.right)) {            root.color = RED;        }        root = deleteMin(root);        if (!isEmpty()) {            root.color = BLACK;        }    }    public void deleteMax() {        if (isEmpty()) {            throw new RuntimeException();        }        if (!isRed(root.left) && !isRed(root.right)) {            root.color = RED;        }        root = deleteMax(root);        if (!isEmpty()) {            root.color = BLACK;        }    }    public void delete(Key key) {        if (isEmpty()) {            throw new RuntimeException();        }        if (!isRed(root.left) && !isRed(root.right)) {            root.color = RED;        }        root = delete(root, key);        if (!isEmpty()) {            root.color = BLACK;        }    }    private Node delete(Node x, Key key) {        if (key.compareTo(x.key) < 0) {            if (!isRed(x.left) && !isRed(x.left.left)) {                x = moveLeft(x);            }            x.left = delete(x.left, key);        } else {            if (isRed(x.left)) {                x = rotateLeft(x);            }            if (key.compareTo(x.key) == 0 && x.right == null) {                return null;            }            if (!isRed(x.right) && !isRed(x.right.left)) {                x = moveRight(x);            }            if (key.compareTo(x.key) == 0) {                x.val = get(x.right, min(x.right).key);                x.key = min(x).key;                x.right = deleteMin(x.right);            } else {                x.right = delete(x.right, key);            }        }        return balance(x);    }    private Node deleteMin(Node x) {        if (x == null) {            return null;        }        if (!isRed(x.left) && !isRed(x.left.left)) {            x = moveLeft(x);        }        x.left = deleteMin(x.left);        return balance(x);    }    private Node deleteMax(Node x) {        if (x == null) {            return null;        }        if (!isRed(x.right) && !isRed(x.right.left)) {            x = moveRight(x);        }        x.right = deleteMax(x.right);        return balance(x);    }    public int size() {        return size(root);    }    private int size(Node x) {        if (x == null) {            return 0;        }        return x.n;    }    public boolean isEmpty() {        return size() == 0;    }    private void flipColor(Node x) {        boolean rootRed = x.color == RED && x.left.color == BLACK && x.right.color == BLACK;        boolean rootBlack = x.color == BLACK && x.left.color == RED && x.right.color == RED;        if (rootBlack || rootRed) {            x.color = !x.color;            x.left.color = !x.left.color;            x.right.color = !x.right.color;        }    }    private Node rotateLeft(Node x) {        Node h = x.right;        x.right = h.left;        h.left = x;        h.color = x.color;        x.color = RED;        h.n = x.n;        x.n = size(h.left) + size(h.right) + 1;        return h;    }    private Node rotateRight(Node x) {        Node h = x.left;        x.left = h.right;        h.right = x;        h.color = x.color;        x.color = RED;        h.n = x.n;        x.n = size(h.left) + size(h.right) + 1;        return h;    }    private boolean isRed(Node x) {        if (x == null) {            return false;        }        return x.color == RED;    }    private Node moveLeft(Node x) {        flipColor(x);        if (isRed(x.right.left)) {            x.right = rotateRight(x.right);            x = rotateLeft(x);        }        return balance(x);    }    private Node moveRight(Node x) {        flipColor(x);        if (isRed(x.left.left)) {            x = rotateRight(x);        }        return balance(x);    }    private Node balance(Node h) {        if (isRed(h.right)) {            h = rotateLeft(h);        }        if (isRed(h.left) && isRed(h.left.left)) {            h = rotateRight(h);        }        if (isRed(h.left) && isRed(h.right)) {            flipColor(h);        }        h.n = size(h.left) + size(h.right) + 1;        return h;    }    private Node min(Node x) {        if (x.left == null) {            return x;        }        return min(x.left);    }    private Node max(Node x) {        if (x.right == null) {            return x;        }        return max(x.right);    }

作者：LZ連結：https://juejin.cn/post/6932371712138805262來源：掘金