6.001 Recitation #7                                        Fall 1997
Prof. Albert R. Meyer                                   T.A.: Anna Chefter

             5-minute-problem #9: Number/Count Labelled Trees
           (posed in Fri, 10/10/97 for presentation Wed, 10/15)

Extend the ordered, number-labelled binary tree structure (discussed
lecture Tue Oct 7 and in SICP, p.156-7) so that each node, in addition to
a number LABEL, also has a positive integer COUNT which equals the total
number of nodes in its subtree -- that is, 1 + the sum of the number of
nodes in its left subtree and its right subtree.  For example:

                            8,13     label,count
                           /    \
                         /        \
                      5,7          13,5
                     /  \          /   \
                   /     \        /      \
                 2,2    7,4    11,2      17,2
                 /      /  \      \       / \
                /      /    \      \     /    \
              1,1    6,2   7.2,1  12,1  14,1  20,1
                     /
                    /
                 6.05,1

Define abstract selectors and constructors for such trees.  Then describe
an implementation of these operations in such a way that the INSERT
procedure already developed for number-labelled works WITHOUT CHANGE for
number/count-labelled trees.

We define Complete binary trees inductively:
a single node is a Complete binary tree of depth 0; if T1 and T2 are
Complete binary trees of depth k, then 

                              .
                             / \
                            /   \
                           T1   T2

is a Complete binary tree of depth k+1.

Describe a sequence of elements whose successive INSERTion into an
initially tree yields a complete binary tree of depth k.

Now describe a sequence of the same length whose INSERTion yields a tree
with the shape:

                         /
                        /
                        \
                         \
                         /
                        /
                        \
                         \
                        .
                        .
                        .

Explain why this second kind of extremely "unbalanced" tree is
exponentially more costly to search or insert into than a Complete tree.

BRIEFLY suggest how number/count-labelled trees could be useful in dealing
with the problem of unbalanced trees.  Keep it simple.  Remember, you have
only FIVE(5) minutes.  (You are NOT expected to look into the extensive
literature about maintaining balanced trees in preparing your
presentation.)


SOLUTION:

We modify the structure of the tree node to hold both the tree entry
and the count of the leaves in the tree. 


       _______     _________     ___________  
  --> | | |  -|-->| left | -|-->| right | \ |
       -------     ---------     -----------
        |
        |   _______ _______ 
	-> | entry | count |
            _______ _______


The tree constructor procedure has to be modified modified:

(define (make-tree entry left right)
  (list (cons entry
	      (+ 1 (count left) (count right)))
	left
	right))

We also need to modify entry selector and add count selector:

(define (entry tree) (caar tree)) 
(define (count tree) (cdar tree))

Note that we do not have modify other selectors and the insert procedure!

We can use this implementation to efficient check if we need to rebalnce the tree:

(define (time-to-rebalance tree factor)
  (or (> (count (right tree)) (* factor (count (left tree))))
      (> (count (left tree))  (* factor (count (right tree))))))