0
我在java中創建了AVLTree，add方法應該是O（log n）...但是我的add方法似乎給了我是一個O（c^n）圖或者一個指數圖而不是一個對數圖。這裏是運行時間與輸入大小的圖表：AVL Tree給我O（c^n）而不是O（log 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接口：
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);
}
}
Big-O符號描述了漸近界。您正在測量頻譜的較低端，其他效果（如緩存層次結構）啓動。將測量結果擴展幾個數量級可能會更好。 – the8472
@ the8472你是什麼意思擴展我的測量？當然，即使這樣，它仍然應該給我一個日誌運行時間？ – madcrazydrumma
他在說你需要在樹的大小足夠大的地方運行測試;更多元素或操作。您需要運行許多測試才能獲得準確的測量結果。無論你考慮什麼樣的基地（例如基數2，基數10等等），等級的次數都會更高。 –