self-balancing-trees

Splay Tree

This is a Java implementation of a Splay Tree. It is utilized in a fictional "recent contacts" program similar to the one used in Android's starred contacts list.

Definition

Splay Trees are Binary Search Trees with an added property that any time an element is accessed (search, add, delete) it is then migrated to the root of the tree by way of left– and right–rotations:

(Via Wikimedia Commons)

This keeps the most recently used items near the top of the tree, at the expense of keeping the tree quite degenerate"). The tree is called a Splay Tree because of how stretched out it can usually get. Nonetheles, because of the principle of locality, the operations search, insert, and delete all operate on the order of O(lg") n) amortized time, even though the true worst case is O(n) for all three.

Usage

1. Clone the repository
2. Copy the contents of the src directory to your project
3. Instantiate a new Splay Tree in your project

For example, if you want a Splay Tree of type String, add this line in your program:

SplayTree<String> tree = new SplayTree<String>();

Public Methods

1. SplayTree(), SplayTree(T d), or SplayTree(Node<T> n)
2. addElement(T d) or addElement(Node<T> n)
3. findElement(T d) or findElement(Node<T> n)
4. removeElement(T d) or removeElement(Node<T> n)

Look at the contents of the file RecentContacts.java for an example use of each of these methods.

Testing

Also included in this program are the files used for testing the public methods of the various classes. I built this program using Eclipse and tested it with JUnit. If you wish to run these unit tests, you will need to have JUnit 4+ installed.