Lecture 8 - Our Specification Of Binary Tree - Introduction

3.1. Our Specification Of Binary Tree - Introduction

Refer to handout.
Our specification of binary tree has a great deal in common with our specification of lists. The main two operations are JOINing two trees and SPLITting a tree (this operation is called pruning, for reasons that will be explained in a moment). We could have specified trees by generalizing our specification of lists to allow each element to have more than 1 successor. This is an interesting exercise, I recommend that you try it. We have not done that because I wanted you to see a few different alternatives: for example, we have not included an INSERT operation on trees (we could easily have done so) - instead we have provided a CREATE_SINGLETON operation that turns a value into a 1-element tree which can then be JOINed to a larger tree (so there is no need for INSERT).

The most distinctive aspect of our specification is its notion of ``subtree''. Recall the lecture in which we discussed the problems that would arise if we allowed lists to share nodes. The specific example we considered, was, when we JOIN(L1,L2), what should happen to L2? We saw that it was very awkward to allow L2 to be part of L1, and sketched out several alternative solutions to this problem. For lists, the solution we adopted was to insist that there would never be any sharing of nodes by two lists - following this policy, we specified that JOIN(L1,L2) would `destroy' L2.

One of the other solutions that we described at the time took exactly the opposite approach. We allow L1 and L2 to share nodes, but, if L2 is a sublist of L1 (as it would be after JOIN(L1,L2)) we mark it as a sublist, and we specify preconditions on certain operations that prevent them from being applied to sublists. For instance, after JOIN(L1,L2), L1 is still a list, not a sublist, but L2 has changed from being a list to being a sublist. JOIN is restricted: its second argument (and perhaps the first as well) must be a list, it cannot be a sublist.

The very same problem arises with trees, and all the solutions we discussed for lists apply equally well for trees. We could adopt the same policy for trees as we did for lists, but we will take this opportunity to experiment with an alternative solution. We will allow one tree to be a subtree of another (i.e. for all the nodes of one to be in another), but it will be clearly marked as a subtree, and some operations will have preconditions saying that a parameter T must, or must not, be a subtree.

Subtrees give us the same ability to inspect and `move around' a tree that windows gave us for lists, so there is no need for a separate type corresponding to window. Instead we will simply have operations to look at the root node of a tree or subtree, and to `get' its left or right subtree, or its parent tree.

Note that my choice of having an INSERT operation for lists but a CREATE_SINGLETON operation for trees, and of having windows for lists but subtrees for trees - these decisions were entirely arbitrary, you could equally well have done it the other way around.