Package net.cscott.jutil

Class RedBlackTree<K>

java.lang.Object
net.cscott.jutil.BinaryTree<K>
net.cscott.jutil.RedBlackTree<K>
Type Parameters:
K - the type of the elements in this tree
Direct Known Subclasses:
IntervalTree
public class RedBlackTree<K> extends BinaryTree<K>
A RedBlackTree is a BinaryTree that uses red-black properties to maintain a balanced form.
See Also:
  • "CLR section 14, (page 263)."

  • Constructor Details

    • RedBlackTree

      public RedBlackTree()

    • RedBlackTree

      public RedBlackTree(Comparator<? super K> c)

  • Method Details

    • makeNode

      protected BinaryTree<K>.Node makeNode(K o)
      Factory method for BinaryTree<K>.Node. Every construction of a BinaryTree<K>.Node takes place through this method; thus subclasses of RedBlackTree can associate new data with their own nodes by extending the BinaryTree<K>.Node class and overriding this method.
      Overrides:
      makeNode in class BinaryTree<K>

    • insertNode

      protected void insertNode(BinaryTree<K>.Node x)
      Description copied from class: BinaryTree
      Inserts z into some appropriate position in this. requires: (z.left == z.right == NIL) modifies: this, z From CLR, pg 251.
      Overrides:
      insertNode in class BinaryTree<K>

    • swapPositions

      protected void swapPositions(BinaryTree<K>.Node a, BinaryTree<K>.Node b)
      Description copied from class: BinaryTree
      Switches the positions of a and b within this. Both must be in the tree; one may be the other's parent. Subclasses are expected to swap any data derived from the positions as well.
      Overrides:
      swapPositions in class BinaryTree<K>

    • deleteNode

      protected void deleteNode(BinaryTree<K>.Node z)
      Description copied from class: BinaryTree
      Splices z out from this. Based on CLR, pg 253. modifies: this, z
      Overrides:
      deleteNode in class BinaryTree<K>

    • rbDeleteFixup

      protected void rbDeleteFixup(BinaryTree<K>.Node x)
      Post delete fixup routine.
      See Also:
      • "CLR, pg. 274"

    • leftRotate

      protected void leftRotate(BinaryTree<K>.Node x)
      Pivots around the edge (x,x.right). Assumes x.right != null.

    • rightRotate

      protected void rightRotate(BinaryTree<K>.Node x)
      Pivots around the edge (x,x.left). Assumes x.left != NIL.