org.amino.ds.tree
Class ParallelRBTree<E>

java.lang.Object
  org.amino.ds.tree.ParallelRBTree<E>

Type Parameters:

E - Type of element

public class ParallelRBTree<E>
extends java.lang.Object

This is an implementation of a relaxed balanced red-black tree data structure.

The implementation is according to the paper Relaxed Balanced Red-Black Trees by Hanke, Ottmann and Soisalon-Soininen, 1997 and The performance of concurrent RB tree algorithms by Hanke, 1998. To gain a complete understanding of this data structure, please first read this paper, available at: http://citeseer.ist.psu.edu/hanke97relaxed.html and http://citeseer.ist.psu.edu/400640.html

Relaxed balancing mean that, in a dictionary stored as a balanced tree, the necessary after updates may be delayed. This is in contrast to strict balancing meaning that rebalancing is performed immediately after update. Relaxed balancing is important for efficiency in highly dynamic applications where updates can occur in bursts. The rebalancing tasks can be performed gradually after all urgent updates, allowing the concurrent use of the dictionary even though the underlying tree structure is not completely in balance.

This implementation propose a new scheme of how to make known rebalancing techniques relaxed in an efficient way.The key idea is to accumulate insertions and deletions such that they can be settled in arbitrary order using the same rebalancing operations as for standard balanced search trees.

The tree implemented here is a leaf-oriented binary search trees, which are full binary trees (each node has either two or no children). The nullary nodes of a tree are called the external nodes or leaves while the other nodes are said to be internal nodes. We assume that the keys (chosen from a totally ordered universe) are stored in the leaves of the binary tree. The internal nods contains routers, which guide the search from the root to a leaf.

Sample performance results here

The following operations are thread-safe and scalable (but see notes in method javadoc): insert, remove, find, search.

The following operations are not thread-safe:

TODO cannot add the same value into the tree

Author:

Xiao Jun Dai

Nested Class Summary

static class

ParallelRBTree.Node<E> Internal node of tree.

Constructor Summary

ParallelRBTree()
Default constructor.

Method Summary

boolean	find(E k) Find the key in the tree.
int	getHeight() Get height of the tree.
void	inOrderWalk(Doable<E,E> operation) Iterate the tree in-order.
void	insert(E element) Insert a element into the tree.
int	leftSubtreeHeight() Get height of left subtree.
void	printBinTree() Print the reb-blak tree.
void	printLeafs() Print all leafs in the tree.
boolean	remove(E element) remove an element from the tree.
int	rightSubtreeHeight() Get height of right subtree.
ParallelRBTree.Node<E>	search(E k) Find the key in the tree.
void	shutdown() Shutdown balancer thread.
boolean	verifyRBTreeHeight() Verify the height of the tree conform to the rule of red-black tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

ParallelRBTree

public ParallelRBTree()

Default constructor.

Method Detail

shutdown

public void shutdown()

Shutdown balancer thread.

insert

public void insert(E element)

Insert a element into the tree.

Parameters:

element - element

remove

public boolean remove(E element)

remove an element from the tree.

Parameters:

element - element to be removed

Returns:

true if node is removed, otherwise false

inOrderWalk

public void inOrderWalk(Doable<E,E> operation)

Iterate the tree in-order.

Parameters:

operation - operation done during walk

find

public boolean find(E k)

Find the key in the tree.

Parameters:

k - key

Returns:

true if found, otherwise false

search

public ParallelRBTree.Node<E> search(E k)

Find the key in the tree.

Parameters:

k - key

Returns:

node found otherwise null

getHeight

public int getHeight()

Get height of the tree.

Returns:

height of the tree

printLeafs

public void printLeafs()

Print all leafs in the tree.

leftSubtreeHeight

public int leftSubtreeHeight()

Get height of left subtree.

Returns:

height of left subtree.

rightSubtreeHeight

public int rightSubtreeHeight()

Get height of right subtree.

Returns:

height of right subtree.

verifyRBTreeHeight

public boolean verifyRBTreeHeight()

Verify the height of the tree conform to the rule of red-black tree.

Returns:

true if conforming to the rule of red-black tree otherwise false.

printBinTree

public void printBinTree()

Print the reb-blak tree.