jdsl.core.api
Interface BinaryTree

All Superinterfaces:

Container, InspectableBinaryTree, InspectableContainer, InspectablePositionalContainer, InspectableTree, PositionalContainer

All Known Implementing Classes:

NodeBinaryTree

public interface BinaryTree

extends InspectableBinaryTree, PositionalContainer

A modifiable tree in which each node has either zero or two children. Binary trees are conceived as starting with a single external node (a/k/a leaf) at the root. (The node's initial element is null.) Thus, a BinaryTree is never empty (isEmpty() is always false). Furthermore, since size() returns the number of internal and external leaves, size() is always at least 1. The splicing methods, link(.) and replaceSubtree(.), leave the spliced-in container with a single external node storing null. The iterator() of a BinaryTree gives nodes in preorder. Note that a (modifiable) BinaryTree cannot be used where a (modifiable) Tree is needed (it would violate the Liskov Substitution Principle, because a tree has the ability to insert arbitrary numbers of children). Hence this interface does not extend the Tree interface. For the inspectable counterparts the substitution principle holds, so InspectableBinaryTree is a subinterface of InspectableTree.

Version:

$Id: BinaryTree.java,v 1.13 2000/01/12 03:21:26 mdh Exp $

Author:

Mark Handy (mdh), Mike Boilen (mgb), Andrew Schwerin (schwerin)

See Also:

InspectableBinaryTree

Method Summary

BinaryTree	cut(Position node) Position node and all its children are removed from this binary tree and replaced with a new external node with a null element.
void	expandExternal(Position node) The external position specified is transformed into an internal, and it gains two external children.
void	graftOnLeft(Position subtreeRoot, java.lang.Object eltOfParent, BinaryTree newSubtree) Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the right child of a new node storing the given element.
void	graftOnRight(Position subtreeRoot, java.lang.Object eltOfParent, BinaryTree newSubtree) Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the left child of a new node, storing the given element.
java.lang.Object	link(Position node, BinaryTree newSubtree) Links binary tree newSubtree at external node node by replacing node with the root of newSubtree.
void	removeAboveExternal(Position node) The parent of node is deleted, and the sibling of node, with all its children, is installed in its place; node is also deleted.
BinaryTree	replaceSubtree(Position subtreeRoot, BinaryTree newSubtree) Swaps a subtree of this binary tree with a binary tree passed in.

Methods inherited from interface jdsl.core.api.InspectableBinaryTree

leftChild, rightChild, sibling

Methods inherited from interface jdsl.core.api.InspectableTree

childAtRank, children, firstChild, isExternal, isInternal, isRoot, lastChild, numChildren, parent, rankOfChild, root, siblingAfter, siblingBefore, siblings

Methods inherited from interface jdsl.core.api.InspectablePositionalContainer

positions

Methods inherited from interface jdsl.core.api.InspectableContainer

contains, elements, isEmpty, size

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Methods inherited from interface jdsl.core.api.Container

newContainer, replaceElement

Method Detail

expandExternal

public void expandExternal(Position node)
                    throws InvalidAccessorException

The external position specified is transformed into an internal, and it gains two external children. The position reference itself doesn't change. The elements of its two new, external children are both null.

Parameters:

node - any external position in this binary tree

Throws:

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

removeAboveExternal

public void removeAboveExternal(Position node)
                         throws BoundaryViolationException,
                                InvalidAccessorException

The parent of node is deleted, and the sibling of node, with all its children, is installed in its place; node is also deleted.

Parameters:

node - any external position in this binary tree

Throws:

BoundaryViolationException - if node is an external position, as required, but also the root of this binary tree.

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

cut

public BinaryTree cut(Position node)
               throws InvalidAccessorException

Position node and all its children are removed from this binary tree and replaced with a new external node with a null element. They are packaged in a new binary tree and returned; all positions elements are still valid, although some of them have a different container after the operation. node can be the root, or an external node.

Parameters:

node - the position above which to make the cut

Returns:

the subtree removed, packaged as a new BinaryTree, with node as its root

Throws:

InvalidAccessorException - if node is null or does not belong to this binary tree.

link

public java.lang.Object link(Position node,
                             BinaryTree newSubtree)
                      throws InvalidAccessorException,
                             InvalidContainerException

Links binary tree newSubtree at external node node by replacing node with the root of newSubtree. As a result of this method, the positions of newSubtree become positions of this binary tree and newSubtree becomes a binary tree with a single node storing null.

Parameters:

node - the external node to replace with the new subtree

newSubtree - the subtree to link in

Returns:

the element of the external position that was removed

Throws:

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

replaceSubtree

public BinaryTree replaceSubtree(Position subtreeRoot,
                                 BinaryTree newSubtree)
                          throws InvalidAccessorException,
                                 InvalidContainerException

Swaps a subtree of this binary tree with a binary tree passed in. In the extremes, the subtree of this binary tree might be the entire tree, or might be just a leaf. subtreeRoot specifies a subtree of this binary tree. That subtree is removed from this binary tree, and newSubtree is linked in in its place. A new binary tree, whose root is the position subtreeRoot, is returned to the user (this binary tree has all the positions of the removed subtree). Note that this binary tree is one of three binary trees involved in the method. The other two are the newSubtree passed in, which becomes an empty tree when the method finishes; and the tree returned, which is a brand new BinaryTree holding the subtreeRoot, and all its children, which were removed from this binary tree. Note that link(.) and cut(.) can both be implemented in terms of this method. newSubtree must be of the same class as this binary tree, or perhaps otherwise node-compatible with this binary tree.

Parameters:

subtreeRoot - any position in this binary tree

newSubtree - the binary tree that will replace the binary tree rooted at subtreeRoot

Returns:

a new binary tree, with subtreeRoot as its root

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

graftOnLeft

public void graftOnLeft(Position subtreeRoot,
                        java.lang.Object eltOfParent,
                        BinaryTree newSubtree)
                 throws InvalidAccessorException,
                        InvalidContainerException

Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the right child of a new node storing the given element. The root of newSubtree, with all its children, is linked in as the left child of the new node, with all the positions and elements unchanged. newSubtree becomes empty.

Parameters:

newSubtree - the binary tree whose root will be linked in as the left child of the new node

eltOfParent - the object to be stored in the new node

subtreeRoot - any position in this binary tree

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

graftOnRight

public void graftOnRight(Position subtreeRoot,
                         java.lang.Object eltOfParent,
                         BinaryTree newSubtree)
                  throws InvalidAccessorException,
                         InvalidContainerException

Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the left child of a new node, storing the given element. The root of newSubtree, with all its children, is linked in as the right child of the new node, with all the positions and elements unchanged. newSubtree becomes empty.

Parameters:

subtreeRoot - any position in this binary tree

eltOfParent - the object to be stored in the new node

newSubtree - the binary tree whose root will be linked in as the right child of the new node

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.