Class IntRBTNode


  • class IntRBTNode
    extends java.lang.Object
    Integer Red-Black Tree node. Not for public use. Use the interface in IntRedBlackTree instead. This should probably be an internal class to IntRedBlackTree, but it's easier to read in a seperate file. See comments in IntRedBlackTree.
    • Constructor Detail

      • IntRBTNode

        private IntRBTNode​(int key,
                           boolean color,
                           IntRBTNode parent,
                           IntRBTNode left,
                           IntRBTNode right,
                           int element)
        The real constructor, used only internally.
      • IntRBTNode

        IntRBTNode​(int key,
                   int element)
        The standard constructor as used by IntRedBlackTree.
        Parameters:
        key - The key to be inserted.
        element - The value to be inserted.
    • Method Detail

      • find

        static final IntRBTNode find​(IntRBTNode x,
                                     int key)
        Find a node with a certain key. Returns null if no such node exists.
      • successor

        final IntRBTNode successor()
        Find the successor node to this.
      • treeInsert

        private static final boolean treeInsert​(IntRedBlackTree tree,
                                                IntRBTNode z)
        Auxiliary function for insert(). See CLR.
      • leftRotate

        private final void leftRotate​(IntRedBlackTree tree)
        Left rotation, used to keep the tree balanced. See CLR.
      • rightRotate

        private final void rightRotate​(IntRedBlackTree tree)
        Right rotation, used to keep the tree balanced. See CLR.
      • delete

        static final void delete​(IntRedBlackTree tree,
                                 IntRBTNode 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.
      • deleteFixupNull

        private static final void deleteFixupNull​(IntRedBlackTree tree,
                                                  IntRBTNode 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.
      • toArray

        int[] toArray​(int offset)
        Create an array representation for the tree under this node. See IntRBTArray for a definition of the resulting array format.
        Parameters:
        offset - See IntRedBlackTree.toArray() for comments.
        Returns:
        The generated array.
      • colorOf

        private static final boolean colorOf​(IntRBTNode x)
      • setColor

        private static final void setColor​(IntRBTNode x,
                                           boolean c)
      • printKeys

        public void printKeys​(int indent)
      • printElements

        public void printElements​(int indent)