數(shù)據(jù)結(jié)構(gòu)-紅黑樹(shù)（Red Black Tree）

? 紅黑樹(shù)也是一種自平衡的二叉搜索樹(shù)
以前也叫做平衡二叉B樹(shù)（Symmetric Binary B-tree）
? 紅黑樹(shù)必須滿足以下 5 條性質(zhì)

節(jié)點(diǎn)是 RED 或者 BLACK
根節(jié)點(diǎn)是 BLACK
葉子節(jié)點(diǎn)（外部節(jié)點(diǎn)，空節(jié)點(diǎn)）都是 BLACK
RED 節(jié)點(diǎn)的子節(jié)點(diǎn)都是 BLACK
RED 節(jié)點(diǎn)的 parent 都是 BLACK
從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有 2 個(gè)連續(xù)的 RED 節(jié)點(diǎn)
從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的 BLACK 節(jié)點(diǎn)

紅黑樹(shù)的等價(jià)變換

? 紅黑樹(shù) 和 4階B樹(shù)（2-3-4樹(shù)）具有等價(jià)性
? BLACK 節(jié)點(diǎn)與它的 RED子節(jié)點(diǎn)融合在一起料扰，形成1個(gè)B樹(shù)節(jié)點(diǎn)
? 紅黑樹(shù)的 BLACK 節(jié)點(diǎn)個(gè)數(shù) 與 4階B樹(shù)的節(jié)點(diǎn)總個(gè)數(shù) 相等
? 網(wǎng)上有些教程：用 2-3樹(shù) 與紅黑樹(shù) 進(jìn)行類比，這是極其不嚴(yán)謹(jǐn)?shù)模?code>2-3樹(shù) 并不能完美匹配紅黑樹(shù) 的所有情況

后面展示的紅黑樹(shù)省略了 NULL 節(jié)點(diǎn)

紅黑樹(shù) vs 2-3-4樹(shù)

思考：如果上圖最底層的 BLACK 節(jié)點(diǎn)是不存在的轮傍，在B樹(shù)中是什么樣的情形惠况？
整棵B樹(shù)只有1個(gè)節(jié)點(diǎn)琐谤，而且是超級(jí)節(jié)點(diǎn)

幾個(gè)英文單詞

? parent：父節(jié)點(diǎn)
? sibling：兄弟節(jié)點(diǎn)
? uncle：叔父節(jié)點(diǎn)（ parent 的兄弟節(jié)點(diǎn)）
? grand：祖父節(jié)點(diǎn)（ parent 的父節(jié)點(diǎn)）

添加結(jié)點(diǎn)

? 已知
B樹(shù)中进苍，新元素必定是添加到葉子節(jié)點(diǎn)中
4階B樹(shù)所有節(jié)點(diǎn)的元素個(gè)數(shù) x 都符合 1 ≤ x ≤ 3

? 建議新添加的節(jié)點(diǎn)默認(rèn)為 RED贯城，這樣能夠讓紅黑樹(shù)的性質(zhì)盡快滿足（性質(zhì) 1熊楼、2、3冤狡、5 都滿足孙蒙，性質(zhì) 4 不一定）
? 如果添加的是根節(jié)點(diǎn)，染成 BLACK 即可

添加的所有情況

1. 有 4 種情況滿足紅黑樹(shù)的性質(zhì) 4 ：`parent` 為 BLACK

同樣也滿足 4階B樹(shù) 的性質(zhì),因此不用做任何額外處理

2. 有 8 種情況不滿足紅黑樹(shù)的性質(zhì) 4 ：`parent` 為 `RED`（ Double Red ）

其中前 4 種屬于B樹(shù)節(jié)點(diǎn)上溢的情況

2.1 添加 – 修復(fù)性質(zhì)4 – LL\RR

? 判定條件：uncle 不是 RED

parent 染成 BLACK悲雳，grand 染成 RED
grand 進(jìn)行單旋操作
LL：右旋轉(zhuǎn)
RR：左旋轉(zhuǎn)

2.2 添加 – 修復(fù)性質(zhì)4 – LR\RL

? 判定條件：uncle 不是 RED

自己染成 BLACK挎峦，grand 染成RED
進(jìn)行雙旋操作
LR：parent 左旋轉(zhuǎn)， grand 右旋轉(zhuǎn)
RL：parent 右旋轉(zhuǎn)合瓢， grand 左旋轉(zhuǎn)

2.3 添加 – 修復(fù)性質(zhì)4 – 上溢 – LL

? 判定條件：uncle 是 RED

parent坦胶、uncle 染成 BLACK
grand向上合并
染成 RED，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

? grand 向上合并時(shí)晴楔，可能繼續(xù)發(fā)生上溢
若上溢持續(xù)到根節(jié)點(diǎn)顿苇，只需將根節(jié)點(diǎn)染成 BLACK

2.4 添加 – 修復(fù)性質(zhì)4 – 上溢 – RR

? 判定條件：uncle 是 RED

parent、uncle 染成 BLACK
grand向上合并
染成 RED税弃，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

2.5 添加 – 修復(fù)性質(zhì)4 – 上溢 – LR

? 判定條件：uncle 是 RED

parent纪岁、uncle 染成 BLACK
grand向上合并
染成 RED，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

2.6 添加 – 修復(fù)性質(zhì)4 – 上溢 – RL

? 判定條件：uncle 是 RED

parent则果、uncle 染成 BLACK
grand向上合并
染成 RED幔翰，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

代碼實(shí)現(xiàn)

普通二叉樹(shù)代碼

package com.njf;

import java.util.LinkedList;
import java.util.Queue;

import com.njf.BinaryTree.Node;

import njf.printer.BinaryTreeInfo;

@SuppressWarnings("unchecked")
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }
    
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }
    
    private void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        
        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }
    
    public void inorder(Visitor<E> visitor) {
        if (visitor == null) return;
        inorder(root, visitor);
    }
    
    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        
        inorder(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorder(node.right, visitor);
    }
    
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root, visitor);
    }
    
    private void postorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        
        postorder(node.left, visitor);
        postorder(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }
    
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            } else { // 后面遍歷的節(jié)點(diǎn)都必須是葉子節(jié)點(diǎn)
                leaf = true;
            }
        }
        
        return true;
    }
    
    public int height() {
        if (root == null) return 0;
        
        // 樹(shù)的高度
        int height = 0;
        // 存儲(chǔ)著每一層的元素?cái)?shù)量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) { // 意味著即將要訪問(wèn)下一層
                levelSize = queue.size();
                height++;
            }
        }
        
        return height;
    }
    
    public int height2() {
        return height(root);
    }
    
    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
    
    protected Node<E> creatNode(E element, Node<E> parent) {
        return new Node<>(element, parent);
    }

    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        
        // 前驅(qū)節(jié)點(diǎn)在左子樹(shù)當(dāng)中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        
        // 從父節(jié)點(diǎn)、祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }
    
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;
        
        // 前驅(qū)節(jié)點(diǎn)在左子樹(shù)當(dāng)中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        
        // 從父節(jié)點(diǎn)西壮、祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @return 如果返回true闷盔，就代表停止遍歷
         */
        abstract boolean visit(E element);
    }
    
    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
        public boolean isLeaf() {
            return left == null && right == null;
        }
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
        public boolean isLeftChild() {
            return parent != null && this == parent.left; 
        }
        public boolean isRightChild() {
            return parent != null && this == parent.right; 
        }
        public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }
    
    /*****************************二叉樹(shù)的打印***************/
    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }
}

相較于AVL樹(shù)增加了獲取兄弟結(jié)點(diǎn)的接口

public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }

二叉搜索樹(shù)代碼

