邯城往事

>>> 展颜笑夙愿,一笑泯恩仇 <<<

目录
树(5)红黑树
/  

树(5)红黑树

红黑树的应用
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。

评论
取消