net.sf.ij_plugins.util

Class RedBlackTree<K extends java.lang.Comparable<K>>

java.lang.Object

net.sf.ij_plugins.util.RedBlackTree<K>

public final class RedBlackTree<K extends java.lang.Comparable<K>>
extends java.lang.Object

Implements a red-black tree.

Author:

Jarek Sacha

Constructor Summary

Constructors

Constructor and Description
RedBlackTree()

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Remove all nodes from the tree.
boolean	contains(K key) Test if tree contains key.
void	insert(K key)
boolean	isEmpty() Test if the tree is logically empty.
void	printTree()
boolean	remove(K key)
K	select(int i) Select i-th key in the tree (key with rank i).
int	size()
void	verify()

Methods inherited from class java.lang.Object

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

Constructor Detail

RedBlackTree

public RedBlackTree()

Method Detail

verify

public void verify()
            throws java.lang.IllegalStateException

Throws:

java.lang.IllegalStateException

clear

public void clear()

Remove all nodes from the tree.

size

public int size()

insert

public void insert(K key)

remove

public boolean remove(K key)

select

public K select(int i)

Select i-th key in the tree (key with rank i).

Parameters:

i - rank of the key to elect.

Returns:

value of key with rank i.

contains

public boolean contains(K key)

Test if tree contains key.

Parameters:

key - the key to search for.

Returns:

the matching key or null if not found.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

printTree

public void printTree()