package com.njf;

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator;
    
    public BST() {
        this(null);
    }
    
    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public void add(E element) {
        elementNotNullCheck(element);
        // 添加第一個(gè)節(jié)點(diǎn)
        if (root == null) {
            root = creatNode(element, null);
            size++;
            // 新添加節(jié)點(diǎn)之后的處理
            afterAdd(root);
            return;
        }
        
        // 添加的不是第一個(gè)節(jié)點(diǎn)
        // 找到父節(jié)點(diǎn)
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等
                node.element = element;
                return;
            }
        } while (node != null);

        // 看看插入到父節(jié)點(diǎn)的哪個(gè)位置
        Node<E> newNode = creatNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        // 新添加節(jié)點(diǎn)之后的處理
        afterAdd(newNode);
    }
    
    /**
     * 添加node之后的調(diào)整
     * @param node 新添加的節(jié)點(diǎn)
     */
    protected void afterAdd(Node<E> node) {}
    
    /**
     * remove node之后的調(diào)整
     * @param node 移除節(jié)點(diǎn)
     */
    protected void afterRemove(Node<E> node,Node<E> replacement) {}

    public void remove(E element) {
        remove(node(element));
    }

    public boolean contains(E element) {
        return node(element) != null;
    }
    
    private void remove(Node<E> node) {
        if (node == null) return;
        size--;
        if (node.hasTwoChildren()) { // 度為2的節(jié)點(diǎn)
            // 找到后繼節(jié)點(diǎn)
            Node<E> s = successor(node);
            // 用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
            node.element = s.element;
            // 刪除后繼節(jié)點(diǎn)
            node = s;
        }
        
        // 刪除node節(jié)點(diǎn)（node的度必然是1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        
        if (replacement != null) { // node是度為1的節(jié)點(diǎn)
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left夺鲜、right的指向
            if (node.parent == null) { // node是度為1的節(jié)點(diǎn)并且是根節(jié)點(diǎn)
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
            afterRemove(node,replacement);
        } else if (node.parent == null) { // node是葉子節(jié)點(diǎn)并且是根節(jié)點(diǎn)
            root = null;
            afterRemove(node,null);
        } else { // node是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
            afterRemove(node,null);
        }
    }
    
    private Node<E> node(E element) {
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(element, node.element);
            if (cmp == 0) return node;
            if (cmp > 0) {
                node = node.right;
            } else { // cmp < 0
                node = node.left;
            }
        }
        return null;
    }
    
    /**
     * @return 返回值等于0，代表e1和e2相等沐扳；返回值大于0，代表e1大于e2觅赊；返回值小于于0龙助，代表e1小于e2
     */
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>)e1).compareTo(e2);
    }
    
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
}

RBTree

package com.njf;

import java.util.Comparator;

import com.njf.BinaryTree.Node;

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);
    }
    
    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        // 添加的是根節(jié)點(diǎn) 或者 上溢到達(dá)了根節(jié)點(diǎn)
        if (parent == null) {
            black(node);
            return;
        }
        // 如果父節(jié)點(diǎn)是黑色，直接返回
        if (isBlack(parent)) return;
        // 祖父節(jié)點(diǎn)
        Node<E> grand = parent.parent;
        // 叔父節(jié)點(diǎn)
        Node<E> uncle = parent.sibling();
        if (isRed(uncle)) {// 叔父節(jié)點(diǎn)是紅色【B樹(shù)節(jié)點(diǎn)上溢】
            black(parent);
            black(uncle);
            // 把祖父節(jié)點(diǎn)當(dāng)做是新添加的節(jié)點(diǎn)
            afterAdd(red(grand));
            return;
        }
        // 叔父節(jié)點(diǎn)不是紅色
        if (parent.isLeftChild()) {//L
            if (node.isLeftChild()) {//LL
                black(parent);
                red(grand);
                rotateRight(grand);
            }else {//LR
                black(node);
                red(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else {//R
            if (node.isLeftChild()) {//RL
                black(node);
                red(grand);
                rotateRight(parent);
                rotateLeft(grand);
            }else {//RR
                black(parent);
                red(grand);
                rotateLeft(grand);
            }
        }
    }
    
    @Override
    protected Node<E> creatNode(E element, Node<E> parent) {
        return new RBNode<E>(element, parent);
    }
    
    /**
     * 左旋轉(zhuǎn)
     * @param grand 高度最低的那個(gè)不平衡節(jié)點(diǎn)
     */
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        //讓parent成為這棵子樹(shù)的根節(jié)點(diǎn)
        afterRotate(grand, parent, child);
    }
    
    /**
     * 右旋轉(zhuǎn)
     * @param grand 高度最低的那個(gè)不平衡節(jié)點(diǎn)
     */
    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = parent.right;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }
    
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        //讓parent成為這棵子樹(shù)的根節(jié)點(diǎn)
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        }else if (grand.isRightChild()) {
            grand.parent.right = parent;
        }else {
            root = parent;
        }
        //更新child的parent
        if (child != null) {
            child.parent = grand;
        }
        //更新grand的parent
        grand.parent = parent;
        //更新結(jié)點(diǎn)的高度
    }
    
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return null;
        ((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 isRed(Node<E> node) {
        return colorOf(node) == RED;
    }
    
    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }
    
    public static class RBNode<E> extends Node<E> {
        public boolean color;
        
        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();
        }
    }
}

