老师，为什么我测试的BST和AVL树性能差异不大啊？

Question

测试结果：

total words is 125901
time1===========14.8127835
total words is 125901
time2===========0.0949778
total words is 125901
time3===========0.0821608

测试类：

package com.company;

import java.util.ArrayList;

public class Main {

    /*public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt",words)){
            System.out.println("total words is "+words.size());
        }

        Map<String,Integer> map = new LinkedListMap<>();
        for(String word : words){
            if(map.contains(word)){
                map.set(word,map.get(word)+1);
            }else{
                map.add(word,1);
            }
        }

        System.out.println("different words is "+map.getSize());
        System.out.println("pride size is"+map.get("pride"));
        System.out.println("prejudice size is"+map.get("prejudice"));


        // write your code here
    }*/

    /*public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt",words)){
            System.out.println("total words is "+words.size());
        }

        Map<String,Integer> map = new BSTMap<>();
        for(String word : words){
            if(map.contains(word)){
                map.set(word,map.get(word)+1);
            }else{
                map.add(word,1);
            }
        }

        System.out.println("different words is "+map.getSize());
        System.out.println("pride size is"+map.get("pride"));
        System.out.println("prejudice size is"+map.get("prejudice"));


        // write your code here
    }*/

    private static double testTime(String fileName,Map<String,Integer> map){
        long time1 = System.nanoTime();

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile(fileName,words)){
            System.out.println("total words is "+words.size());
        }

        for(String word : words){
            if(map.contains(word)){
                map.set(word,map.get(word)+1);
            }else{
                map.add(word,1);
            }
        }

        for(String word:words){
            map.contains(word);
        }
        /*System.out.println("different words is "+map.getSize());
        System.out.println("pride size is"+map.get("pride"));
        System.out.println("prejudice size is"+map.get("prejudice"));*/


        long time2 = System.nanoTime();
        return (time2 - time1) / 1000000000.0;
    }

    public static void main(String[] args) {
        Map<String,Integer> map1 = new LinkedListMap<>();
        double time1 = testTime("pride-and-prejudice.txt",map1);
        System.out.println("time1==========="+time1);

        BSTMap<String,Integer> map2 = new BSTMap<>();
        double time2 = testTime("pride-and-prejudice.txt",map2);
        System.out.println("time2==========="+time2);

        AVLMap<String,Integer> map3 = new AVLMap<>();
        double time3 = testTime("pride-and-prejudice.txt",map3);
        System.out.println("time3==========="+time3);
    }




}

AVLTree

package com.company;

import java.util.ArrayList;
import java.util.List;

public class AVLTree<K extends Comparable<K>,V> {


    //1     定义Node
    class Node{
        private K key;
        private V value;
        private Node left,right;
        private int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            this.height = 1;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("key=").append(key);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }

    //2     定义属性
    private int size;
    private Node root;

    /**
     * getHeight
     * @author weidoudou
     * @date 2023/4/1 11:34
     * @param node 请添加参数描述
     * @return int
     **/
    private int getHeight(Node node){
        if(null==node){
            return 0;
        }
        return node.height;
    }

