树(5)红黑树

Published on with 0 views and 0 comments

红黑树的应用
Java 中，TreeMap、TreeSet 都使用红黑树作为底层数据结构
JDK 1.8 开始，HashMap 也引入了红黑树：当冲突的链表长度超过 8 时，自动转为红黑树
Linux 底层的 CFS 进程调度算法中，vruntime 使用红黑树进行存储。
多路复用技术的 Epoll，其核心结构是红黑树 + 双向链表。

满足一个树是红黑树条件：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点必须是黑色
  3. 红色节点不能连续
  4. 从任意节点出发，到其所有叶子节点的简单路径上都包含相同数目的黑色节点.（非常重要）
  5. 每个红色节点的两个子节点一定都是黑色（叶子节点包含 NULL）

一棵典型的红黑树，如图 1.1 所示
image20220407091117nzxz13q.png

插入
1.插入节点置为红色，当插入位置为根节点时，改成黑色即可，插入位置的父节点为黑色时，直接插入。
2.当插入位置的父节点为红色时，分两种情况讨论
  • 第一种情况父节点是左子树

对于这种情况又可以分为以下 3 中小的情况考虑

1.叔叔节点是黑色(null 节点也是黑色)，插入到左子树中
image20220407101237jywz3o7.png
插入 120220407102233otmrgsn.gif

2.叔叔节点是黑色(null 节点也是黑色)，插入到右子树中
image20220407103814jkexjzt.png
插入 220220407103936x9zsuwg.gif

3.叔叔节点是红色
image20220407104131bdcw7yc.png
插入 320220407104333xy4l8eq.gif

  • 第二种情况，父节点是右子树

这种情况也可以分为以下 3 中小的情况考虑

1。叔叔节点是黑色，插入到右子树中
image2022040710460018es9ts.png
插入 420220407104735f9vyqjn.gif

2.叔叔节点是黑色，插入到右子树中。
image20220407104836n8h7cpc.png
插入 520220407104917fcujolc.gif

3.叔叔节点是红色。
image20220407105014jgk99h3.png
插入 620220407105341pyoin5u.gif

只看这些图绝对看不懂红黑树，结合代码就要简单些了

插入节点的总体流程图

红黑树插入流程 20220407182506l1pb7za.png

个人感觉只把 node 的父节点是左子节点这一条线的三种情况背下来就行了，面试的时候就说剩下的差不多就行了吧。

删除

#友情提醒，相对于插入，删除操作则更加复杂#

在插入操作中，通过判断插入结点的叔叔结点的颜色来确定恰当的平衡操作。而删除操作中，是通过检查兄弟结点的颜色来决定恰当的平衡操作。

红黑树中插入一个结点最容易出现两个连续的红色结点，违背红黑树的性质 3（红黑树中不存在两个相邻的红色结点）。而删除操作，最容易造成子树黑高（Black Height）的变化（删除黑色结点可能导致根结点到叶结点黑色结点的数目减少，即黑高降低）

与插入操作相比，红黑树的删除操作相对复杂一点，但多点儿耐心，还是没有问题的。为了理解删除操作，我们先来看一个 双黑（Double Black） 的概念

当删除结点 v 是黑色结点，且其被其黑色子节点 a(null 节点也算黑色子节点)替换时，其黑色子结点 a 就被标记为 双黑
image202204080939304edxrij.png

删除到此为止，防止脑溢血

红黑树的 Java 代码实现
package com.example.practical_demo.RedBlackTree;

public enum Color {
    Black("黑色"), Red("红色");

    private String color;

    private Color(String color) {
        this.color = color;
    }

    @Override
    public String toString() {
        return color;
    }
}

package com.example.practical_demo.RedBlackTree;

public class Node {
    public int key;
    public Color color;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(Color color) {
        this.color = color;
    }

    public Node(int key) {
        this.key = key;
        this.color = Color.Red;
    }

    /**
     * 求在树中节点的高度
     *
     * @return
     */
    public int height() {
        return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
    }

    /**
     * 在以该节点为根节点的树中，求最小节点
     *
     * @return
     */
    public Node minimum() {
        Node pointer = this;
        while (pointer.left != RedBlackTree.NULL)
            pointer = pointer.left;
        return pointer;
    }

