Trees, Graphs and SearchSlide 2Revisiting ListsCode that manipulates listsTreesTree Procedurescountleavescountleaves and substitution model – pg. 2countleaves – bigger exampleGeneral operations on treesEven more general operations on treesWhy search?Examples of SearchExamples of searchWeb search and Web spidersSimple searchSimple maintenanceSlide 18Simple maintenance – ordered caseBetter searchSearching a binary treeSlide 22Maintaining a binary treeHierarchical searchSearching the WebA new data structureDirected graph – an ADTSlide 28Slide 29Searching a directed graphDepth first searchBreadth first searchGeneral search frameworkStrategies for creating search seekersCreating a depth-first strategyTracking the depth first seekerCreating a breadth-first strategy??Tracking the breadth first seekerSlide 39Slide 40Dealing with cycles and sharingA better search methodVariations on a search themeSummaryA Breadth-first strategy01/14/19 6.001 SICP 1/43Trees, Graphs and Search •Key themes from previous lectures–Induction for proving code correctness–Data structures can gather information together into abstract units–Code to manipulate data abstractions tends to reflect structure of abstraction01/14/19 6.001 SICP 2/43Trees, Graphs and Search •Key themes from previous lectures–Induction for proving code correctness–Data structures can gather information together into abstract units–Code to manipulate data abstractions tends to reflect structure of abstraction•Exploring the combination of these themes–Trees–Graphs–Algorithms for trees and graphs01/14/19 6.001 SICP 3/43Revisiting Lists•List: sequence of cons pairs, ending in nil–Closed under the action of cons –Closed (except for the empty list) under the action of cdr–Induction shows that all lists satisfy this property01/14/19 6.001 SICP 4/43Code that manipulates lists(define (map proc lst) (if (null? lst) nil (cons (proc (car lst)) (map proc (cdr lst))))(map square ‘(1 2 3 4));Value: (1 4 9 16)Is there anything special about lists of numbers?Type Definition:List<number>more generally (and in more detail)List<C> = Pair<C,List<C>> | nullBase caseInductive case01/14/19 6.001 SICP 5/43Trees•Type Definition:–Tree<C> = List<Tree<C>> | Leaf<C>–Leaf<C> = C•Operations: –leaf?–Examples: countleaves, scaletree246826 84rootchildren or subtrees01/14/19 6.001 SICP 6/43Tree Procedures•A tree is a list; we can use list procedures on them:(define my-tree (list 4 (list 5 7) 2))4 25 7my-tree(countleaves my-tree) ==> 4(length my-tree)==> 301/14/19 6.001 SICP 7/43countleaves•Strategy–base case: count of an empty tree is 0–base case: count of a leaf is 1–recursive strategy: the count of a tree is the sum of the countleaves of each child in the tree.Implementation:(define (countleaves tree) (cond ((null? tree) 0) ;base case ((leaf? tree) 1) ;base case (else ;recursive case (+ (countleaves (car tree)) (countleaves (cdr tree))))))(define (leaf? x) (not (pair? x)))01/14/19 6.001 SICP 8/43countleaves and substitution model – pg. 2(define (countleaves tree) (cond ((null? tree) 0) ;base case ((leaf? tree) 1) ;base case (else ;recursive case (+ (countleaves (car tree)) (countleaves (cdr tree))))))(define (leaf? x) (not (pair? x)))•Example(countleaves (list 5 7))(countleaves )(countleaves (5 7) )(+ (countleaves 5) (countleaves (7) ))(+ 1 (+ (countleaves 7) (countleaves nil)))(+ 1 (+ 1 0))==> 27501/14/19 9/43countleaves – bigger example(define my-tree (list 4 (list 5 7) 2)) (countleaves my-tree)(countleaves (4 (5 7) 2) )(+ (countleaves 4) (countleaves ((5 7) 2) ))==> 4425 7my-tree(cl (4 (5 7) 2))+(cl 4) (cl ((5 7) 2) )+(cl (5 7)) (cl (2))+(cl 2)(cl nil)+(cl 5)(cl (7))+(cl 7)(cl nil)111 01001/14/19 6.001 SICP 10/43General operations on trees(define (tree-map proc tree) (if (null? tree) ‘() (if (leaf? tree) (proc tree) (cons (tree-map proc (car tree)) (tree-map proc (cdr tree))))))Induction still holds for this kind of procedure!01/14/19 6.001 SICP 11/43Even more general operations on trees(define (tree-manip leaf-op init merge tree) (if (null? tree) init (if (leaf? Tree) (leaf-op tree) (merge (tree-manip leaf-op init merge (car tree)) (tree-manip leaf-op init merge (cdr tree))))))(tree-manip (lambda (x) (* x x)) ‘() cons ‘(1 (2 (3 4) 5) 6)) (1 (4 (9 16) 25) 36)(tree-manip (lambda (x) 1) 0 + ‘(1 (2 (3 4) 5) 6)) 6 ;; number of leaves(tree-manip (lambda (x) x) ‘() (lambda (a b) (append b (list a))) ‘(1 (2 (3 4) 5) 6)) (6 (5 (4 3) 2) 1) ;; deep reverse01/14/19 6.001 SICP 12/43Why search?•Structuring data is only part of the issue•Finding information distributed throughout complex data structures is often equally important01/14/19 6.001 SICP 13/43Examples of Search•Look up a friend’s email addressstatetowntypebusiness• Look up a business01/14/19 6.001 SICP 14/43Examples of search•Find a document on the Web01/14/19 6.001 SICP 15/43Web search and Web spiders•Web == (rapidly growing) collection of documents (unordered)•Document == text (& other material) & links to other documents•Stages:–Documents identified by URLs (http://sicp.csail.mit.edu)–Using HTTP protocol, can retrieve document, plus encoding information (ASCII, HTML, GIF, JPG, MPEG)–Program can extract links from document, hence URLs to other documents–Spider starts within initial set of URLs, retrieves documents, adds links, and keeps going. Each time it does some work, e.g. index of documents (keywords)01/14/19 6.001 SICP 16/43Simple search•Unordered collection of elements• treat as a list(define (find1 compare query set) (cond ((null? Set) ‘not-here) ((compare query (car set)) (car set)) (else (find1 compare query (cdr set)))))Order of growth is linear – if not there –n; if there, n/201/14/19 6.001 SICP 17/43Simple maintenance•Insertion is constant cost•Deletion is linear cost01/14/19 6.001 SICP 18/43Simple search•Ordered collection<<<<•Can use ordering, assume less? Same?(define (find2 less? Same? Query set) (cond ((null? Set) ‘not-here) ((less? Query (car set)) ‘not-here) ((same? Query (car set)) (car set)) (else (find2 less? Same? Query (cdr set)))))Order of growth is linear – if not there -- n/2; if there --
View Full Document
Unlocking...