    /**
     * getBalanceFactor
     * @author weidoudou
     * @date 2023/4/1 11:36
     * @param node 请添加参数描述
     * @return int
     **/
    private int getBalanceFactor(Node node){
        if(null==node){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 无参构造函数
     * @author weidoudou
     * @date 2023/1/1 11:09
     * @return null
     **/
    public AVLTree(){
        this.size = 0;
        this.root = null;
    }



    public boolean isEmpty() {
        return size==0?true:false;
    }

    public int getSize() {
        return size;
    }

    //3     定义包含函数
    private Node containsKey(K key,Node node){
        //结束条件
        if(null==node){
            return null;
        }

        //循环条件
        if(key.compareTo(node.key)<0){
            return containsKey(key,node.left);
        }else if(key.compareTo(node.key)>0){
            return containsKey(key, node.right);
        }else{//key.compareTo(node.key)=0 其实这个也是结束条件
            return node;
        }
    }

    public boolean contains(K key) {
        return containsKey(key,root)==null?false:true;
    }

    public V get(K key) {
        Node node = containsKey(key,root);
        if(null!=node){
            return node.value;
        }
        return null;
    }


    //3     递归，添加元素
    public Node add(K key,V value,Node node){
        //3.1   终止条件
        //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断，因为已经调了containsKey方法判断了
        if(node==null){
            size++;
            return new Node(key,value);
        }

        //3.1.2 最终插入左孩子
        if(key.compareTo(node.key)<0 ){
            node.left = add(key,value,node.left);
        }else if(key.compareTo(node.key)>0){
            node.right = add(key,value,node.right);
        }else{
            node.value = value;
        }

        node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
        int balanceFactor = getBalanceFactor(node);
        /*if(Math.abs(balanceFactor)>1){
            System.out.println("unbalanced:"+balanceFactor);
        }*/

        //左左情况
        if(balanceFactor>1&&getBalanceFactor(node.left)>=0){
            return rightRotate(node);
            //右右情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
            return leftRotate(node);
            //左右情况
        }else if(balanceFactor>1&&getBalanceFactor(node.left)<0){
            //先对左子节点左旋转，然后整体右旋转
            node.left = leftRotate(node.left);
            return rightRotate(node);
            //右左情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }



    // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    /**
     * 右旋转
     * 1    旋转
     * 2    变更高度
     * @author weidoudou
     * @date 2023/4/14 7:27
     * @param y 请添加参数描述
     * @return com.company.AVLTree<K,V>.Node
     **/
    private Node rightRotate(Node y){
        //1 右旋转
        Node x = y.left;
        Node T3 = x.right;
        x.right = y;
        y.left = T3;

        //2 变更高度
        y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
        x.height = Math.max(getHeight(x.left),getHeight(x.left))+1;
        return x;
    }


    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //    y                             x
    //  /  \                          /   \
    // T1   x      向左旋转 (y)       y     z
    //     / \   - - - - - - - ->   / \   / \
    //   T2  z                     T1 T2 T3 T4
    //      / \
    //     T3 T4
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        // 向左旋转过程
        x.left = y;
        y.right = T2;

        // 更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    public void add(K key, V value) {
        root = add(key,value,root);
        /*Node node = containsKey(key,root);
        //未找到，插值
        if(node==null){
            //2.1   考虑特殊情况,如果是第一次调用，root为null
            if(root==null){
                root = new Node(key,value);
                size++;
            }else{
                //2.2   添加递归方法
                add(key,value,root);
            }
        }else{
            node.value = value;
        }*/
        //找到后，更新值
    }

    public void set(K key, V value) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        node.value = value;
    }

    private Node remove(Node node, K key){
        //终止条件1 基本判断不到，因为已经判断了containskey
        if(node==null){
            return null;
        }

        Node retNode;
        //递归
        if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            retNode = node;
        }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            retNode = node;
        }else{
            //已找到要删除的元素
            //1 如果只有左子节点或只有右子节点，则直接将子节点替换
            if(node.left==null){
                retNode = node.right;
                size--;
            }else if(node.right==null){
                retNode = node.left;
                size--;
            }else{
                //2 如果有左子节点和右子节点，则寻找前驱或后继 对当前节点替换掉
                Node nodeMain = findMin(node.right);

                nodeMain.right = remove(node.right,nodeMain.key);//这块要么用removMin方法（添加维护平衡的代码），要么复用remove方法(删除以node右子树为根的二叉树的最小值)
                nodeMain.left = node.left;
                node.left = node.right = null;
                retNode = nodeMain;
                size--;
            }
        }

        if(retNode==null){
            return null;
        }

        retNode.height = 1+Math.max(getHeight(retNode.left),getHeight(retNode.right));
        int balanceFactor = getBalanceFactor(retNode);

        //左左情况
        if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){
            return rightRotate(retNode);
            //右右情况
        }else if(balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
            return leftRotate(retNode);
            //左右情况
        }else if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
            //先对左子节点左旋转，然后整体右旋转
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
            //右左情况
        }else if(balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;

    }

    private Node findMin(Node node){
        //1     终止条件
        if(node.left==null){
            return node;
        }

        //2     递归
        return findMin(node.left);
    }

    private Node removMin(Node node){
        //终止条件
        if(node.left==null){
            Node rightNode = node.right;
            node.right = null;
            return rightNode;
        }

        //递归
        node.left = removMin(node.left);
        return node;
    }

    /**
     * 删除任意元素 若删除元素节点下只有一个节点直接接上即可，若有两个节点，则找前驱或后继，本节找前驱
     * @author weidoudou
     * @date 2023/1/1 11:52
     * @param key 请添加参数描述
     * @return V
     **/
    public V remove(K key) {
        Node node = containsKey(key,root);
        if(node != null){
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    //1     校验二分搜索树(中序遍历参考之前的中序遍历一节)
    public boolean judgeBST(){
        List<K> list = new ArrayList<>();
        inOrder(root,list);
        for(int i=1;i<list.size();i++){
            if(list.get(i-1).compareTo(list.get(i))>0){
                return false;
            }
        }
        return true;
    }

    private void inOrder(Node node, List<K> list){
        if(node==null){
            return;
        }
        inOrder(node.left,list);
        list.add(node.key);
        inOrder(node.right,list);
    }


    //2     校验平衡二叉树
    public boolean judgeBalance(){
        return judgeBalance(root);
    }

    private boolean judgeBalance(Node node){
        if(node == null){
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor)>1){
            return false;
        }
        return judgeBalance(node.left)&&judgeBalance(node.right);
    }




    public static void main(String[] args) {
        System.out.println("Pride and Prejudice");
        ArrayList<String> words = new ArrayList<>();

        if(FileOperation.readFile("pride-and-prejudice.txt",words)){
            System.out.println("Total words: "+words.size());
            AVLTree<String,Integer> avlTree = new AVLTree<>();
            for(String word:words){
                if(avlTree.contains(word)){
                    avlTree.set(word,avlTree.get(word)+1);
                }else{
                    avlTree.add(word,1);
                }
            }
            System.out.println("Total different words:"+avlTree.getSize());
            System.out.println("judge BST:"+avlTree.judgeBST());
            System.out.println("judge Balance:"+avlTree.judgeBalance());


            for(String word:words){
                avlTree.remove(word);
                if(!avlTree.judgeBalance()||!avlTree.judgeBST()){
                    System.out.println("平衡二叉树删除元素后不满足二叉树或者平衡二叉树性质");
                }
            }
        }


    }


}

Answer 1

liuyubobobo 2023-04-20 08:09:41

AVL 的改进是在 BST 退化的情况下才能显现出来，对于通常数据，大体随机分布的情况，AVL 的性能和 BST 就是不大。

一个简单的让 BST 退化的方式是，把插入的元素排序，按顺序插入，再按顺序查找，再按顺序删除，应该能看到 BST 和 AVL 的显著性能差异。

继续加油！：）

• 提问者 小蜗牛有大理想 #1

  但是我用avl树实现的集合比BST实现的集合速度就快很多，我理解是不是map的put值相对耗时导致的

• 提问者 小蜗牛有大理想 #2

  老师，您参照我  ”avl实现的集合速度比BST实现的集合快了三倍（list不排序的情况）“  这个问题，同样是用avlTree实现的，为什么Set 运行速度就这么显著？

• liuyubobobo 回复 提问者 小蜗牛有大理想 #3

  三倍的性能差异其实不构成算法复杂度的差异（相较于 n 的规模是几十万上百万。）如果你追究这部分性能差异，那么这个基于 AVL 的 map 就还有优化的地方，最显著的可以优化的地方是在 set, remove 和 get 的时候，我们都先判断了一下 contain，再做具体的 set, remove 和 get。这使得这些操作寻找了两遍元素。这两边可以合一。（相较于 set，不需要这个 contain 的判断。）感兴趣可以自己优化一下这部分逻辑试试看？继续加油！：）