    @Override
    public String toString() {
        String position = "null";
        if (this.parent != RedBlackTree.NULL)
            position = this.parent.left == this ? "left" : "right";
        return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
    }
}

package com.example.practical_demo.RedBlackTree;

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

public class RedBlackTree {

    public final static Node NULL = new Node(Color.Black);

    public Node root;

    public RedBlackTree() {
        this.root = NULL;
    }

    /**
     * 左旋转
     *
     * @param node
     */
    public void leftRotate(Node node) {
        Node rightNode = node.right;

        node.right = rightNode.left;
        if (rightNode.left != RedBlackTree.NULL)
            rightNode.left.parent = node;

        rightNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL)
            this.root = rightNode;
        else if (node.parent.left == node)
            node.parent.left = rightNode;
        else
            node.parent.right = rightNode;

        rightNode.left = node;
        node.parent = rightNode;
    }

    /**
     * 右旋转
     *
     * @param node
     */
    public void rightRotate(Node node) {
        Node leftNode = node.left;

        node.left = leftNode.right;
        if (leftNode.right != RedBlackTree.NULL)
            leftNode.right.parent = node;

        leftNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL) {
            this.root = leftNode;
        } else if (node.parent.left == node) {
            node.parent.left = leftNode;
        } else {
            node.parent.right = leftNode;
        }

        leftNode.right = node;
        node.parent = leftNode;
    }

    public void insert(Node node) {
        //null节点
        Node parentPointer = RedBlackTree.NULL;
        //根节点
        Node pointer = this.root;
        //遍历寻找node的父节点
        while (pointer != RedBlackTree.NULL) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        //为node节点设置父节点
        node.parent = parentPointer;
        //看node节点是放在左子树还是右子树
        if (parentPointer == RedBlackTree.NULL) {
            this.root = node;
        } else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
        //新node节点的子节点是两个null节点，并且新node节点的颜色是红色
        node.left = RedBlackTree.NULL;
        node.right = RedBlackTree.NULL;
        node.color = Color.Red;
        //平衡修复红黑树
        this.insertFixUp(node);
    }

    /**
     * 平衡修复
     * @param node
     */
    private void insertFixUp(Node node) {
        // 当node不是根结点，且node的父节点颜色为红色
        while (node.parent.color == Color.Red) {
            // 先判断node的父节点是左子节点，还是右子节点，这不同的情况，解决方案也会不同
            if (node.parent == node.parent.parent.left) {
                Node uncleNode = node.parent.parent.right;
                if (uncleNode.color == Color.Red) { // 如果叔叔节点是红色，则父父一定是黑色
                    // 通过把父父节点变成红色，父节点和兄弟节点变成黑色，然后在判断父父节点的颜色是否合适
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.right) { // node是其父节点的右子节点，且叔叔节点是黑色
                    // 对node的父节点进行左旋转
                    node = node.parent;
                    this.leftRotate(node);
                } else { // node如果叔叔节点是黑色，node是其父节点的左子节点，父父节点是黑色
                    // 把父节点变成黑色，父父节点变成红色，对父父节点进行右旋转
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.rightRotate(node.parent.parent);
                }
            } else {
                Node uncleNode = node.parent.parent.left;
                if (uncleNode.color == Color.Red) {
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node = node.parent;
                    this.rightRotate(node);
                } else {
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.leftRotate(node.parent.parent);
                }
            }
        }
        // 如果之前树中没有节点，那么新加入的点就成了新结点，而新插入的结点都是红色的，所以需要修改。
        this.root.color = Color.Black;
    }

    /**
     * n2替代n1
     *
     * @param n1
     * @param n2
     */
    private void transplant(Node n1, Node n2) {

        if (n1.parent == RedBlackTree.NULL) { // 如果n1是根节点
            this.root = n2;
        } else if (n1.parent.left == n1) { // 如果n1是其父节点的左子节点
            n1.parent.left = n2;
        } else { // 如果n1是其父节点的右子节点
            n1.parent.right = n2;
        }
        n2.parent = n1.parent;
    }

    /**
     * 删除节点node
     *
     * @param node
     */
    public void delete(Node node) {
        Node pointer1 = node;
        // 用于记录被删除的颜色，如果是红色，可以不用管，但如果是黑色，可能会破坏红黑树的属性
        Color pointerOriginColor = pointer1.color;
        // 用于记录问题的出现点
        Node pointer2;
        if (node.left == RedBlackTree.NULL) {
            pointer2 = node.right;
            this.transplant(node, node.right);
        } else if (node.right == RedBlackTree.NULL) {
            pointer2 = node.left;
            this.transplant(node, node.left);
        } else {
            // 如要删除的字节有两个子节点，则找到其直接后继（右子树最小值），直接后继节点没有非空左子节点。
            pointer1 = node.right.minimum();
            // 记录直接后继的颜色和其右子节点
            pointerOriginColor = pointer1.color;
            pointer2 = pointer1.right;
            // 如果其直接后继是node的右子节点，不用进行处理
            if (pointer1.parent == node) {
                pointer2.parent = pointer1;
            } else {
                // 否则，先把直接后继从树中提取出来，用来替换node
                this.transplant(pointer1, pointer1.right);
                pointer1.right = node.right;
                pointer1.right.parent = pointer1;
            }
            // 用node的直接后继替换node，继承node的颜色
            this.transplant(node, pointer1);
            pointer1.left = node.left;
            pointer1.left.parent = pointer1;
            pointer1.color = node.color;
        }
        if (pointerOriginColor == Color.Black) {
            this.deleteFixUp(pointer2);
        }
    }

    /**
     * The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4
     *
     * @param node
     */
    private void deleteFixUp(Node node) {
        // 如果node不是根节点，且是黑色
        while (node != this.root && node.color == Color.Black) {
            // 如果node是其父节点的左子节点
            if (node == node.parent.left) {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.right;
                // 如果node兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    leftRotate(node.parent);
                    pointer1 = node.parent.right;
                }
                if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.right.color == Color.Black) {
                    pointer1.left.color = Color.Black;
                    pointer1.color = Color.Red;
                    rightRotate(pointer1);
                    pointer1 = node.parent.right;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.right.color = Color.Black;
                    leftRotate(node.parent);
                    node = this.root;
                }
            } else {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.left;
                // 如果他兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    rightRotate(node.parent);
                    pointer1 = node.parent.left;
                }
                if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.left.color == Color.Black) {
                    pointer1.right.color = Color.Black;
                    pointer1.color = Color.Red;
                    leftRotate(pointer1);
                    pointer1 = node.parent.left;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.left.color = Color.Black;
                    rightRotate(node.parent);
                    node = this.root;
                }
            }

        }
        node.color = Color.Black;
    }

    private void innerWalk(Node node) {
        if (node != NULL) {
            innerWalk(node.left);
            System.out.println(node);
            innerWalk(node.right);
        }
    }

    /**
     * 中序遍历
     */
    public void innerWalk() {
        this.innerWalk(this.root);
    }

    /**
     * 层次遍历
     */
    public void print() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.root);
        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp);
            if (temp.left != NULL)
                queue.add(temp.left);
            if (temp.right != NULL)
                queue.add(temp.right);
        }
    }

    // 查找
    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != NULL && pointer.key != key) {
            pointer = pointer.key < key ? pointer.right : pointer.left;
        }
        return pointer;
    }

}
package com.example.practical_demo.RedBlackTree;

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

