java - AVL 树给我 O(c^n) 而不是 O(log n)

Question

我在 java 中创建了一个 AVLTree 并且 add 方法应该是 O(log n)... 但是我的 add 方法似乎给我一个 O(c^n) 的图或一个指数图而不是一个对数图。这是运行时间与输入大小的关系图:

谁能帮忙弄清楚为什么会这样？

这是我的 AVLTree 的代码:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import cw1.rs10.lib.IAVLTree;

public class AVLTree<K, V> implements IAVLTree<K, V>
{
    public class Node {
        private K key;
        private ArrayList<V> values;
        private Node left, right;
        private int height;

        public Node(K key, V value) {
            this.key = key;
            this.values = new ArrayList<V>();
            this.left = null;
            this.right = null;
            this.height = 0;

            values.add(value);
        }

        public K getKey() {
            return key;
        }
        public void setKey(K key) {
            this.key = key;
        }

        public ArrayList<V> getValues() {
            return values;
        }
        public void addValue(V value) {
            values.add(value);
        }

        public Node getLeft() {
            return left;
        }
        public Node getRight() {
            return right;
        }

        public void setLeft(Node left) {
            this.left = left;
        }
        public void setRight(Node right) {
            this.right = right;
        }

        public int getHeight() {
            return height;
        }
        public void setHeight(int height) {
            this.height = height;
        }
    }

    private Node rootNode;
    private Comparator<K> comparator;

    //Unused
    public AVLTree() {
    }

    public AVLTree(Comparator<K> comparator) {
        this.rootNode = null;
        this.comparator = comparator;
    }

    @Override
    public V add(K k, V v) {
        Node n = rootNode = add(k, v, rootNode);
        if(n != null)
            return v;
        else
            return null;
    }
    private Node add(K key, V value, Node node) {
        if(node == null)
            return new Node(key, value);

        if(comparator.compare(key, node.getKey()) < 0) {
            node.setLeft(add(key, value, node.getLeft()));

            if(height(node.getLeft()) - height(node.getRight()) == 2) {
                if(comparator.compare(key, node.getLeft().getKey()) < 0)
                    node = rotateLeft(node);
                else
                    node = doubleRotateLeft(node);
            }
        } else if(comparator.compare(key, node.getKey()) > 0) {
            node.setRight(add(key, value, node.getRight()));

            if(height(node.getRight()) - height(node.getLeft()) == 2) {
                if(comparator.compare(key, node.getRight().getKey()) > 0)
                    node = rotateRight(node);
                else
                    node = doubleRotateRight(node);
            }
        } else {
            //Handle duplicate
            node.getValues().add(value);
        }

        node.setHeight( Math.max(height(node.getLeft()), height(node.getRight())) + 1 );

        return node;
    }

    @Override
    public V remove(K key, V value) throws Exception {
        Node node = rootNode = remove(key, value, rootNode);
        if(node != null)
            return value;
        else
            return null;
    }
    private Node remove(K key, V value, Node node) {
        //If node with key contains one or less values, remove the whole key
        //Else remove value from node with key
        if(node == null) return null;
        else if(comparator.compare(key, node.getKey()) < 0) {
            node.setLeft(remove(key, value, node.getLeft()));

            if(height(node.getLeft()) - height(node.getRight()) == 2) {
                if(comparator.compare(key, node.getLeft().key) < 0)
                    node = rotateLeft(node);
                else
                    node = doubleRotateLeft(node);
            }
        } else if(comparator.compare(key, node.getKey()) > 0) {
            node.setRight(remove(key, value, node.getRight()));

            if(height(node.getRight()) - height(node.getLeft()) == 2) {
                if(comparator.compare(key, node.getRight().key) < 0)
                    node = rotateRight(node);
                else
                    node = doubleRotateRight(node);
            }
        } else {
            if(node.getValues().size() > 1) {
                node.getValues().remove(value);
                return node;
            } else {
                if(node.getLeft() == null && node.getRight() == null)
                    return null;
                if(node.getLeft() == null) return node.getRight();
                if(node.getRight() == null) return node.getLeft();

                Node smallestNode = smallestNode(node.getRight());
                node = smallestNode;
                node.setRight(remove(key, value, node.getRight()));

                return node;
            }
        }
        return node;
    }

    @Override
    public Iterator<V> find(K key) {
        Node n = search(key, rootNode);
        if(n != null) {
            ArrayList<V> values = n.getValues();
            return values.iterator();
        } else {
            return new ArrayList<V>().iterator();
        }
    }
    private Node search(K key, Node node) {
        while(node != null) {
            if(comparator.compare(key, node.getKey()) < 0)
                node = node.getLeft();
            else if(comparator.compare(key, node.getKey()) > 0)
                node = node.getRight();
            else
                return node;
        }
        return null;
    }

