Class RBTNode<T>
- java.lang.Object
-
- org.apache.uima.internal.util.rb_trees.RBTNode<T>
-
class RBTNode<T> extends java.lang.Object
Node used in RedBlackTree, holds int Object pairs and links Red-Black Tree node. Not for public use. Use the interface in RedBlackTree instead. This should probably be an internal class to RedBlackTree, but it's easier to read in a seperate file. See comments in RedBlackTree.
-
-
Field Summary
Fields Modifier and Type Field Description private static boolean
BLACK
private boolean
color
(package private) T
element
private static int
indentInc
private int
key
(package private) RBTNode<T>
left
private RBTNode<T>
parent
private static boolean
RED
(package private) RBTNode<T>
right
-
Constructor Summary
Constructors Modifier Constructor Description private
RBTNode(int key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right, T element)
The real constructor, used only internally.(package private)
RBTNode(int key, T element)
The standard constructor as used by RedBlackTree.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static <T> boolean
colorOf(RBTNode<T> x)
(package private) static <T> void
delete(RedBlackTree<T> tree, RBTNode<T> z)
Delete a given node from the tree.private static <T> void
deleteFixup(RedBlackTree<T> tree, RBTNode<T> x)
From CLR.private static <T> void
deleteFixupNull(RedBlackTree<T> tree, RBTNode<T> x)
Like deleteFixup(), only that the node we should be working on is null, and we actually hand in the node's mother.(package private) static <T> RBTNode<T>
find(RBTNode<T> x, int key)
Find a node with a certain key.(package private) void
getBinaryTree(BinaryTree tree)
(package private) static <T> boolean
insert(RedBlackTree<T> tree, RBTNode<T> x)
Insert a node into a tree.(package private) int
keys(int pos, int[] keys)
Fill an array with the keys contained in the tree.private static <T> RBTNode<T>
leftOf(RBTNode<T> x)
private void
leftRotate(RedBlackTree<T> tree)
Left rotation, used to keep the tree balanced.void
printElements(int indent)
void
printKeys(int indent)
private static <T> RBTNode<T>
rightOf(RBTNode<T> x)
private void
rightRotate(RedBlackTree<T> tree)
Right rotation, used to keep the tree balanced.private static <T> void
setColor(RBTNode<T> x, boolean c)
(package private) RBTNode<T>
successor()
Find the successor node to this.private static <T> boolean
treeInsert(RedBlackTree<T> tree, RBTNode<T> z)
Auxiliary function for insert().
-
-
-
Field Detail
-
RED
private static final boolean RED
- See Also:
- Constant Field Values
-
BLACK
private static final boolean BLACK
- See Also:
- Constant Field Values
-
key
private int key
-
color
private boolean color
-
element
T element
-
indentInc
private static final int indentInc
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
RBTNode
private RBTNode(int key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right, T element)
The real constructor, used only internally.
-
RBTNode
RBTNode(int key, T element)
The standard constructor as used by RedBlackTree.- Parameters:
key
- The key to be inserted.element
- The value to be inserted.
-
-
Method Detail
-
find
static final <T> RBTNode<T> find(RBTNode<T> x, int key)
Find a node with a certain key. Returns null if no such node exists.
-
insert
static final <T> boolean insert(RedBlackTree<T> tree, RBTNode<T> x)
Insert a node into a tree. See CLR.
-
treeInsert
private static final <T> boolean treeInsert(RedBlackTree<T> tree, RBTNode<T> z)
Auxiliary function for insert(). See CLR.
-
leftRotate
private final void leftRotate(RedBlackTree<T> tree)
Left rotation, used to keep the tree balanced. See CLR.
-
rightRotate
private final void rightRotate(RedBlackTree<T> tree)
Right rotation, used to keep the tree balanced. See CLR.
-
delete
static final <T> void delete(RedBlackTree<T> tree, RBTNode<T> z)
Delete a given node from the tree. The node must be contained in the tree! Our code is more complicated than CLR because we don't use a NIL sentinel.
-
deleteFixup
private static final <T> void deleteFixup(RedBlackTree<T> tree, RBTNode<T> x)
From CLR. x must not be null.
-
deleteFixupNull
private static final <T> void deleteFixupNull(RedBlackTree<T> tree, RBTNode<T> x)
Like deleteFixup(), only that the node we should be working on is null, and we actually hand in the node's mother. Special case because we don't use sentinels.
-
keys
int keys(int pos, int[] keys)
Fill an array with the keys contained in the tree. The array must at least have the size of the tree! Returns the size of the tree, for internal reasons.
-
colorOf
private static final <T> boolean colorOf(RBTNode<T> x)
-
setColor
private static final <T> void setColor(RBTNode<T> x, boolean c)
-
printKeys
public void printKeys(int indent)
-
printElements
public void printElements(int indent)
-
getBinaryTree
void getBinaryTree(BinaryTree tree)
-
-