数据结构-红黑树（Red Black Tree）

作者: 鼬殿 | 来源:发表于2020-06-10 15:47 被阅读0次

◼ 红黑树也是一种自平衡的二叉搜索树
以前也叫做平衡二叉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 的父节点）

添加结点

◼ 已知
B树中，新元素必定是添加到叶子节点中
4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3

◼ 建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）
◼ 如果添加的是根节点，染成 BLACK 即可

添加的所有情况

1. 有 4 种情况满足红黑树的性质 4 ：`parent` 为 BLACK

同样也满足 4阶B树 的性质,因此不用做任何额外处理

2. 有 8 种情况不满足红黑树的性质 4 ：`parent` 为 `RED`（ Double Red ）

其中前 4 种属于B树节点上溢的情况

2.1 添加 – 修复性质4 – LL\RR

◼ 判定条件：uncle 不是 RED

parent 染成 BLACK，grand 染成 RED
grand 进行单旋操作
LL：右旋转
RR：左旋转

2.2 添加 – 修复性质4 – LR\RL

◼ 判定条件：uncle 不是 RED

自己染成 BLACK，grand 染成RED
进行双旋操作
LR：parent 左旋转， grand 右旋转
RL：parent 右旋转， grand 左旋转

2.3 添加 – 修复性质4 – 上溢 – LL

◼ 判定条件：uncle 是 RED

parent、uncle 染成 BLACK
grand向上合并
染成 RED，当做是新添加的节点进行处理

◼ grand 向上合并时，可能继续发生上溢
若上溢持续到根节点，只需将根节点染成 BLACK

2.4 添加 – 修复性质4 – 上溢 – RR

◼ 判定条件：uncle 是 RED

parent、uncle 染成 BLACK
grand向上合并
染成 RED，当做是新添加的节点进行处理

2.5 添加 – 修复性质4 – 上溢 – LR

◼ 判定条件：uncle 是 RED

parent、uncle 染成 BLACK
grand向上合并
染成 RED，当做是新添加的节点进行处理

2.6 添加 – 修复性质4 – 上溢 – RL

◼ 判定条件：uncle 是 RED

parent、uncle 染成 BLACK
grand向上合并
染成 RED，当做是新添加的节点进行处理

代码实现

普通二叉树代码

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 { // 后面遍历的节点都必须是叶子节点
                leaf = true;
            }
        }
        
        return true;
    }
    
    public int height() {
        if (root == null) return 0;
        
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        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) { // 意味着即将要访问下一层
                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;
        
        // 前驱节点在左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找前驱节点
        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;
        
        // 前驱节点在左子树当中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找前驱节点
        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;
        }
    }
    
    /*****************************二叉树的打印***************/
    @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树增加了获取兄弟结点的接口

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

二叉搜索树代码

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);
        // 添加第一个节点
        if (root == null) {
            root = creatNode(element, null);
            size++;
            // 新添加节点之后的处理
            afterAdd(root);
            return;
        }
        
        // 添加的不是第一个节点
        // 找到父节点
        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);

        // 看看插入到父节点的哪个位置
        Node<E> newNode = creatNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        // 新添加节点之后的处理
        afterAdd(newNode);
    }
    
    /**
     * 添加node之后的调整
     * @param node 新添加的节点
     */
    protected void afterAdd(Node<E> node) {}
    
    /**
     * remove node之后的调整
     * @param node 移除节点
     */
    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的节点
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点
            node = s;
        }
        
        // 删除node节点（node的度必然是1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        
        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                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是叶子节点并且是根节点
            root = null;
            afterRemove(node,null);
        } else { // node是叶子节点，但不是根节点
            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;
        // 添加的是根节点 或者 上溢到达了根节点
        if (parent == null) {
            black(node);
            return;
        }
        // 如果父节点是黑色，直接返回
        if (isBlack(parent)) return;
        // 祖父节点
        Node<E> grand = parent.parent;
        // 叔父节点
        Node<E> uncle = parent.sibling();
        if (isRed(uncle)) {// 叔父节点是红色【B树节点上溢】
            black(parent);
            black(uncle);
            // 把祖父节点当做是新添加的节点
            afterAdd(red(grand));
            return;
        }
        // 叔父节点不是红色
        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);
    }
    
    /**
     * 左旋转
     * @param grand 高度最低的那个不平衡节点
     */
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        //让parent成为这棵子树的根节点
        afterRotate(grand, parent, child);
    }
    
    /**
     * 右旋转
     * @param grand 高度最低的那个不平衡节点
     */
    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成为这棵子树的根节点
        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;
        //更新结点的高度
    }
    
    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();
        }
    }
}

代码调用

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();
    }
}

结果如下:

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

删除结点（情况较复杂）

◼ B树中，最后真正被删除的元素都在叶子节点中

1. 删除 – RED节点

◼ 直接删除，不用作任何调整

2. 删除 – BLACK节点

◼ 有 3 种情况
1. 拥有 2 个 RED 子节点的 BLACK 节点
不可能被直接删除，因为会找它的子节点替代删除
因此不用考虑这种情况
2. 拥有 1 个 RED 子节点的 BLACK 节点
3. BLACK 叶子节点

2.1 删除 – 拥有1个RED子节点的BLACK节点

◼ 判定条件：用以替代的子节点是 RED
◼ 将替代的子节点染成 BLACK 即可保持红黑树性质

2.2 删除 – BLACK叶子节点 – sibling为BLACK

◼BLACK叶子节点被删除后，会导致B树节点下溢（比如删除88）
◼ 如果 sibling 至少有 1 个 RED 子节点
进行旋转操作
旋转之后的中心节点继承 parent 的颜色
旋转之后的左右节点染为 BLACK

