Class RBTNode<T>

java.lang.Object
org.apache.uima.internal.util.rb_trees.RBTNode<T>

class RBTNode<T> extends 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 Details

  • 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

      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.
    • successor

      final RBTNode<T> successor()
      Find the successor node to this.
    • 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)
    • leftOf

      private static final <T> RBTNode<T> leftOf(RBTNode<T> x)
    • rightOf

      private static final <T> RBTNode<T> rightOf(RBTNode<T> x)
    • printKeys

      public void printKeys(int indent)
    • printElements

      public void printElements(int indent)
    • getBinaryTree

      void getBinaryTree(BinaryTree tree)