net.cscott.jutil

Class BinaryTree

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 `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 `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()

Field Detail

comp

protected Comparator comp

NIL

protected final BinaryTree.Node NIL

Constructor Detail

BinaryTree

public BinaryTree()

Creates an empty tree which accepts only mutually comparable elements.

BinaryTree

public BinaryTree(Comparator c)

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

Method Detail

add

public BinaryTree.Node add(Object k)

Constructs a node for k and inserts it into this. Uses nodes' own methods to dispatch

contains

public boolean contains(Object k)

Returns true if k is present in this.

deleteNode

protected void deleteNode(BinaryTree.Node z)

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

dump

public String dump()

dump

public String dump(BinaryTree.Node x)

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.

main

public static void main(String[] args)

makeNode

protected BinaryTree.Node makeNode(Object key)

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

maximum

public Object maximum()

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

maximum

protected BinaryTree.Node maximum(BinaryTree.Node x)

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

minimum

public Object minimum()

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

minimum

protected BinaryTree.Node minimum(BinaryTree.Node x)

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

remove

public void remove(Object k)

root

protected BinaryTree.Node root()

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.

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.

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.

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.

setRoot

protected BinaryTree.Node setRoot(BinaryTree.Node r)

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.

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.

test

public void test()