Class 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
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
-
Method Summary
Modifier and TypeMethodDescriptionfinal boolean
int
hashCode()
int
height()
Reports the height ofthis
.void
inOrderAssemble
(T root, BinaryTree<T> left, BinaryTree<T> right) Assembles inthis
a tree that has the same in-order traversal as a tree with root labelroot
and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.replaceRoot
(T x) Replaces the root ofthis
withx
, and returns the old root.root()
Reports the root ofthis
.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
-
hashCode
-
toString
-
root
Description copied from interface:BinaryTree
Reports the root ofthis
.- Specified by:
root
in interfaceBinaryTree<T>
- Returns:
- the root entry of
this
-
replaceRoot
Description copied from interface:BinaryTree
Replaces the root ofthis
withx
, and returns the old root.- Specified by:
replaceRoot
in interfaceBinaryTree<T>
- Parameters:
x
- the new root- Returns:
- the old root
-
height
Description copied from interface:BinaryTree
Reports the height ofthis
.- Specified by:
height
in interfaceBinaryTree<T>
- Returns:
- the height
-
inOrderAssemble
Description copied from interface:BinaryTree
Assembles inthis
a tree that has the same in-order traversal as a tree with root labelroot
and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.- Specified by:
inOrderAssemble
in interfaceBinaryTree<T>
- Parameters:
root
- the root labelleft
- the left subtreeright
- the right subtree
-