代碼調(diào)用

package com.njf;

import njf.printer.BinaryTrees;

public class Main {
    
    static void test1() {
        Integer data[] = new Integer[] {
                67, 52, 92, 96, 53, 95, 13, 63, 34, 82, 76, 54, 9, 68, 39
        };
        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) {
        // TODO Auto-generated method stub
        test1();
    }
}

結(jié)果如下:

           ┌─────────67─────────┐
           │                    │
    ┌─────52────┐             ┌─95─┐
    │           │             │    │
┌─R_13─┐      ┌─54─┐      ┌─R_82─┐ 96
│      │      │    │      │      │
9      34─┐ R_53  R_63 ┌─76      92
          │            │
         R_39        R_68

刪除結(jié)點(diǎn)（情況較復(fù)雜）

? B樹(shù)中渠牲，最后真正被刪除的元素都在葉子節(jié)點(diǎn)中

1. 刪除 – RED節(jié)點(diǎn)

? 直接刪除旋炒，不用作任何調(diào)整

2. 刪除 – BLACK節(jié)點(diǎn)

? 有 3 種情況
1. 擁有 2 個(gè) RED 子節(jié)點(diǎn)的 BLACK 節(jié)點(diǎn)
不可能被直接刪除，因?yàn)闀?huì)找它的子節(jié)點(diǎn)替代刪除
因此不用考慮這種情況
2. 擁有 1 個(gè) RED 子節(jié)點(diǎn)的 BLACK 節(jié)點(diǎn)
3. BLACK 葉子節(jié)點(diǎn)

2.1 刪除 – 擁有1個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)

? 判定條件：用以替代的子節(jié)點(diǎn)是 RED
? 將替代的子節(jié)點(diǎn)染成 BLACK 即可保持紅黑樹(shù)性質(zhì)

2.2 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為BLACK

?BLACK葉子節(jié)點(diǎn)被刪除后签杈，會(huì)導(dǎo)致B樹(shù)節(jié)點(diǎn)下溢（比如刪除88）
? 如果 sibling 至少有 1 個(gè) RED 子節(jié)點(diǎn)
進(jìn)行旋轉(zhuǎn)操作
旋轉(zhuǎn)之后的中心節(jié)點(diǎn)繼承 parent 的顏色
旋轉(zhuǎn)之后的左右節(jié)點(diǎn)染為 BLACK

2.3 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為BLACK

? 判定條件：sibling沒(méi)有 1 個(gè) RED 子節(jié)點(diǎn)
? 將 sibling 染成 RED瘫镇、parent 染成 BLACK 即可修復(fù)紅黑樹(shù)性質(zhì)

如果 parent 是 BLACK
會(huì)導(dǎo)致 parent 也下溢
這時(shí)只需要把 parent 當(dāng)做被刪除的節(jié)點(diǎn)處理即可

2.3 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為RED

? 如果 sibling 是 RED
sibling 染成 BLACK，parent 染成 RED答姥，進(jìn)行旋轉(zhuǎn)
于是又回到 sibling 是 BLACK 的情況

刪除結(jié)點(diǎn)代碼如下：

