src/sicp/ex2_64.rkt

   1 #lang racket
   2
   3 (require "ch2_3_3_sets_as_trees.rkt")
   4 (require racket/trace)
   5
   6 (define (list->tree elements)
   7   (car (partial-tree elements (length elements))))
   8
   9 (define (partial-tree elts n)
  10   (if (= n 0)
  11       (cons '() elts)
  12       (let ((left-size (quotient (- n 1) 2)))
  13         (let ((left-results (partial-tree elts left-size)))
  14           (let ((left-tree (car left-results))
  15                 (non-left-elements (cdr left-results))
  16                 (right-size (- n (+ left-size 1))))
  17             (let ((this (car non-left-elements))
  18                   (right-results (partial-tree (cdr non-left-elements) right-size)))
  19               (let ((right-tree (car right-results))
  20                     (remaining-elts (cdr right-results)))
  21                 (cons (make-tree this left-tree right-tree)
  22                       remaining-elts))))))))
  23
  24 ;;(trace list->tree)
  25 ;;(trace partial-tree)
  26
  27 (provide list->tree)
  28
  29 ;; a
  30 #|
  31 Let us take an example:
  32
  33   (list->tree '(1 3 5 7 9 11))
  34
  35 We do
  36 (partial-tree '(1 3 5 7 9 11) 6)
  37   => (partial-tree '(1 3 5 7 9 11) 2)
  38     => (partial-tree '(1 3 5 7 9 11) 0)
  39
  40 At this point, we have found a leaf node. So, we push the null list,
  41 take the first element on the list as the parent and look for the
  42 right tree. The call returns to the previous call to partial-tree
  43 (i.e. (partial-tree '(1 3 5 7 9 11) 2)) which means n is 2.
  44
  45 The right-size = (- n (+ left-size 1)) => (- 2 (+ 0 1)) => 1
  46 So we invoke partial-tree for the right tree.
  47
  48 (partial-tree '(3 5 7 9 11) 1)
  49   => (partial-tree '(3 5 7 9 11) 0)
  50
  51 This will push an empty list (as the left node) and look for right node.
  52 (partial-tree '(5 7 9 11) 0)
  53
  54 this gives us the subtree (1 () (3 () ()))
  55
  56 At every stage of making a subtree, we cons it with the remaining elements.
  57 The tree looks like this:
  58
  59                5
  60               / \
  61              /   \
  62             1     9
  63            / \    /\
  64           /   \  7  11
  65         ()     3
  66               / \
  67              /   \
  68             ()   ()
  69
  70 part b. For each node, we do a cons of the tree under the node with the remaining
  71 elements. So the order of growth is O(n).
  72
  73 |#
  74
  75