Red-black tree
 All Classes Functions
Classes | Public Member Functions | Protected Member Functions | List of all members
org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V > Class Reference
Inheritance diagram for org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >:

Classes

class  Node
 

Public Member Functions

int size ()
 
String toString ()
 

Protected Member Functions

Node getNilNode ()
 
Node getRootNode ()
 
void add (Node z)
 
Node minimum (Node x)
 
Node successor (Node x)
 
void remove (Node z)
 
Node search (K key)
 
Iterator< Node > nodesIterator ()
 

Detailed Description

A minimalist implementation of a red black tree.

Parameters
Ka type of nodes keys
Va type of nodes values
Author
Karol Sobczak

Definition at line 14 of file RedBlackTree.java.

Member Function Documentation

void org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.add ( Node  z)
protected

Adds a new node into the red-black tree.

Parameters
za new node

Definition at line 353 of file RedBlackTree.java.

Node org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.getNilNode ( )
protected

Returns a nil node.

Returns
a nil node

Definition at line 337 of file RedBlackTree.java.

Node org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.getRootNode ( )
protected

Returns a root node.

Returns
a root node

Definition at line 345 of file RedBlackTree.java.

Node org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.minimum ( Node  x)
protected

Returns a node with a minimum value for a subtree.

Parameters
xa root of a subtree
Returns
a node with a minimum value

Definition at line 382 of file RedBlackTree.java.

Iterator<Node> org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.nodesIterator ( )
protected

Returns an iterator for the red-black tree nodes (in ascending order).

Returns
an iterator for the red-black tree nodes (in ascending order)

Definition at line 467 of file RedBlackTree.java.

void org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.remove ( Node  z)
protected

Removes a node from a tree.

Parameters
za node to be removed

Definition at line 411 of file RedBlackTree.java.

Node org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.search ( key)
protected

Searches for a node containing a given key.

Parameters
keya key to be found
Returns
a node containing a given key or nil if such node does not exist

Definition at line 451 of file RedBlackTree.java.

int org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.size ( )

Returns a current red-black tree size.

Returns
a current red-black tree size

Definition at line 475 of file RedBlackTree.java.

Node org.adblocktv.tagsserver.utils.rbtree.RedBlackTree< K extends Comparable, V >.successor ( Node  x)
protected

Returns a node successor.

Parameters
xa node for which a successor should be found
Returns
a successor for a node x or nil if such node does not exists

Definition at line 394 of file RedBlackTree.java.


The documentation for this class was generated from the following file: