Class 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.
    • 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.
      • 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)