;; My proc for printing trees
(define (print-tree node)
(define (pt-help node depth)
(begin (d-print depth)
(display (datum node))
(newline)
(for-each (lambda (x) (pt-help x (+ depth 1)))
(children node))))
(define (d-print depth)
(if (= depth 0)
(display "o ")
(begin (display " ")
(d-print (- depth 1)))))
(newline)
(pt-help node 0)
(newline))
(define (print-tree node)
(define (pt-help node depth)
(begin (d-print depth)
(display (datum node))
(newline)
(for-each (lambda (x) (pt-help x (+ depth 1)))
(children node))))
(define (d-print depth)
(cond ((= depth 0)
(display "o "))
((= depth 1)
(display "|->o "))
(else
(begin (display "| ")
(d-print (- depth 1))))))
(newline)
(pt-help node 0)
(newline))
;;
;; Recap theta issues
;;
;; Tricks when composing functions:
;; Example:
(define (find x lst) ;; also called 'member?'
(cond ((null? lst) #f)
((= x (first lst)) #t)
(else (find x (cdr lst)))))
(find 1 '(2 3 1 4))
(find 1 '(2 3 11 4))
(define (pairs lst)
(map (lambda (x) (find (+ x 1) lst)) lst))
(pairs '(1 2 3 9 11 12))
;; Orders of growth: find is obviously linear in n.
;; pairs calls map (linear) with a linear function
;; Thus, T(n)*T(n) -> T(n^2)
;; Caveat: Only true since the number of calls to map is
;; not determined by the running time/return value of find!
;; Not always the case:
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
(define (fast-fact n)
(fact (fact n)))
;; Question: what is the order of growth
;; for fast-fact in terms of n?
;; First guess:
;; We know that fact is T(n), so fact(fact(n)) => T(n)*T(n)
;; Close, but not quite! You can compose the running times of
;; composed functions, but __ only if n is constant __!
;; Here, the return value of the inner fact affects the running
;; time of the outer fact.
;; If you try it our, this func obviously grows faster than n^x
(map fast-fact '(1 2 3 4 5 6))
;;
;; Today: another abstract data type -- TREES
;;
;; Real life motivation -- trees are all over:
;; Draw real tree
;; Draw cs tree
;; Draw world tree
;; Draw eval tree
;; +
;; / | \
;; - 3 *
;; / \ /|\
;; 1 2 4 5 6
;; Anything that has this sort of a hierarchical
;; structure can be represented using our tree ADT
;; Terms:
;; Nodes (also called trees or subtrees)
;; Edges
;; Nodes are a ... (Absolute)
;; Root
;; Branch
;; Leaf
;; Nodes have a ... (Relative)
;; Parent
;; Child(ren)
;; Datum -- Value (Name ??)
;; Non-obvious properties of trees:
;; 1. No cycles
;; 2. 1-way Edges
;; 3. Connected
;; 4. Recursively defined:
;; x is a tree iff
;; x is a leaf or all the children
;; of x are trees.
;; 5. Sequences are also trees:
;; '(1 2 3 4) --> (1
;; \
;; 2
;; \
;; 3
;; \
;; 4)
;; Trees are 'more powerful' in the sense
;; that they can have more than one 'child'
;; or 'next' node.
;; 6. k-ary
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Our interface:
;;
;; Constructors:
;; (make-node datum lst-of-children) Theta(1)
;;
;; Selectors:
;; (datum node) Theta(1)
;; (children node) Theta(1)
;;
;; Eval tree from above:
;; +
;; / | \
;; - 3 *
;; / \ /|\
;; 1 2 4 5 6
(define t (make-node + (list (make-node - (list (make-node 1 '())
(make-node 2 '())))
(make-node 3 '())
(make-node * (list (make-node 4 '())
(make-node 5 '())
(make-node 6 '()))))))
(print-tree t)
(datum t)
(children t)
(datum (car (children t)))
;; Watch out! This is wrong:
(define t (make-node + (list (make-node - (list 1
2))
3
(make-node * (list 4
5
6)))))
(datum t)
(children t)
( car (children (car (children t)))) ;; should be a node
(datum (car (children (car (children t))))) ;; should be 1
;;;;;;;;;;;;;;;;;;;;;;; Peer instruction?
;;
;; --> Is our use of 'car' here an abstraction
;; violation? Should we have selectors called
;; first-child and rest-children?
;; Exam: Open notes/open book
;; Wks 1 and 2
;; No nested lists!
;; Some groupwork -- group of 4
;;
;; Only 1 copy of HWs/Proj
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Searching
;; Guess a number from 1 to 1000.
;; Slow way: is it 1?, is it 2?, is it 3?
;; Think of this as list-based.
;; Fast way: I'll tell you higher/lower
;; is it 500? is it 250? is it 125?
;; Your guesses make a tree:
;; 500
;; / \
;; 250 750
;; / \ / \
;; 125 380 525 875
;; / \
;; 62 ... ... ...
;; You come to an answer faster because you are
;; exploiting the heirarchical nature of these
;; numbers. At each step, you cut the size of your
;; problem in half. (Compare lists ...)
;; So common, its given a name: BST
;; Making your own BST:
;; Insert --> Easy ( log(n) )
;; Find --> Easy ( log(n) )
;; Remove --> Hard!
;;
;; Tuesday
;;
4-6 Greg 310 Soda
6-8 Jane 310 Soda
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Efficiency of trees:
;;
;; How long does it take to find something in
;; a list --> linear time
;;
;;
;;
;; How long in a tree? Well, if the tree provides
;; information on the next node --> log base 2 time!
;; (Since it cuts the number of things that you
;; want to look for in half at each step.)
;;
;;
;;
;;
;; This applies for a binary tree, but running times
;; change with the k-ary-ness of the tree!
;; A trinary (3-way) tree cuts the problem in thirds
;; at each step. So, running time log base 3.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Traversing trees
;;
;; In what order to we look at things in trees:
;;
;;
;;
;; Breadth-First:
;; For a given node, look at it, then its siblings,
;; then its children.
;; Depth-First:
;; For a given node, look at children before siblings
;; Three subchoices:
;; 1. Pre-order: look at node, then children, then sibs
;; 2. Post-order: look at children, then node, then sibs
;; 3. In-order: look at first child, then node, then second
;; child, then sibs. Only works if you know how to 'splice'
;; the node into the list of children.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Why no standard tree representation?
;; Trees are very complex --> different trees for
;; different applications will have different properties
;; o empty trees allowed?
;; o children stored in order?
;; o empty datum or not?
;; o etc.
;;
;;
;;
;; Our tree ADT is a good compromise in that it captures
;; almost everthing that we want about trees and nothing
;; that we don't.
;;
;; Feel free to make your own if you have some sort of
;; hierarchical data that does fit well into our
;; abstraction -- see examples in ~/lectures/2.2/
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Interface implementation
;;
;; Design decisions:
;; o Branch nodes have useful data (ones in SICP don't)
;; o k-ary (arbitrary number of children)
;; o Branch order matters
;; o No empty trees
(define make-tree cons)
(define datum car)
(define children cdr)
;; +
;; / | \
;; - 3 *
;; / \ /|\
;; 1 2 4 5 6
(define t (make-node + (list (make-node - (list (make-node 1 '())
(make-node 2 '())))
(make-node 3 '())
(make-node * (list (make-node 4 '())
(make-node 5 '())
(make-node 6 '()))))))
(datum t)
(children t)
(datum (car (children t)))
;; Other useful procs:
(define (leaf? node)
(null? (children node)))
(define (make-leaf datum)
(make-node datum '()))
;; +
;; / | \
;; - 3 *
;; / \ /|\
;; 1 2 4 5 6
(define t (make-node + (list (make-node - (list (make-leaf 1)
(make-leaf 2)))
(make-leaf 3)
(make-node * (list (make-leaf 4)
(make-leaf 5)
(make-leaf 6))))))
(datum t)
(children t)
(datum (car (children t)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Operating on trees
;;
;; Given a tree of numbers, square every element
;; Here's the list version
(define square (lambda (x) (* x x)))
(define (square-list lst)
(if (empty? lst)
(list)
(cons (square (car lst))
(square-list (cdr lst)))))
(square-list '(1 2 3))
;; Here's our first version:
(define (square-tree node)
(make-node (square (datum node))
(sq-tree-helper (children node))))
(define (sq-tree-helper lst-of-nodes) ;; called a forest!
(if (empty? lst-of-nodes)
(list)
(cons (square-tree (car lst-of-nodes))
(sq-tree-helper (cdr lst-of-nodes))))))
;; Test it out
(define t1 (make-node 1 (list (make-node 2 (list (make-leaf 3)))
(make-leaf 4))))
(print-tree t1)
(define t1-squared (square-tree t1))
(print-tree t1-squared)
;; First version is way too complicated. Let's simplify:
(define (square-tree node)
(make-node (square (datum node))
(sq-tree-helper (children node))))
(define (sq-tree-helper lst-of-nodes) ;; called a forest!
(map square-tree lst-of-nodes))
(print-tree t1)
(define t1-squared (square-tree t1))
(print-tree t1-squared)
;; Better, but still 1 more improvement:
(define (square-tree node)
(make-node (square (datum node))
(map square-tree (children node))))
(print-tree t1)
(define t1-squared (square-tree t1))
(print-tree t1-squared)
;;
;; Recursive, but no explicit base case!!
;;
;; How does it work?
;; There are two recursions here:
;; The downward:
;; Recurse down the tree and stop when
;; you run into a leaf node
;; The 'across':
;; Recurse across the list of children
;; and stop at the end.
;; Map is doing both of them!
(trace map)
(trace square-tree)
(square-tree t1)
;;.. -> square-tree with node = (1 (2 (3)) (4))
;;.. -> map with args = (#[closure arglist=l 1ed530] ((2 (3)) (4)))
;;.... -> square-tree with node = (2 (3))
;;.... -> map with args = (#[closure arglist=l 1ed530] ((3)))
;;...... -> square-tree with node = (3) +++
;;...... -> map with args = (#[closure arglist=l 1ed530] ()) ***
;;...... <- map returns ()
;;...... <- square-tree returns (9) ===
;; +++ Square-tree of a leaf:
;; *** map square-tree of an empty children)
;; === return value : leaf with datum squared!
(untrace map)
(untrace square-tree)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Finding the Pattern:
;;
;; This pattern of applying a func to all the
;; data of a tree is sufficiently common to
;; merit its own HOP. Write tree-map as follows:
;;
;; (define (tree-map func node) ...)
;;
;; (tree-map square t1)
(define (tree-map func node)
(make-node (func (datum node))
(map (lambda (x) (tree-map func x))
(children node))))
(print-tree t1)
(define t1-squared (tree-map square t1))
(print-tree t1-squared)