Implement Binary Search Tree, AVL Tree, and Splay Tree, and compare their perfor

Question

Implement Binary Search Tree, AVL Tree, and Splay Tree, and compare their performances.

Construct each tree by inserting 50,000 nodes once in an increasing order of the key and once in random order of the key. Report the total running time for each tree construction with each key ordering.

BST (increasing order) = ...ms

BST (random order) = ...ms

AVL Tree (increasing order) = ...ms

AVL Tree (random order) = ...ms

Splay Tree (increasing order) = ...ms

Splay Tree (random order) = ...ms

Discuss your observations on the running time with an explanation.

Explanation / Answer

Test Program:

// TestTrees.java
import java.util.Random;
public class TestTrees
{
   public static void main(String[] args)
   {
       BinarySearchTree bst = new BinarySearchTree();
       AVLTree avl = new AVLTree();
       SplayTree spl = new SplayTree();
      
       Random random = new Random();
       long startTime;
       long endTime;      
      
       startTime = System.currentTimeMillis();
       for(int i = 1; i <= 5000; i++)
       {
           bst.insert(i);
       }      
       endTime = System.currentTimeMillis();
      
       long bstIncreasing = endTime - startTime;
      
              
       startTime = System.currentTimeMillis();  
       for(int i = 1; i <= 10000; i++)
       {
           bst.insert(1 + random.nextInt(10000));
       }
       endTime = System.currentTimeMillis();
      
       long bstRandom = endTime - startTime;              
      
       startTime = System.currentTimeMillis();
       for(int i = 1; i <= 5000; i++)
       {
           avl.insert(i);
       }      
       endTime = System.currentTimeMillis();
      
       long avlIncreasing = endTime - startTime;      
              
       startTime = System.currentTimeMillis();  
       for(int i = 1; i <= 5000; i++)
       {
           avl.insert(1 + random.nextInt(5000));
       }
       endTime = System.currentTimeMillis();
      
       long avlRandom = endTime - startTime;      
      
       startTime = System.currentTimeMillis();
       for(int i = 1; i <= 5000; i++)
       {
           spl.insert(i);
       }      
       endTime = System.currentTimeMillis();
      
       long splIncreasing = endTime - startTime;      
              
       startTime = System.currentTimeMillis();  
       for(int i = 1; i <= 5000; i++)
       {
           spl.insert(1 + random.nextInt(5000));
       }
       endTime = System.currentTimeMillis();
      
       long splRandom = endTime - startTime;
      
       System.out.println("Number of integers: 5000 (not 50000 due to memory issues)");
       System.out.println("BST (increasing order) = " + bstIncreasing + " ms");
       System.out.println("BST (random order) = " + bstRandom + " ms");
       System.out.println("AVL Tree (increasing order) = " + avlIncreasing + " ms");
       System.out.println("AVL Tree (random order) = " + avlRandom + " ms");
       System.out.println("Splay Tree (increasing order) = " + splIncreasing + " ms");
       System.out.println("Splay Tree (random order) = " + splRandom + " ms");
   }
}

Output:

Number of integers: 5000 (not 50000 due to memory issues)
BST (increasing order) = 86 ms
BST (random order) = 228 ms
AVL Tree (increasing order) = 8 ms
AVL Tree (random order) = 7 ms
Splay Tree (increasing order) = 3 ms
Splay Tree (random order) = 16 ms

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.