= Solution
Return the new root of the affected <subtree>, assigning that result back to the parent's child reference:
``
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)
``
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>. \b[The returned <binary search tree> represents the old <multiset> plus one occurrence of `word`.] With height $h$, at most $h+1$ 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.
Back to article page
