Package components.binarytree

Class BinaryTreeSecondary<T>

java.lang.Object

components.binarytree.BinaryTreeSecondary<T>

Type Parameters:

T - type of BinaryTree labels

All Implemented Interfaces:

BinaryTree<T>, BinaryTreeKernel<T>, Standard<BinaryTree<T>>, Iterable<T>

Direct Known Subclasses:

BinaryTree1

public abstract class BinaryTreeSecondary<T>
extends Object
implements BinaryTree<T>

Layered implementations of secondary methods for BinaryTree.

Execution-time performance of all methods implemented in this class is O(1).

While a trivial implementation of inOrderAssemble could simply call assemble, the preferred implementation here does an AVL-tree rotation if necessary, so that if left and right are AVL trees that differ in height by no more than 2, then the resulting tree is an AVL tree. This provides a very simple way of getting balanced trees where recursive client code maintains an invariant that depends only on the in-order traversal string: simply replace every call to assemble by an otherwise identical call to inOrderAssemble in all client code that incrementally updates a binary tree to maintain this invariant. For example, this works for a binary tree used as a binary search tree, and when the in-order traversal of a binary tree is intended to be directly interpreted as a string (as in a representation of a Sequence).

Constructor Summary

Constructors

Constructor	Description
BinaryTreeSecondary()

Method Summary

Modifier and Type	Method	Description
final boolean	equals(Object obj)
int	hashCode()
int	height()	Reports the height of this.
void	inOrderAssemble(T root, BinaryTree<T> left, BinaryTree<T> right)	Assembles in this a tree that has the same in-order traversal as a tree with root label root and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this.
T	replaceRoot(T x)	Replaces the root of this with x, and returns the old root.
T	root()	Reports the root of this.
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface components.binarytree.BinaryTreeKernel

assemble, disassemble, size

Methods inherited from interface java.lang.Iterable

forEach, iterator, spliterator

Methods inherited from interface components.standard.Standard

clear, newInstance, transferFrom

Constructor Details

BinaryTreeSecondary

public BinaryTreeSecondary()

Method Details

equals

public final boolean equals(Object obj)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object

root

public T root()

Description copied from interface: BinaryTree

Reports the root of this.

Specified by:

root in interface BinaryTree<T>

Returns:

the root entry of this

replaceRoot

public T replaceRoot(T x)

Description copied from interface: BinaryTree

Replaces the root of this with x, and returns the old root.

Specified by:

replaceRoot in interface BinaryTree<T>

Parameters:

x - the new root

Returns:

the old root

height

public int height()

Description copied from interface: BinaryTree

Reports the height of this.

Specified by:

height in interface BinaryTree<T>

Returns:

the height

inOrderAssemble

public void inOrderAssemble(T root,
 BinaryTree<T> left,
 BinaryTree<T> right)

Description copied from interface: BinaryTree

Assembles in this a tree that has the same in-order traversal as a tree with root label root and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this.

Specified by:

inOrderAssemble in interface BinaryTree<T>

Parameters:

root - the root label

left - the left subtree

right - the right subtree