Package net.cscott.jutil

Class BinaryTree<K>

java.lang.Object
net.cscott.jutil.BinaryTree<K>
Type Parameters:
K - the type of the elements in this tree
Direct Known Subclasses:
RedBlackTree
public class BinaryTree<K> extends Object
A BinaryTree is a Tree where each node has at most two children.

All elements of a given BinaryTree t must be mutually comparable, either inherently or through an external Comparator.

Unlike a TreeSet, duplicate elements are allowed in a BinaryTree.

FSK: We should probably have a Tree interface by now... Sometimes you want to expose the fact that you're working with a Tree, instead of abstract it into a Set or what-have-you. Have to think about adding that.

See Also:
  • "CLR section 13, (page 244)."

  • Field Details

  • Constructor Details

    • BinaryTree

      public BinaryTree()
      Creates an empty tree which accepts only mutually comparable elements.
      See Also:

    • BinaryTree

      public BinaryTree(Comparator<? super K> c)
      Creates an empty tree which uses c to determine element ordering.

  • Method Details

    • makeNode

      protected BinaryTree<K>.Node makeNode(K key)
      Creates a BinaryTree<K>.Node n for this such that n.key == k. 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.

      Note that makeNode must deal with the case when key is null, regardless of whether the tree itself allows null elements, because the NIL sentinel node has null as its key.

    • setLeft

      protected BinaryTree<K>.Node setLeft(BinaryTree<K>.Node p, BinaryTree<K>.Node l)
      Sets the left child of p. Modifies: this, p, l Effects: p.left_post = l. Returns: p.left_pre.

    • setRight

      protected BinaryTree<K>.Node setRight(BinaryTree<K>.Node p, BinaryTree<K>.Node r)
      Sets the right child of p. Modifies: this, p, r Effects: p.right_post = r. Returns: p.right_pre.

    • setParent

      protected BinaryTree<K>.Node setParent(BinaryTree<K>.Node c, BinaryTree<K>.Node p)
      Sets the parent of p. Modifies: this, c, p Effects: c.parent_post = p. Returns: c.parent_pre.

    • swapPositions

      protected void swapPositions(BinaryTree<K>.Node a, BinaryTree<K>.Node b)
      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.

    • root

      protected BinaryTree<K>.Node root()

    • setRoot

      protected BinaryTree<K>.Node setRoot(BinaryTree<K>.Node r)

    • add

      public BinaryTree<K>.Node add(K k)
      Constructs a node for k and inserts it into this. Uses nodes' own methods to dispatch

    • remove

      public void remove(Object k)

    • contains

      public boolean contains(Object k)
      Returns true if k is present in this.

    • minimum

      public K minimum()
      Returns the minimum element of this. Requires: this is non-empty.

    • maximum

      public K maximum()
      Returns the maximum element of this. Requires: this is non-empty.

    • search

      protected BinaryTree<K>.Node search(BinaryTree<K>.Node x, Object k)
      Finds the Node n (in the subtree rooted at x) such that n.key = k. From CLR, pg 248.

    • minimum

      protected BinaryTree<K>.Node minimum(BinaryTree<K>.Node x)
      Finds the minimum Node n (in the subtree rooted at x). From CLR, pg 248.

    • maximum

      protected BinaryTree<K>.Node maximum(BinaryTree<K>.Node x)
      Finds the maximum Node n (in the subtree rooted at x). From CLR, pg 248.

    • successor

      protected BinaryTree<K>.Node successor(BinaryTree<K>.Node x)
      Returns the successor of x in the sorted order determined by an inorder tree walk. From CLR, pg 249.

    • insertNode

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

    • deleteNode

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

    • dump

      public String dump()

    • dump

      public String dump(BinaryTree<K>.Node x)