2.3 删除 – BLACK叶子节点 – sibling为BLACK

◼ 判定条件：sibling没有 1 个 RED 子节点
◼ 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

如果 parent 是 BLACK
会导致 parent 也下溢
这时只需要把 parent 当做被删除的节点处理即可

2.3 删除 – BLACK叶子节点 – sibling为RED

◼ 如果 sibling 是 RED
sibling 染成 BLACK，parent 染成 RED，进行旋转
于是又回到 sibling 是 BLACK 的情况

删除结点代码如下：

@Override
    protected void afterRemove(Node<E> node, Node<E> replacement) {
        // 如果删除的节点是红色
        if (isRed(node)) return;
        //用以取代删除节点的子节点是红色
        if (isRed(replacement)) {
            black(replacement);
            return;
        }
        Node<E> parent = node.parent;
        //删除的是根结点
        if (parent == null) return;
        
        // 删除的是黑色叶子节点【下溢】
        // 判断被删除的node是左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) {// 被删除的节点在左边，兄弟节点在右边
            if (isRed(sibling)) {//兄弟结点为红色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 更换兄弟
                sibling = parent.right;
            }
            // 兄弟节点必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if (parentBlack) {
                    afterRemove(parent, null);
                }
            }else {// 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                if (isBlack(sibling.right)) {
                    // 兄弟节点的左边是黑色，兄弟要先旋转
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling, colorOf(parent));
                black(parent);
                black(sibling.right);
                rotateLeft(parent);
            }
        }else {// 被删除的节点在右边，兄弟节点在左边
            if (isRed(sibling)) {//兄弟结点为红色
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 更换兄弟
                sibling = parent.left;
            }
            // 兄弟节点必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                boolean isParentBlack = colorOf(parent);
                red(sibling);
                black(parent);
                if (isParentBlack) {
                    afterRemove(parent, null);
                }
            }else {// 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                // 兄弟节点的左边是黑色，兄弟要先旋转
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling, colorOf(parent));
                black(parent);
                black(sibling);
                rotateRight(parent);
            }
        }
    }

代码调用

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();
    }
}

删除结果打印如下：

    ┌────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

红黑树的平衡

◼ 最初遗留的困惑：为何那5条性质，就能保证红黑树是平衡的？
那5条性质，可以保证红黑树等价于 4阶B树

◼ 相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍
◼ 是一种弱平衡、黑高度平衡
◼ 红黑树的最大高度是 2 * log(n + 1) ，依然是 O(logn) 级别

AVL树 vs 红黑树

◼ AVL树

平衡标准比较严格：每个左右子树的高度差不超过1
最大高度是 1.44 ∗ log( n +2) − 1.328（100W个节点，AVL树最大树高28）
搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整

◼ 红黑树

平衡标准比较宽松：没有一条路径会大于其他路径的2倍
最大高度是2 ∗ log(n + 1)（ 100W个节点，红黑树最大树高40）
搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整

◼ 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
◼ 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
◼ 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

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

数据结构-红黑树（Red Black Tree）

红黑树的等价变换

红黑树 vs 2-3-4树

几个英文单词

添加结点

添加的所有情况

1. 有 4 种情况满足红黑树的性质 4 ：`parent` 为 BLACK

2. 有 8 种情况不满足红黑树的性质 4 ：`parent` 为 `RED`（ Double Red ）

2.1 添加 – 修复性质4 – LL\RR

2.2 添加 – 修复性质4 – LR\RL

2.3 添加 – 修复性质4 – 上溢 – LL

2.4 添加 – 修复性质4 – 上溢 – RR

2.5 添加 – 修复性质4 – 上溢 – LR

2.6 添加 – 修复性质4 – 上溢 – RL

代码实现

删除结点（情况较复杂）

1. 删除 – RED节点

2. 删除 – BLACK节点

2.1 删除 – 拥有1个RED子节点的BLACK节点

2.2 删除 – BLACK叶子节点 – sibling为BLACK

2.3 删除 – BLACK叶子节点 – sibling为BLACK

2.3 删除 – BLACK叶子节点 – sibling为RED

删除结点代码如下：

代码调用

红黑树的平衡

AVL树 vs 红黑树

BST vs AVL Tree vs Re d Black Tree

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构-红黑树（Red Black Tree）

红黑树的等价变换

红黑树 vs 2-3-4树

几个英文单词

添加结点

添加的所有情况

1. 有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK

2. 有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ）

2.1 添加 – 修复性质4 – LL\RR

2.2 添加 – 修复性质4 – LR\RL

2.3 添加 – 修复性质4 – 上溢 – LL

2.4 添加 – 修复性质4 – 上溢 – RR

2.5 添加 – 修复性质4 – 上溢 – LR

2.6 添加 – 修复性质4 – 上溢 – RL

代码实现

删除结点（情况较复杂）

1. 删除 – RED节点

2. 删除 – BLACK节点

2.1 删除 – 拥有1个RED子节点的BLACK节点

2.2 删除 – BLACK叶子节点 – sibling为BLACK

2.3 删除 – BLACK叶子节点 – sibling为BLACK

2.3 删除 – BLACK叶子节点 – sibling为RED

删除结点代码如下：

代码调用

红黑树的平衡

AVL树 vs 红黑树

BST vs AVL Tree vs Re d Black Tree

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

1. 有 4 种情况满足红黑树的性质 4 ：`parent` 为 BLACK

2. 有 8 种情况不满足红黑树的性质 4 ：`parent` 为 `RED`（ Double Red ）