@Override
    protected void afterRemove(Node<E> node, Node<E> replacement) {
        // 如果刪除的節(jié)點(diǎn)是紅色
        if (isRed(node)) return;
        //用以取代刪除節(jié)點(diǎn)的子節(jié)點(diǎn)是紅色
        if (isRed(replacement)) {
            black(replacement);
            return;
        }
        Node<E> parent = node.parent;
        //刪除的是根結(jié)點(diǎn)
        if (parent == null) return;
        
        // 刪除的是黑色葉子節(jié)點(diǎn)【下溢】
        // 判斷被刪除的node是左還是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) {// 被刪除的節(jié)點(diǎn)在左邊铣除，兄弟節(jié)點(diǎn)在右邊
            if (isRed(sibling)) {//兄弟結(jié)點(diǎn)為紅色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 更換兄弟
                sibling = parent.right;
            }
            // 兄弟節(jié)點(diǎn)必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟節(jié)點(diǎn)沒(méi)有1個(gè)紅色子節(jié)點(diǎn)，父節(jié)點(diǎn)要向下跟兄弟節(jié)點(diǎn)合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if (parentBlack) {
                    afterRemove(parent, null);
                }
            }else {// 兄弟節(jié)點(diǎn)至少有1個(gè)紅色子節(jié)點(diǎn)鹦付，向兄弟節(jié)點(diǎn)借元素
                if (isBlack(sibling.right)) {
                    // 兄弟節(jié)點(diǎn)的左邊是黑色尚粘，兄弟要先旋轉(zhuǎn)
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling, colorOf(parent));
                black(parent);
                black(sibling.right);
                rotateLeft(parent);
            }
        }else {// 被刪除的節(jié)點(diǎn)在右邊，兄弟節(jié)點(diǎn)在左邊
            if (isRed(sibling)) {//兄弟結(jié)點(diǎn)為紅色
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 更換兄弟
                sibling = parent.left;
            }
            // 兄弟節(jié)點(diǎn)必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟節(jié)點(diǎn)沒(méi)有1個(gè)紅色子節(jié)點(diǎn)敲长，父節(jié)點(diǎn)要向下跟兄弟節(jié)點(diǎn)合并
                boolean isParentBlack = colorOf(parent);
                red(sibling);
                black(parent);
                if (isParentBlack) {
                    afterRemove(parent, null);
                }
            }else {// 兄弟節(jié)點(diǎn)至少有1個(gè)紅色子節(jié)點(diǎn)郎嫁，向兄弟節(jié)點(diǎn)借元素
                // 兄弟節(jié)點(diǎn)的左邊是黑色秉继，兄弟要先旋轉(zhuǎn)
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling, colorOf(parent));
                black(parent);
                black(sibling);
                rotateRight(parent);
            }
        }
    }

代碼調(diào)用

package com.njf;

import njf.printer.BinaryTrees;

public class Main {
    static void test4() {
        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);

        for (int i = 0; i < data.length; i++) {
            rb.remove(data[I]);
            System.out.println("---------------------------------------");
            System.out.println("【" + data[i] + "】");
            BinaryTrees.println(rb);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        test4();
    }
}

刪除結(jié)果打印如下：

    ┌────70───┐
        │         │
     ┌─56─┐     ┌─87─┐
     │    │     │    │
 ┌─R_22─┐ 62─┐ 74  ┌─96
 │      │    │     │
20    ┌─55  R_68 R_90
      │
    R_50
---------------------------------------
【55】
        ┌────70───┐
        │         │
     ┌─56─┐     ┌─87─┐
     │    │     │    │
 ┌─R_22─┐ 62─┐ 74  ┌─96
 │      │    │     │
20      50  R_68 R_90
---------------------------------------
【87】
        ┌────70───┐
        │         │
     ┌─56─┐     ┌─90─┐
     │    │     │    │
 ┌─R_22─┐ 62─┐ 74    96
 │      │    │
20      50  R_68
---------------------------------------
【56】
        ┌───70──┐
        │       │
     ┌─62─┐   ┌─90─┐
     │    │   │    │
 ┌─R_22─┐ 68 74    96
 │      │