public class RedBlackTree {

    public final static Node NULL = new Node(Color.Black);

    public Node root;

    public RedBlackTree() {
        this.root = NULL;
    }

    /**
     * 左旋转
     *
     * @param node
     */
    public void leftRotate(Node node) {
        Node rightNode = node.right;

        node.right = rightNode.left;
        if (rightNode.left != RedBlackTree.NULL)
            rightNode.left.parent = node;

        rightNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL)
            this.root = rightNode;
        else if (node.parent.left == node)
            node.parent.left = rightNode;
        else
            node.parent.right = rightNode;

        rightNode.left = node;
        node.parent = rightNode;
    }

    /**
     * 右旋转
     *
     * @param node
     */
    public void rightRotate(Node node) {
        Node leftNode = node.left;

        node.left = leftNode.right;
        if (leftNode.right != RedBlackTree.NULL)
            leftNode.right.parent = node;

        leftNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL) {
            this.root = leftNode;
        } else if (node.parent.left == node) {
            node.parent.left = leftNode;
        } else {
            node.parent.right = leftNode;
        }

        leftNode.right = node;
        node.parent = leftNode;
    }

    public void insert(Node node) {
        //null节点
        Node parentPointer = RedBlackTree.NULL;
        //根节点
        Node pointer = this.root;
        //遍历寻找node的父节点
        while (pointer != RedBlackTree.NULL) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        //为node节点设置父节点
        node.parent = parentPointer;
        //看node节点是放在左子树还是右子树
        if (parentPointer == RedBlackTree.NULL) {
            this.root = node;
        } else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
        //新node节点的子节点是两个null节点，并且新node节点的颜色是红色
        node.left = RedBlackTree.NULL;
        node.right = RedBlackTree.NULL;
        node.color = Color.Red;
        //平衡修复红黑树
        this.insertFixUp(node);
    }

    /**
     * 平衡修复
     * @param node
     */
    private void insertFixUp(Node node) {
        // 当node不是根结点，且node的父节点颜色为红色
        while (node.parent.color == Color.Red) {
            // 先判断node的父节点是左子节点，还是右子节点，这不同的情况，解决方案也会不同
            if (node.parent == node.parent.parent.left) {
                Node uncleNode = node.parent.parent.right;
                if (uncleNode.color == Color.Red) { // 如果叔叔节点是红色，则父父一定是黑色
                    // 通过把父父节点变成红色，父节点和兄弟节点变成黑色，然后在判断父父节点的颜色是否合适
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.right) { // node是其父节点的右子节点，且叔叔节点是黑色
                    // 对node的父节点进行左旋转
                    node = node.parent;
                    this.leftRotate(node);
                } else { // node如果叔叔节点是黑色，node是其父节点的左子节点，父父节点是黑色
                    // 把父节点变成黑色，父父节点变成红色，对父父节点进行右旋转
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.rightRotate(node.parent.parent);
                }
            } else {
                Node uncleNode = node.parent.parent.left;
                if (uncleNode.color == Color.Red) {
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node = node.parent;
                    this.rightRotate(node);
                } else {
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.leftRotate(node.parent.parent);
                }
            }
        }
        // 如果之前树中没有节点，那么新加入的点就成了新结点，而新插入的结点都是红色的，所以需要修改。
        this.root.color = Color.Black;
    }

    /**
     * n2替代n1
     *
     * @param n1
     * @param n2
     */
    private void transplant(Node n1, Node n2) {

        if (n1.parent == RedBlackTree.NULL) { // 如果n1是根节点
            this.root = n2;
        } else if (n1.parent.left == n1) { // 如果n1是其父节点的左子节点
            n1.parent.left = n2;
        } else { // 如果n1是其父节点的右子节点
            n1.parent.right = n2;
        }
        n2.parent = n1.parent;
    }

    /**
     * 删除节点node
     *
     * @param node
     */
    public void delete(Node node) {
        Node pointer1 = node;
        // 用于记录被删除的颜色，如果是红色，可以不用管，但如果是黑色，可能会破坏红黑树的属性
        Color pointerOriginColor = pointer1.color;
        // 用于记录问题的出现点
        Node pointer2;
        if (node.left == RedBlackTree.NULL) {
            pointer2 = node.right;
            this.transplant(node, node.right);
        } else if (node.right == RedBlackTree.NULL) {
            pointer2 = node.left;
            this.transplant(node, node.left);
        } else {
            // 如要删除的字节有两个子节点，则找到其直接后继（右子树最小值），直接后继节点没有非空左子节点。
            pointer1 = node.right.minimum();
            // 记录直接后继的颜色和其右子节点
            pointerOriginColor = pointer1.color;
            pointer2 = pointer1.right;
            // 如果其直接后继是node的右子节点，不用进行处理
            if (pointer1.parent == node) {
                pointer2.parent = pointer1;
            } else {
                // 否则，先把直接后继从树中提取出来，用来替换node
                this.transplant(pointer1, pointer1.right);
                pointer1.right = node.right;
                pointer1.right.parent = pointer1;
            }
            // 用node的直接后继替换node，继承node的颜色
            this.transplant(node, pointer1);
            pointer1.left = node.left;
            pointer1.left.parent = pointer1;
            pointer1.color = node.color;
        }
        if (pointerOriginColor == Color.Black) {
            this.deleteFixUp(pointer2);
        }
    }

    /**
     * The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4
     *
     * @param node
     */
    private void deleteFixUp(Node node) {
        // 如果node不是根节点，且是黑色
        while (node != this.root && node.color == Color.Black) {
            // 如果node是其父节点的左子节点
            if (node == node.parent.left) {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.right;
                // 如果node兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    leftRotate(node.parent);
                    pointer1 = node.parent.right;
                }
                if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.right.color == Color.Black) {
                    pointer1.left.color = Color.Black;
                    pointer1.color = Color.Red;
                    rightRotate(pointer1);
                    pointer1 = node.parent.right;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.right.color = Color.Black;
                    leftRotate(node.parent);
                    node = this.root;
                }
            } else {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.left;
                // 如果他兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    rightRotate(node.parent);
                    pointer1 = node.parent.left;
                }
                if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.left.color == Color.Black) {
                    pointer1.right.color = Color.Black;
                    pointer1.color = Color.Red;
                    leftRotate(pointer1);
                    pointer1 = node.parent.left;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.left.color = Color.Black;
                    rightRotate(node.parent);
                    node = this.root;
                }
            }

        }
        node.color = Color.Black;
    }

    private void innerWalk(Node node) {
        if (node != NULL) {
            innerWalk(node.left);
            System.out.println(node);
            innerWalk(node.right);
        }
    }

    /**
     * 中序遍历
     */
    public void innerWalk() {
        this.innerWalk(this.root);
    }

    /**
     * 层次遍历
     */
    public void print() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.root);
        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp);
            if (temp.left != NULL)
                queue.add(temp.left);
            if (temp.right != NULL)
                queue.add(temp.right);
        }
    }

    // 查找
    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != NULL && pointer.key != key) {
            pointer = pointer.key < key ? pointer.right : pointer.left;
        }
        return pointer;
    }

}

