Implementation of Balanced Binary Search Trees - AVLTree, RedBlackTree, SplayTree.
There is no required team task in SP5. This is an optional assignment (for individual submission only), with deadline at the end of the semester. Important: elegance of code, code reuse from BST, and implementation of single pass algorithms, where possible.
-
Extend BST to AVL trees (AVLTree). Starter code: AVLTree.java.
-
Extend BST to Red Black Trees (RedBlacktree). Starter code: RedBlackTree.java.
-
Extend BST to Splay Trees (SplayTree). Implement bottom-up splaying. Include in your submission, code that generates a random sequence of add/remove/contains operations, with skewed distributions. Experiment and find probability distributions for which the splay tree is faster than BST or Java's TreeMap for a sequence of n operations by at least 10%, for large n (say, 10M+). The probability distribution need not be uniform, but every element should have a non-zero probability of being chosen for contains/remove. Starter code: SplayTree.java.