All Packages  Class Hierarchy  This Package  Previous  Next  Index

Interface jdsl.core.api.BinaryTree

public interface BinaryTree
extends InspectableBinaryTree
Interface for a binary tree that can be modified. Note that binary trees are specified to start with a single external node with a null element, so no generic insert(.) method is needed here; every conceivable binary tree (except one with no nodes at all) can be built up from the methods of this interface. In addition, because the splice methods (link and replaceSubtree) invalidate containers. Any class implementing BinaryTree must throw an InvalidContainerException from all methods if the container has been invalidated.

Version:
$Revision: 1.2 $, $Date: 1998/06/29 21:10:40 $
Author:
Mark Handy, Mike Boilen (mgb)

Method Index

o cut(Position)
Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element.
o expandExternal(Position)
The external position specified is transformed into an internal, and it gains two children.
o link(Position, BinaryTree)
Position mustBeExternal is removed from the tree.
o removeAboveExternal(Position)
The parent of Position mustBeExternal is deleted, and the sibling subtree of mustBeExternal takes the parent's place as the left/right child of the parent's parent.
o replaceSubtree(Position, BinaryTree)
Swaps a subtree of the tree on which the method is called with a "subtree" passed in.

Methods

o expandExternal 
 public abstract void expandExternal(Position mustBeExternal) throws InvalidPositionException, InvalidContainerException
The external position specified is transformed into an internal, and it gains two children. The position reference itself doesn't change, and its element also doesn't change. The elements of its two new, external children are both null objects.

Parameters:
mustBeExternal - A position which must be an external position in the BinaryTree
Throws: InvalidPositionException
Thrown, in addition to the usual circumstances, when mustBeExternal is internal.
Throws: InvalidContainerException
if this container has been invalidated.
o removeAboveExternal 
 public abstract void removeAboveExternal(Position mustBeExternal) throws InvalidPositionException, BoundaryViolationException, InvalidContainerException
The parent of Position mustBeExternal is deleted, and the sibling subtree of mustBeExternal takes the parent's place as the left/right child of the parent's parent. The external position specified is also deleted.

Parameters:
mustBeExternal - A position which must be an external position in the BinaryTree
Throws: BoundaryViolationException
When the position specified is an external position, as required, but also the root
Throws: InvalidPositionException
In addition to the usual invalid-position possibilities, this is thrown when the position specified is not external
Throws: InvalidContainerException
if this container has been invalidated.
o cut 
 public abstract BinaryTree cut(Position subtreeRoot) throws InvalidPositionException, InvalidContainerException
Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element. They are packaged in a new binary tree and returned; all positions and elements are still valid, although some of them have a different container after the operation.

Parameters:
subtreeRoot - The position above which to make the cut
Returns:
The subtree removed, packaged as a new BT, with subtreeRoot as its root
Throws: InvalidPositionException
if subtreeRoot is of a type not accepted by this container or null.
Throws: InvalidContainerException
if this container has been invalidated.
o link 
 public abstract void link(Position mustBeExternal,
                           BinaryTree newSubtree) throws InvalidPositionException, InvalidContainerException, InvalidArgumentException
Position mustBeExternal is removed from the tree. The root of newSubtree, with all its children, is installed in its place, with all their positions and elements unchanged.

Parameters:
mustBeExternal - The external node to replace with the new subtree
newSubtree - The subtree to link in
Throws: InvalidPositionException
if subtreeRoot is of a type not accepted by this container or null.
Throws: InvalidContainerException
if this container has been invalidated.
Throws: InvalidArgumentException
if newSubtree is the same tree that link is called on.
o replaceSubtree 
 public abstract BinaryTree replaceSubtree(Position subtreeRoot,
                                           BinaryTree newSubtree) throws InvalidPositionException, InvalidContainerException, InvalidArgumentException
Swaps a subtree of the tree on which the method is called with a "subtree" passed in. In the extreme, the subtree of the tree on which the method is called might be the entire tree, or might be just a leaf. Position subtreeRoot specifies a subtree of the tree on which this method is called. That subtree is removed from the tree, and newSubtree is linked in in its place. A new tree, whose root is the position subtreeRoot, is returned to the user (this tree corresponds exactly to the removed subtree). Note that a new BinaryTree is created to hold this removed subtree. Note that link(.) and cut(.) can both be implemented in terms of this method.

Parameters:
subtreeRoot - Any position in the BinaryTree on which the method is called
newSubtree - The tree that will replace the tree rooted at subtreeRoot
Returns:
A new BinaryTree, with subtreeRoot as its root
Throws: InvalidPositionException
if subtreeRoot is of a type not accepted by this container or null.
Throws: InvalidContainerException
if this container has been invalidated.
Throws: InvalidArgumentException
if newSubtree is the same 
All Packages  Class Hierarchy  This Package  Previous  Next  Index