So far, we have developed the data structure of a binary tree as a hierarchical structure recursively defined as follows: a binary tree is either
Like with trees, we can define operations over trees by mirroring this structure.
binary-tree-sizeIn a prior lab, we explored some basic recursive operations over trees. Let’s revisit them, but this time with an eye towards generalized patterns.
Our basic example of tree recursion was computing the size of the tree, i.e., the number of values it contains. We can define the size operation recursively by case analysis on the structure of the tree:
We can then translate this recursive algorithm into code:
(define binary-tree-size
(lambda (t)
(if (empty-tree? t)
0
(+ 1
(binary-tree-size (btl tree))
(binary-tree-size (btr tree))))))
And here is an example run of tree-size on a sample tree using the tree-creation helper functions we wrote in the previous reading.
;;; Encodes the following tree:
;;; 5
;;; / \
;;; 3 7
;;; / \ \
;;; 1 4 9
;;; /
;;; 8
(define example-tree
(binary-tree 5
(binary-tree 3
(leaf 1)
(leaf 4))
(binary-tree 7
empty-tree
(binary-tree 9
(leaf 8)
empty-tree))))
> example-tree
'(5 (3 (1 _ _) (4 _ _)) (7 _ (9 (8 _ _) _)))
> (tree-size example-tree)
7
Here is the step-by-step evaluation of the function.
Note the order of evaluation between the left and right branches of each sub-tree.
For concision, we’re using size rather than binary-tree-size.
And we’ve underlined the part of the expression we’re evaluating with x’s.
(size example-tree)
xxxxxxxxxxxx
--> (size '(5 (3 ...) (7 ...)))
xxxxxxxxxxxxxxxxxxxxxxxxxxx
--> (+ 1 (size '(3 ...)) (size '(7 ...)))
xxxxxxxxxxxxxxx
--> (+ 1 (+ 1 (size '(1 _ _)) (size '(4 _ _))) (size '(7 ...)))
xxxxxxxxxxxxxxx
--> (+ 1 (+ 1 (+ 1 (size '_) (size '_)) (size '(4 _ _))) (size '(7 ...)))
xxxxxxxxx
--> (+ 1 (+ 1 (+ 1 0 (size '_)) (size '(4 _ _))) (size '(7 ...)))
xxxxxxxxx
--> (+ 1 (+ 1 (+ 1 0 0) (size '(4 _ _))) (size '(7 ...)))
xxxxxxxxx
--> (+ 1 (+ 1 1 (size '(4 _ _))) (size '(7 ...)))
xxxxxxxxxxxxxxx
--> (+ 1 (+ 1 1 (+ 1 (size '_) (size '_))) (size '(7 ...)))
xxxxxxxxx xxxxxxxxx
--> (+ 1 (+ 1 1 (+ 1 0 0)) (size '(7 ...)))
xxxxxxxxx
--> (+ 1 (+ 1 1 1) (size '(7 ...)))
xxxxxxxxx
--> (+ 1 3 (size '(7 _ (9 ...))))
xxxxxxxxxxxxxxxxxxx
--> (+ 1 3 (+ 1 (size ' _) (size '(9 ...))))
xxxxxxxxxx
--> (+ 1 3 (+ 1 0 (size '(9 (8 ...) _))))
xxxxxxxxxxxxxxxxxxxx
--> (+ 1 3 (+ 1 0 (+ 1 (size '(8 _ _)) (size '_))))
xxxxxxxxxxxxxx ; Skipping a few steps
--> (+ 1 3 (+ 1 0 (+ 1 1 (size '_))))
xxxxxxxxx
--> (+ 1 3 (+ 1 0 (+ 1 1 0)))
xxxxxxxxx
--> (+ 1 3 (+ 1 0 2))
xxxxxxxxx
--> (+ 1 3 3)
xxxxxxxxx
--> 7
As you should recall from our initial explorations of recursion, there is a traditional pattern for recursion over lists:
(define recursive-proc
(lambda (lst)
(if (null? lst)
(base-case)
(combine (car lst)
(recursive-proc (cdr lst) other)))))
We chose this pattern because of the common definition of a list. Because a list is either (a) null or (b) the cons of a value and a list we have two cases: one for when the list is null and one for the cons case. Since the cdr of a list is itself a list, in makes sense to recurse on the cdr.
A binary tree, in comparison, is either the (a) empty tree or (b) a combination of a value and two subtrees. If it’s Hence, we will need to recurse on both halves, as well as look at the value in the node.
(define binary-tree-proc
(lambda (tree)
(if (empty-tree? tree)
(base-case other)
(combine (process (btt tree))
(binary-tree-proc (btl tree))
(binary-tree-proc (btr tree))))))
For the binary-tree-size above,
combine procedure is +process the top value by using 1We can also use this pattern to find the depth of a tree, the number of
levels in the tree.
(define binary-tree-depth
(lambda (tree)
(if (empty-tree? tree)
0
(+ 1 (max (binary-tree-depth (btl tree))
(binary-tree-depth (btr tree)))))))
The combine here is slightly more subtle. We have to find a max and then add
1, rather than combining the values directly. And we throw away the top value,
since it has no relevance.
If we have a tree of numbers, we can sum them using a similar pattern.
(define binary-tree-sum
(lambda (tree)
(if (empty-tree? tree)
0
(+ (btt tree)
(binary-tree-sum (btl tree))
(binary-tree-sum (btr tree))))))
Are you sick of the pattern yet? I know I am. So let’s move on.
We can use a variant of this pattern to search the tree for a value.
;;; (binary-tree-contains? tree val) -> boolean?
;;; tree : binary-tree?
;;; val : any?
;;; Determine if the tree contains a specific value
(define binary-tree-contains?
(lambda (tree val)
(cond
; The empty tree contains no values
[(empty-tree? tree)
#f]
; If the value is at the top, the tree contains the value
[(equal? (btt tree) val)
#t]
; If the left subtree contains the value, the tree contains the value
[(binary-tree-contains? (btl tree) val)
#t]
; If the right subtree contains the value, the tree contains the value
[(binary-tree-contains? (btr tree) val)
#t]
; If none of these cases hold, the tree does not contain the value
[else
#f])))
While this looks quite different from the earlier pattern, it has a similar
concept. Once again, we have a base case when the tree is empty. In this
ase, the base case is “the value is not there”, or #f. We’re also combining
information from the top, the left subtree, and the right subtree. In particular,
we’re considering whether the value appears in any of those three places.
It’s just more convenient to express it as a cond.
In fact, it there may be even better ways to express it. The Zen of Booleans encourages us to think about other ways to write things when we’re writing a lot of explicit Boolean values. Can we do better? Here’s one option.
(define binary-tree-contains?
(lambda (tree val)
(and (not (empty-tree? tree))
(or (equal? (contents tree) val)
(binary-tree-contains? (left tree) val)
(binary-tree-contains? (right tree) val)))))
Isn’t that nicely concise?
Important! You will note that in all of these cases, we use direct recursion rather than tail recursion (or even accumulator recursion). That’s because it’s very difficult to express recursion on both subtrees using anything other than direct recursion.
Computer scientists have found a wide variety of applications of binary trees and more general trees. As we suggested at the beginning of the reading, a general tree can provide a way to represent the hierarchy of positions at the organization. At the top of the tree we have the President or CEO. Beneath the President are the Vice Presidents. Beneath each Vice President are Deans or Directors. And so on or so forth.
However, there’s little you can do with a tree representing a hierarchy than try to find where someone belongs in the hierarchy. Hence, we use trees for a variety of other applications.
As its name suggests, a decision tree represents a series of decisions, such as yes/no questions. We might have the left branch correspond to a “yes” answer and the right branch correspond to a “no” answer. Here is a text-based decision tree to help students select a course.
Have you taken a course in computer science?
N: Are you interested in learning to program?
N: We recommend that you take CSC 105, in which you consider social issues in computing.
Y: We recommend that you take CSC 151, in which you consider both programming issues and more general social issues.
Y: Did you take CSC 151 or an equivalent course?
N: Did you enjoy the course?
N: We recommend that you take CSC 151; it presents a different view you might enjoy.
Y: We recommend that you take CSC 151. You'll learn new things.
Y: We recommend that you talk to a faculty member.
We also use forms of binary trees called binary search trees. In binary search trees, everything in the left subtree is smaller than the root (in a tree of strings, everything in the left subtree comes alphabetically before the root) and everything in the right subtree is larger than the root (in a tree of strings, everything in the right subtree comes alphabetically after the root).
The tree-contains? procedure that we just saw looks everywhere in a
tree for a value. But we noted in the prior section that a tree can
be arranged so that smaller things are to the left and larger things
are to the right. In that case, we only need to look on one side.
Here’s a simple implementation of such a procedure for trees of
strings.
;;; (bst-find bst str) -> boolean?
;;; bst : treeof string?
;;; str : string
;;; Look for a string in a binary searh tree of string
;;; When we say that bst is a binary search tree, we mean it is a binary
;;; tree with the property that the left subtree contains smaller values
;;; the right subtree contains larger values, and the subtrees are both
;;; binary search trees.
(define bst-find
(lambda (bst str)
(if (empty-tree? bst)
#f
(let ([root (btt bst)])
(cond
; If we find the value at the root, we're done
[(string-ci=? str root)
root]
; If the value is less than the root, we should look in the
; left subtree. (And don't need the right subtree.)
[(string-ci<? str root)
(bst-find (btl bst) str)]
; Otherwise, the value is greater than the root. We should
; look in the right subtree. (And it can't be in the left
; subtree.)
[else
(bst-find (btr bst) str)])))))
How does this work in practice? You’ll trace it in a self-check.
Many of the binary-tree procedures we’ve used need to look at both subtrees of the tree. When we print a tree, we print both subtrees. When we compute the size of the tree, we compute the size of each subtree. When we compute the depth of the tree, we compute the depth of each subtree. And when we sum the values in a tree, we sum both subtrees.
But we’ve also seen some tree recursion in which we only look at one subtree
or the other. The bt procedure you wrote in an earlier lab only enters
one of the two subtrees. The bst-find procedure only enters one of the
subtrees. The decision-tree example suggests that you only take on path
(that is, the answers are always one of “yes” or “no”, so once we’ve answered
a question, we’ve chosen a subtree).
This second kind of recursion is comparatively powerful. In essence, by choosing one subtree or another, we get to “throw away” half of the tree. That makes tree procedures that use this model relatively fast. How fast? We’ll explore that later. But for now, think about an instance in which we have a tree with 1000 elements. If we look at the top and throw away half, we’re left with 500 (or maybe 499). Throwing away half, we’re left with 250. Then 125. THen 62, 31, 15, 7, 3, 1. Throwing away half the values nine times left us with only one element. That seems much faster than looking at all 1000 elements.
Unfortunately, the “recurse on only half the tree” approach is limited to certain circumstances. But when we can arrange our data to use it, we probably should.
Note the order of the recursive calls to tree-sum.
We recursively call the function first on the left subtree and then the right subtree.
What if we flipped these calls?
Consider this alternative version of binary-tree-sum:
(define sum-binary-tree
(lambda (t)
(if (null? t)
0
(+ (btt t)
(sum-binary-tree (btr t))
(sum-binary-tree (btl t))))))
How does it behave differently from the original tree-sum version?
Justify your answer in terms of the operations that tree-sum ultimately performs on its elements.
Consider the following tree, drawn in lovely ASCII art.
Mongoose
/ \
Iguana Pidgeon
/ / \
Emu Ocelot Yak
\ / \
Gnu Skink Zebra
/
FennecFox
a. Trace (informally) how bst-find finds “Skink”.
(bst-search '("Mongoose" L R) "Skink")
; Skink comes after Mongoose
--> (bst-search '(Pidgeon L R) "Skink")
b. Trace (informally) what happens if we try to find “Hippo” using bst-find.