-
Notifications
You must be signed in to change notification settings - Fork 0
/
sp5-bst-2018f.txt
26 lines (20 loc) · 1.16 KB
/
sp5-bst-2018f.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Implementation of data structures and algorithms
Fall 2018
Short Project 5: Blanced binary search trees
Thu, Sep 27, 2018
Version 1.0: Initial description (Thu, Sep 27).
Due: 11:59 PM, Sun, Dec 16.
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.
1. Extend BST to AVL trees (AVLTree). Starter code: AVLTree.java.
2. Extend BST to Red Black Trees (RedBlacktree). Starter code: RedBlackTree.java.
3. 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.