DataStructures
Class Treap

java.lang.Object
  |
  +--DataStructures.Treap

public class Treap

extends java.lang.Object

Implements a treap. Note that all "matching" is based on the compareTo method.

Constructor Summary

Treap()
Construct the treap.

Method Summary

Comparable	find(Comparable x) Find an item in the tree.
Comparable	findMax() Find the largest item in the tree.
Comparable	findMin() Find the smallest item in the tree.
void	insert(Comparable x) Insert into the tree.
boolean	isEmpty() Test if the tree is logically empty.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the tree logically empty.
void	printTree() Print the tree contents in sorted order.
void	remove(Comparable x) Remove from the tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Treap

public Treap()

Construct the treap.

Method Detail

insert

public void insert(Comparable x)

Insert into the tree. Does nothing if x is already present.

Parameters:

x - the item to insert.

remove

public void remove(Comparable x)

Remove from the tree. Does nothing if x is not found.

Parameters:

x - the item to remove.

findMin

public Comparable findMin()

Find the smallest item in the tree.

Returns:

the smallest item, or null if empty.

findMax

public Comparable findMax()

Find the largest item in the tree.

Returns:

the largest item, or null if empty.

find

public Comparable find(Comparable x)

Find an item in the tree.

Parameters:

x - the item to search for.

Returns:

the matching item, or null if not found.

makeEmpty

public void makeEmpty()

Make the tree logically empty.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

printTree

public void printTree()

Print the tree contents in sorted order.

main

public static void main(java.lang.String[] args)