Class RBTNode<T>
java.lang.Object
org.apache.uima.internal.util.rb_trees.RBTNode<T>
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 -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static final <T> boolean
(package private) static final <T> void
delete
(RedBlackTree<T> tree, RBTNode<T> z) Delete a given node from the tree.private static final <T> void
deleteFixup
(RedBlackTree<T> tree, RBTNode<T> x) From CLR.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.(package private) static final <T> RBTNode<T>
Find a node with a certain key.(package private) void
getBinaryTree
(BinaryTree tree) (package private) static final <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 final <T> RBTNode<T>
private final void
leftRotate
(RedBlackTree<T> tree) Left rotation, used to keep the tree balanced.void
printElements
(int indent) void
printKeys
(int indent) private static final <T> RBTNode<T>
private final void
rightRotate
(RedBlackTree<T> tree) Right rotation, used to keep the tree balanced.private static final <T> void
Find the successor node to this.private static final <T> boolean
treeInsert
(RedBlackTree<T> tree, RBTNode<T> z) Auxiliary function for insert().
-
Field Details
-
RED
private static final boolean RED- See Also:
-
BLACK
private static final boolean BLACK- See Also:
-
key
private int key -
color
private boolean color -
parent
-
left
-
right
-
element
T element -
indentInc
private static final int indentInc- See Also:
-
-
Constructor Details
-
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 Details
-
find
Find a node with a certain key. Returns null if no such node exists. -
successor
Find the successor node to this. -
insert
Insert a node into a tree. See CLR. -
treeInsert
Auxiliary function for insert(). See CLR. -
leftRotate
Left rotation, used to keep the tree balanced. See CLR. -
rightRotate
Right rotation, used to keep the tree balanced. See CLR. -
delete
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
From CLR. x must not be null. -
deleteFixupNull
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
-
setColor
-
leftOf
-
rightOf
-
printKeys
public void printKeys(int indent) -
printElements
public void printElements(int indent) -
getBinaryTree
-