    @Override
    public Iterator<V> removeAll(K key) {
        Node n = search(key, rootNode);
        ArrayList<V> values = n.getValues();

        try {
            remove(n.getKey(), null);
        } catch (Exception e) {
            e.printStackTrace();
        }

        return values.iterator();
    }

    @Override
    public Iterator<V> listAll() {
        ArrayList<V> entries = new ArrayList<V>();
        listAll(rootNode, entries);
        return entries.iterator();
    }
    private void listAll(Node n, ArrayList<V> entries) {
        if(n != null) {
            listAll(n.getLeft(), entries);
            entries.addAll(n.getValues());
            listAll(n.getRight(), entries);
        }
    }

    @Override
    public int height() {
        return height(rootNode);
    }   

    //Custom Methods
    /**
     * A method to test if the tree is logically empty
     * 
     * @return true if empty, false if not
     */
    public boolean isEmpty() {
        return rootNode == null;
    }
    /**
     * Logically empties the tree by setting the rootNode to null
     */
    public void empty() {
        rootNode = null;
    }
    public void inOrderTraversal(Node node) {
        if(node != null) {
            inOrderTraversal(node.getLeft());
            System.out.print(node.getKey() + ", ");
            inOrderTraversal(node.getRight());
        }
    }
    public int height(Node node) {
        if(node == null) return -1;
        else return node.height;
    }
    public Node getRootNode() {
        return rootNode;
    }
    public Node smallestNode(Node node) {
        if(node.getLeft() == null)
            return node;
        return smallestNode(node.getLeft());
    }

    private Node rotateLeft(Node node2) {
        Node node1 = node2.getLeft();

        node2.setLeft(node1.getRight());
        node1.setRight(node2);

        node2.setHeight(Math.max(height(node2.getLeft()), height(node2.getRight())) + 1);
        node1.setHeight(Math.max(height(node1.getLeft()), node2.getHeight()) + 1);

        return node1;
    }
    private Node rotateRight(Node node1) {
        Node node2 = node1.getRight();

        node1.setRight(node2.getLeft());
        node2.setLeft(node1);

        node1.setHeight(Math.max(height(node1.getLeft()), height(node1.getRight())) + 1);
        node2.setHeight(Math.max(height(node2.getRight()), node1.getHeight()) + 1);

        return node2;
    }
    private Node doubleRotateLeft(Node node3) {
        node3.setLeft(rotateRight(node3.getLeft()));
        return rotateLeft(node3);
    }
    private Node doubleRotateRight(Node node1) {
        node1.setRight(rotateLeft(node1.getRight()));
        return rotateRight(node1);
    }
}

我的 AVLTree 的接口(interface):

import java.util.Iterator;

public interface IAVLTree<K,V>
{
    public V add(K k, V v);

    public V remove(K k, V v);

    public Iterator<V> removeAll(K k);

    public Iterator<V> find(K k);

    public Iterator<V> listAll();

    public int height();

}

最后，我的测试代码:

public class AVLTest
{
    private static long startTime, endTime;
    private static int amountOfCommands = 10000;

    public static void main(String[] args) {
        AVLTree<String, Integer> tree = new AVLTree<String, Integer>(String.CASE_INSENSITIVE_ORDER);
        try {
            startTime = System.currentTimeMillis();
            for (int i = 1; i <= amountOfCommands; i++) {
                String key = "K" + i;
                tree.add(key, i);
            }
            endTime = System.currentTimeMillis();
        } catch(Exception e) {
            e.printStackTrace();
        }
        long runningTime = endTime - startTime;
        System.out.println("Running Time: " + runningTime + "ms\nNo. of Commands: " + amountOfCommands);
    }
}

Answer 1

你测量错了。您的测试代码测量将所有 元素添加到树中的时间，而不是只添加一个。

startTime = System.currentTimeMillis();
for (int i = 1; i <= amountOfCommands; i++) {
    String key = "K" + i;
    tree.add(key, i);
}
endTime = System.currentTimeMillis();

您要测量的是将一个节点添加到树中所需的时间，作为树中已有节点数的函数。

for (int i = 1; i < amountOfCommands; i++) { // note the < instead of <=
    String key = "K" + i;
    tree.add(key, i);
}
String key = "K" + amountOfCommands;
startTime = System.currentTimeMillis();
tree.add(key, amountOfCommands);
endTime = System.currentTimeMillis();

当然，如果您对所有测量重复使用同一棵树，您可以更有效地运行测试。我会留给你。