Each binary tree entry stores its word, positive frequency, and two child references:A
class Tree(val word: String, var count: Int,
var left: Tree = null, var right: Tree = null)null reference denotes an empty subtree. A word is a non-null string data type value; its order below is the fixed lexicographic order used by String.compareTo.The representation invariant says that
root is either null or the root of a finite, acyclic binary search tree, with no software object shared between different child subtrees. Every reachable entry has a non-null word and a strictly positive frequency. For each entry , every word in its entire left subtree is strictly less than t.word, and every word in its entire right subtree is strictly greater. This is an inherited ordering condition on all descendants, rather than merely a comparison with immediate children. It implies that each distinct word has exactly one entry. The empty initial state satisfies it.The abstraction function is the finite multiset assigning each stored word its positive count and assigning all other words zero. Frequencies and their increments must fit in
Int; the implementation below explicitly rejects an increment at its representational limit instead of silently violating positivity through integer overflow.Return the new root of the affected subtree, assigning that result back to the parent's child reference:Assume the input binary search tree satisfies part (b)'s representation invariant and, if the key already occurs, its count can be incremented. Structural induction proves the postcondition. For an empty subtree, the fresh entry represents one occurrence. Otherwise the word comparison identifies the only possible child subtree containing the word. The recursive call adds exactly one occurrence there, preserving the inherited strict bounds; in the equal case only the count changes. The number of entries in the current subtree strictly decreases in each recursive call, proving algorithm termination. The returned binary search tree represents the old multiset plus one occurrence of
def addToTree(word: String, t: Tree): Tree = {
require(word != null)
if (t == null) new Tree(word, 1)
else {
val c = word.compareTo(t.word)
if (c < 0) t.left = addToTree(word, t.left)
else if (c > 0) t.right = addToTree(word, t.right)
else {
require(t.count < Int.MaxValue)
t.count += 1
}
t
}
}
// Updating the whole structure uses: root = addToTree(word, root)word. With height , at most comparisons are made; without balancing this can be linear in the number of words. Actual comparison work also depends on the compared string data type lengths.start == null if and only if end == null. Otherwise there is a finite list of distinct software objects , with start eq v0, end eq v(m-1), v0.left == null, and v(m-1).right == null. For every valid adjacent pair, v(i).right eq v(i+1) and v(i+1).left eq v(i). These are exactly the entries reachable through the list links, so there is no extra cycle or branch. All counts are positive, all words are non-null, and words strictly increase from start to end.This is the representation invariant for a null-terminated doubly linked list without a list header. The abstraction function reads the ordered word-count pairs from left to right. Conversion additionally requires the output entries, counts and words to be precisely those of the input binary search tree; that preservation property is an operation postcondition, rather than an invariant of an arbitrary list by itself.
Perform a destructive binary search tree flattening by converting both child subtrees and splicing their endpoints around the original root:Save the child references before changing their interpretation. The input is a finite binary search tree satisfying part (b), and no external client may simultaneously rely on the old tree links. By structural induction, the two recursive calls return disjoint, ordered doubly linked lists containing exactly their original entries. The binary search tree bounds place every left word before
def flatten(t: Tree): (Tree, Tree) = {
if (t == null) (null, null)
else {
val oldLeft = t.left
val oldRight = t.right
val (ls, le) = flatten(oldLeft)
val (rs, re) = flatten(oldRight)
t.left = le
if (le != null) le.right = t
t.right = rs
if (rs != null) rs.left = t
val start = if (ls == null) t else ls
val end = if (re == null) t else re
(start, end)
}
}t.word and every right word after it. Splicing the left end, t, and the right start therefore preserves strict order and reciprocal links. A missing left list makes t.left null and t the start; a missing right list similarly makes t the end. The resulting outside links are null as required by part (i).The recursive loop variant analogue is the strictly smaller number of entries in each child subtree. Every entry is processed once and incurs a constant number of link writes, so time complexity is and recursion uses auxiliary space. No new
Tree entry is created; returning endpoint tuples and using a call stack are permitted auxiliary storage. The old binary search tree representation is consumed by this operation.Replace suspended recursive calls by an explicit stack for an inorder traversal. Save each original right child before overwriting that link:The method belongs to the concrete class owning
def flattenIterative(): (Tree, Tree) = {
val pending = new scala.collection.mutable.Stack[Tree]
var current = root
var start: Tree = null
var end: Tree = null
while (current != null || pending.nonEmpty) {
while (current != null) {
pending.push(current)
current = current.left
}
val t = pending.pop()
val nextSubtree = t.right
t.left = end
if (end == null) start = t else end.right = t
t.right = null
end = t
current = nextSubtree
}
root = null
(start, end)
}root. Clearing root records that ownership has transferred to the returned doubly linked list; callers retain both returned endpoints. The inner loop invariant says that the current subtree lies before all its pending ancestors in inorder traversal; pushing and descending left preserves this fact. Its loop variant is the number of entries along the remaining left-child path, a finite decreasing quantity.The outer loop invariant says that
start through end is precisely the already emitted sorted prefix, with reciprocal links and null outside endpoints. current and the pending ancestors describe exactly the remaining traversal in order; original links that are still needed have been retained. A pending ancestor has not yet had its right child overwritten. The next popped entry is therefore the next sorted entry. Saving nextSubtree preserves its future work before assigning t.right = null; linking it to end extends the prefix by exactly one entry. The number of original entries not yet emitted is an outer loop variant, since each full outer iteration emits one. At exit nothing remains, proving the same preservation and ordering postconditions as the recursive version.Each entry is pushed and popped once, giving time complexity and auxiliary space. No new
Tree entries are allocated. The historical mutable stack interface provides the push and pop operations used here; its later deprecation does not change their meaning.[ref] Articles by others on the same topic
There are currently no matching articles.