001package components.binarytree;
002
003import java.util.Iterator;
004
005/**
006 * Layered implementations of secondary methods for {@code BinaryTree}.
007 *
008 * <p>
009 * Execution-time performance of all methods implemented in this class is O(1).
010 *
011 * <p>
012 * While a trivial implementation of {@code inOrderAssemble} could simply call
013 * {@code assemble}, the preferred implementation here does an AVL-tree rotation
014 * if necessary, so that if {@code left} and {@code right} are AVL trees that
015 * differ in height by no more than 2, then the resulting tree is an AVL tree.
016 * This provides a very simple way of getting balanced trees where
017 * <i>recursive</i> client code maintains an invariant that depends only on the
018 * in-order traversal string: simply replace every call to {@code assemble} by
019 * an otherwise identical call to {@code inOrderAssemble} in all client code
020 * that <i>incrementally</i> updates a binary tree to maintain this invariant.
021 * For example, this works for a binary tree used as a binary search tree, and
022 * when the in-order traversal of a binary tree is intended to be directly
023 * interpreted as a string (as in a representation of a {@code Sequence}).
024 *
025 * @param <T>
026 *            type of BinaryTree labels
027 */
028public abstract class BinaryTreeSecondary<T> implements BinaryTree<T> {
029
030    /*
031     * 2221/2231 assignment code deleted.
032     */
033
034}