package com.example.practical_demo.RedBlackTree;

public class Test01 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
        RedBlackTree redBlackTree = new RedBlackTree();
        for (int i = 0; i < arr.length; i++) {
            redBlackTree.insert(new Node(arr[i]));
        }
        System.out.println("树的高度： " + redBlackTree.root.height());
        System.out.println("左子树的高度： " + redBlackTree.root.left.height());
        System.out.println("右子树的高度： " + redBlackTree.root.right.height());
        System.out.println("层次遍历");
        redBlackTree.print();
        // 要删除节点
        Node node = redBlackTree.search(4);
        redBlackTree.delete(node);
        System.out.println("树的高度： " + redBlackTree.root.height());
        System.out.println("左子树的高度： " + redBlackTree.root.left.height());
        System.out.println("右子树的高度： " + redBlackTree.root.right.height());
        System.out.println("层次遍历");
        redBlackTree.print();
    }
}
红黑树和 AVl 树的区别

首先红黑树是不符合 AVL 树的平衡条件的，即每个节点的左子树和右子树的高度最多差 1 的二叉查找树。但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而 AVL 是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高！！！

  1. 如果插入一个 node 引起了树的不平衡，AVL 和 RB-Tree 都是最多只需要 2 次旋转操作，即两者都是 O(1)；但是在删除 node 引起树的不平衡时，最坏情况下，AVL 需要维护从被删 node 到 root 这条路径上所有 node 的平衡性，因此需要旋转的量级 O(logN)，而 RB-Tree 最多只需 3 次旋转，只需要 O(1)的复杂度。
  2. 其次，AVL 的结构相较 RB-Tree 来说更为平衡，在插入和删除 node 更容易引起 Tree 的 unbalance，因此在大量数据需要插入或者删除时，AVL 需要 rebalance 的频率会更高。因此，RB-Tree 在需要大量插入和删除 node 的场景下，效率更高。自然，由于 AVL 高度平衡，因此 AVL 的 search 效率更高。
  3. map 的实现只是折衷了两者在 search、insert 以及 delete 下的效率。总体来说，RB-tree 的统计性能是高于 AVL 的。

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择 AVL，如果搜索，插入删除次数几乎差不多，应该选择 RB。

标题：树(5)红黑树
作者：cuijianzhe
地址：https://cjzshilong.cn/articles/2022/04/08/1649401112733.html

↑ ↓