net.cscott.jutil
Class BinaryTree

java.lang.Object
  net.cscott.jutil.BinaryTree

Direct Known Subclasses:

RedBlackTree

public class BinaryTree
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)."

Nested Class Summary

class

BinaryTree.Node A BinaryTree.Node is an element of this tree.

Field Summary

protected Comparator	comp
protected BinaryTree.Node	NIL

Constructor Summary

BinaryTree()
Creates an empty tree which accepts only mutually comparable elements.

BinaryTree(Comparator c)
Creates an empty tree which uses c to determine element ordering.

Method Summary

BinaryTree.Node	add(Object k) Constructs a node for k and inserts it into this.
boolean	contains(Object k) Returns true if k is present in this.
protected void	deleteNode(BinaryTree.Node z) Splices z out from this.
String	dump()
String	dump(BinaryTree.Node x)
protected void	insertNode(BinaryTree.Node z) Inserts z into some appropriate position in this.
static void	main(String[] args)
protected BinaryTree.Node	makeNode(Object key) Creates a BinaryTree.Node n for this such that n.key == k.
Object	maximum() Returns the maximum element of this.
protected BinaryTree.Node	maximum(BinaryTree.Node x) Finds the maximum Node n (in the subtree rooted at x).
Object	minimum() Returns the minimum element of this.
protected BinaryTree.Node	minimum(BinaryTree.Node x) Finds the minimum Node n (in the subtree rooted at x).
void	remove(Object k)
protected BinaryTree.Node	root()
protected BinaryTree.Node	search(BinaryTree.Node x, Object k) Finds the Node n (in the subtree rooted at x) such that n.key = k.
protected BinaryTree.Node	setLeft(BinaryTree.Node p, BinaryTree.Node l) Sets the left child of p.
protected BinaryTree.Node	setParent(BinaryTree.Node c, BinaryTree.Node p) Sets the parent of p.
protected BinaryTree.Node	setRight(BinaryTree.Node p, BinaryTree.Node r) Sets the right child of p.
protected BinaryTree.Node	setRoot(BinaryTree.Node r)
protected BinaryTree.Node	successor(BinaryTree.Node x) Returns the successor of x in the sorted order determined by an inorder tree walk.
protected void	swapPositions(BinaryTree.Node a, BinaryTree.Node b) Switches the positions of a and b within this.
void	test()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

NIL

protected final BinaryTree.Node NIL

comp

protected Comparator comp

Constructor Detail

BinaryTree

public BinaryTree()

Creates an empty tree which accepts only mutually comparable elements.

See Also:

Comparable

BinaryTree

public BinaryTree(Comparator c)

Creates an empty tree which uses c to determine element ordering.

Method Detail

makeNode

protected BinaryTree.Node makeNode(Object key)

Creates a BinaryTree.Node n for this such that n.key == k. Factory method for BinaryTree.Node. Every construction of a BinaryTree.Node takes place through this method; thus subclasses of RedBlackTree can associate new data with their own nodes by extending the BinaryTree.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.Node setLeft(BinaryTree.Node p,
                                  BinaryTree.Node l)

Sets the left child of p. Modifies: this, p, l Effects: p.left_post = l. Returns: p.left_pre.

setRight

protected BinaryTree.Node setRight(BinaryTree.Node p,
                                   BinaryTree.Node r)

Sets the right child of p. Modifies: this, p, r Effects: p.right_post = r. Returns: p.right_pre.

setParent

protected BinaryTree.Node setParent(BinaryTree.Node c,
                                    BinaryTree.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.Node a,
                             BinaryTree.Node b)

Switches the positions of a and b within this. Subclasses are expected to swap any data derived from the positions as well.

root

protected BinaryTree.Node root()

setRoot

protected BinaryTree.Node setRoot(BinaryTree.Node r)

add

public BinaryTree.Node add(Object 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 Object minimum()

Returns the minimum element of this. Requires: this is non-empty.

maximum

public Object maximum()

Returns the maximum element of this. Requires: this is non-empty.

search

protected BinaryTree.Node search(BinaryTree.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.Node minimum(BinaryTree.Node x)

Finds the minimum Node n (in the subtree rooted at x). From CLR, pg 248.

maximum

protected BinaryTree.Node maximum(BinaryTree.Node x)

Finds the maximum Node n (in the subtree rooted at x). From CLR, pg 248.

successor

protected BinaryTree.Node successor(BinaryTree.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.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.Node z)

Splices z out from this. Based on CLR, pg 253. modifies: this, z

test

public void test()

main

public static void main(String[] args)

dump

public String dump()

dump

public String dump(BinaryTree.Node x)