20      50
---------------------------------------
【74】
     ┌───62───┐
     │        │
 ┌─R_22─┐   ┌─70─┐
 │      │   │    │
20      50 68    90─┐
                    │
                   R_96
---------------------------------------
【96】
     ┌───62───┐
     │        │
 ┌─R_22─┐   ┌─70─┐
 │      │   │    │
20      50 68    90
---------------------------------------
【22】
     ┌─62─┐
     │    │
  ┌─50  ┌─70─┐
  │     │    │
R_20   68    90
---------------------------------------
【62】
  ┌─50─┐
  │    │
R_20   68─┐
          │
          70─┐
             │
            R_90
---------------------------------------
【20】
50─┐
   │
   68─┐
      │
      70─┐
         │
        R_90
---------------------------------------
【70】
50─┐
   │
   68─┐
      │
      90
---------------------------------------
【68】
50─┐
   │
  R_90
---------------------------------------
【90】
50

紅黑樹(shù)的平衡

? 最初遺留的困惑：為何那5條性質(zhì)，就能保證紅黑樹(shù)是平衡的泽铛？
那5條性質(zhì)尚辑，可以保證紅黑樹(shù) 等價(jià)于 4階B樹(shù)

? 相比AVL樹(shù)，紅黑樹(shù)的平衡標(biāo)準(zhǔn)比較寬松：沒(méi)有一條路徑會(huì)大于其他路徑的2倍
? 是一種弱平衡盔腔、黑高度平衡
? 紅黑樹(shù)的最大高度是 2 * log(n + 1) 杠茬，依然是 O(logn) 級(jí)別

AVL樹(shù) vs 紅黑樹(shù)

? AVL樹(shù)

平衡標(biāo)準(zhǔn)比較嚴(yán)格：每個(gè)左右子樹(shù)的高度差不超過(guò)1
最大高度是 1.44 ? log( n +2) ? 1.328（100W個(gè)節(jié)點(diǎn)，AVL樹(shù)最大樹(shù)高28）
搜索弛随、添加瓢喉、刪除都是 O(logn) 復(fù)雜度，其中添加僅需 O(1) 次旋轉(zhuǎn)調(diào)整舀透、刪除最多需要 O(logn) 次旋轉(zhuǎn)調(diào)整

? 紅黑樹(shù)

平衡標(biāo)準(zhǔn)比較寬松：沒(méi)有一條路徑會(huì)大于其他路徑的2倍
最大高度是2 ? log(n + 1)（ 100W個(gè)節(jié)點(diǎn)栓票，紅黑樹(shù)最大樹(shù)高40）
搜索、添加盐杂、刪除都是 O(logn) 復(fù)雜度逗载，其中添加、刪除都僅需 O(1) 次旋轉(zhuǎn)調(diào)整

? 搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除链烈，選擇AVL樹(shù)厉斟；搜索、插入强衡、刪除次數(shù)幾乎差不多擦秽，選擇紅黑樹(shù)
? 相對(duì)于AVL樹(shù)來(lái)說(shuō)，紅黑樹(shù)犧牲了部分平衡性以換取插入/刪除操作時(shí)少量的旋轉(zhuǎn)操作漩勤，整體來(lái)說(shuō)性能要優(yōu)于AVL樹(shù)
? 紅黑樹(shù)的平均統(tǒng)計(jì)性能優(yōu)于AVL樹(shù)感挥，實(shí)際應(yīng)用中更多選擇使用紅黑樹(shù)

BST vs AVL Tree vs Re d Black Tree

例如：
10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 6 , 41, 37, 24, 96

BST

AVL

最后編輯于：2020.06.13 17:18:24

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市越败，隨后出現(xiàn)的幾起案子触幼，更是在濱河造成了極大的恐慌，老刑警劉巖究飞，帶你破解...
沈念sama閱讀 212,383評(píng)論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件置谦，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡亿傅，警方通過(guò)查閱死者的電腦和手機(jī)媒峡，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,522評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)葵擎，“玉大人谅阿，你說(shuō)我怎么就攤上這事。” “怎么了签餐？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,852評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵寓涨，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我氯檐，道長(zhǎng)缅茉，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,621評(píng)論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任男摧，我火速辦了婚禮，結(jié)果婚禮上译打，老公的妹妹穿的比我還像新娘耗拓。我一直安慰自己，他們只是感情好奏司，可當(dāng)我...
茶點(diǎn)故事閱讀 65,741評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布乔询。她就那樣靜靜地躺著，像睡著了一般韵洋。火紅的嫁衣襯著肌膚如雪竿刁。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 49,929評(píng)論 1贊 290
城市分裂傳說(shuō)
那天搪缨，我揣著相機(jī)與錄音食拜，去河邊找鬼。笑死副编，一個(gè)胖子當(dāng)著我的面吹牛负甸，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播痹届，決...
沈念sama閱讀 39,076評(píng)論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼呻待，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了队腐？” 一聲冷哼從身側(cè)響起蚕捉，我...
開(kāi)封第一講書(shū)人閱讀 37,803評(píng)論 0贊 268
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎柴淘，沒(méi)想到半個(gè)月后迫淹，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,265評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡悠就，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,582評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年千绪，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片梗脾。...
茶點(diǎn)故事閱讀 38,716評(píng)論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡荸型，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情瑞妇，我是刑警寧澤稿静，帶...
沈念sama閱讀 34,395評(píng)論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站辕狰，受9級(jí)特大地震影響改备，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜蔓倍，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,039評(píng)論 3贊 316
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一悬钳、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧偶翅，春花似錦默勾、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,798評(píng)論 0贊 21
一樁弒父案母剥，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至形导，卻和暖如春环疼，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背朵耕。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,027評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工炫隶，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人阎曹。一個(gè)月前我還...
沈念sama閱讀 46,488評(píng)論 2贊 361
代替公主和親
正文我出身青樓等限，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親芬膝。傳聞我的和親對(duì)象是個(gè)殘疾皇子望门，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,612評(píng)論 2贊 350

數(shù)據(jù)結(jié)構(gòu)-紅黑樹(shù)（Red Black Tree）

紅黑樹(shù)的等價(jià)變換

紅黑樹(shù) vs 2-3-4樹(shù)

幾個(gè)英文單詞

添加結(jié)點(diǎn)

添加的所有情況

1. 有 4 種情況滿足紅黑樹(shù)的性質(zhì) 4 ：parent 為 BLACK

2. 有 8 種情況不滿足紅黑樹(shù)的性質(zhì) 4 ：parent 為 RED（ Double Red ）

2.1 添加 – 修復(fù)性質(zhì)4 – LL\RR

2.2 添加 – 修復(fù)性質(zhì)4 – LR\RL

2.3 添加 – 修復(fù)性質(zhì)4 – 上溢 – LL

2.4 添加 – 修復(fù)性質(zhì)4 – 上溢 – RR

2.5 添加 – 修復(fù)性質(zhì)4 – 上溢 – LR

2.6 添加 – 修復(fù)性質(zhì)4 – 上溢 – RL

代碼實(shí)現(xiàn)

刪除結(jié)點(diǎn)（情況較復(fù)雜）

1. 刪除 – RED節(jié)點(diǎn)

2. 刪除 – BLACK節(jié)點(diǎn)

2.1 刪除 – 擁有1個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)

2.2 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為BLACK

2.3 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為BLACK

2.3 刪除 – BLACK葉子節(jié)點(diǎn) – sibling為RED

刪除結(jié)點(diǎn)代碼如下：

代碼調(diào)用

紅黑樹(shù)的平衡

AVL樹(shù) vs 紅黑樹(shù)

BST vs AVL Tree vs Re d Black Tree

1. 有 4 種情況滿足紅黑樹(shù)的性質(zhì) 4 ：`parent` 為 BLACK

2. 有 8 種情況不滿足紅黑樹(shù)的性質(zhì) 4 ：`parent` 為 `RED`（ Double Red ）