# Abstract Data Types

Read Abstract Data Types first.

A type of the data is defined by the set of legal operations which could be performed on the data.

There are my **Lecture Notes** for *Berkeley CS61A* course as it taught in a Spring of 2008.

;; Hierarchical data - a form, a shape, a structure of the data ;; Tree - the way to represent a hierarchical data. ;; Tree is a structure with "vertical" links between its Nodes ;; a Node of a Tree is a Tree itself (a Node is of type Tree) ;; a structure with "horizontal" links between nodes is called List ;; usually a Node of a List is a List itself ;; Tree - a structure with only one parent for each Node ;; a structure with more than one parent for a Node is called Graph ;; Graph is a structure with "horisontal" and "vertical" links between its Nodes. ;; Nodes of a Graph are Graphs themselves ;; Binary Tree - a structure with at most two children - left and right branches. ;; Binary Search Tree - a pre-ordered Tree ;; all elements on the left branch are less than Datum of the Node ;; all elements on the right branch are greater than Datum of the Node ;; ADT: General Tree - Datum and a List of children (a List of Trees/Nodes) ;; Pieces of a tree (Nodes) are Trees themselves. ;; ADT Tree ;; Selectors: datum, children - a List of Nodes/Trees ;; root Node (only one) ;; branch Nodes (many) ;; leaf Nodes (Nodes with no children) (many) ;; every Node has only one parent ;; root Node has no parent ;; each Node of a Tree is itself a Tree ;; there is no difference between Trees and Nodes - they are of the same type. ;; ADT General Tree: constructor and selectors (synonyms) '(d n1, n2, n3) ; a Node is a List of a Datum and a List of Nodes (define make-tree cons) ; prepend a Datum to a List (define datum car) ; CAR is a Datum (define children cdr) ; CDR is a List of Trees (leaf nodes) (define (leaf? n) ; predicate function (null? (children n))) ;; very beautiful piece of recursive code (define (tree-map f t) (make-tree (f (datum t)) (map (lambda (c) (tree-map f c)) ; the base-case is inside the map (cildren t)))) ; a list of trees (leaf nodes) ;; read and trace this piece of code until a premature enlightenment ;; chanting: domain and range, domain and range (define (tree-map f t) (make-tree (f (datum t)) ; Tree is a List of Datum and children (forest-map f (children t)))) (define (forest-map f l) ; a Forest is a list-of-trees (if (null? l) '() (cons (tree-map f (car l)) ; the mutual recursions (forest-map f (cdr l))))) ;; Recursion is the way to deal with nested Lists (sequences) ;; Mutual Recursion is a general way for dealing with 2D-structures ;; Deep Lists - Lists of Pairs - looks like a special kind of Binary Tree '((John Lenon) (Paul McCartny) (Geoge Harrison) (Ringo Starr)) ;; a defective Binary Tree ;; branch Nodes have no Datum, only children ;; leaf Nodes have only Datums, no children (define (deep-map f l) (if (list? l) (map (lambda (e) (deep-map f e)) l) ; a branch node - no datums - proceed (f l))) ; a leaf node - apply a procedure ;; General Trees have both Datums and Children ;; Deep Lists have either Datums or Children ;; traversing a Deep List (List of Pairs) as if it is a Binary Tree. (define (deep-map f l) (cond ((null? l) '()) ; the base case (()) ((pair? l) ; a branch node - spine cord pair (CDR) (cons (deep-map f (car l)) (deep-map f (cdr l)))) (else (f l)))) ; a datum (CAR) ;; traversing any structure made out of Pairs (deep-map (lambda (x) (* x x)) '((1 . 2) (3 . 4) (((5)) . 6))) ;; Lists-of-Pairs looks like a Binary Tree ;; Associative List looks like a Lookup Table

;; 2 children n-children ;; ;; Binary Tree Tree ;; ;; CAR/CDR Recursion Deep List ;; (nested pairs) (nested lists) ;; Nested Lists are defective Binary Trees ;; each Node has either children or Datum, not both. ;; CAR/CDR Recursion (define (deep-map f p) (cond ((null? p) '()) ; the base case (()) ((pair? p) ; a branch node - spine cord pair (cdr) (cons (deep-map f (car p)) (deep-map f (cdr p)))) (else (f p)))) ; a datum (car) ;; Lists of Lists (define (map f l) (if (null? l) '() (cons (f (car l)) (map f (cdr l))))) (define (filter f l) (cond ((null? l) '()) ((f (car l)) (cons (car l) (filter f (cdr l)))) (else (filter f (cdr l))))) ;; binary Decision Tree ;; binary tree recursion without a binary tree (+ (count-change (- amount (car coins)) coins) ; left branch (count-change amount (cdr coins))) ; right branch ;; Tree traversal (order of visiting its nodes) ;; in a Tree there are only "vertical" links between nodes, no "horizontal" links ;; a constructor (define make-tree cons) ;; selectors - synonyms (define datum car) (define children cdr) ;; a tree made out of lists (define t1 '(1 (2 (3) (4)) (5 (6) (7) (8)))) ;; depth-first traversal (define (depth-first-search t) (display (datum t)) (for-each depth-first-search (children t))) (depth-first-search t1) ;; breadth-first traversal (row by row) ;; use breadth-first search to find a Shortest Path. (define (breadth-first-search t) (bfs-iter (list t))) ; a list of length 1 with the root Node inside (define (bfs-iter q) (if (null? q) ; Queue is an ordered List of Trees/Nodes 'done (let ((n (car q))) ; CAR of queue is a Node (each Node is a Tree) (display (datum n)) (bfs-iter (append (cdr q) (children n)))))) ; CDR of queue is a List (breadth-first-search t1) ;; Traversing a Binary Tree ;; a Node of a Binary Tree is a Binary Tree made out of Pairs ;; (datum . (left-branch . right-branch)) - tightly packed Pointers ;; prototyping ADT '(1 . (2 . 3)) (car '(1 . (2 . 3))) ; datum (cdr '(1 . (2 . 3))) ; CDR is pair (cadr '(1 . (2 . 3))) ; left branch (cddr '(1 . (2 . 3))) ; right branch ;; constructor (define (make-node d l r) (cons d (cons l r))) ;; selectors - synonyms (define datum car) (define left-branch cadr) (define right-branch cddr) ;; tests (define n (make-node '(1 2 3) '() '())) ; a leaf node - no children, only datum (datum n) (left-branch n) (right-branch n) ;; a Node of a Binary Tree is a Binary Tree made out of Lists ;; (datum left-branch right-branch) - loosely coupled Pointers ;; Computer memory is an indexed sequence (Array) of words. ;; Representing any structure as a list of pointers is the most natural way. ;; prototyping ADT '(1 2 3) (car '(1 2 3)) ; datum (cdr '(1 2 3)) ; CDR of a list is a list (cadr '(1 2 3)) ; left branch (caddr '(1 2 3)) ; right branch ;; constructor (define (make-node d l r) (cons d (list l r))) ; stick a Datum in front of children ;; selectors (synonyms) (define entry car) (define left-branch cadr) (define right-branch caddr) ;; testing (define n (make-node '(1 2 3) '() '())) ; a leaf node - no children, only datum (entry n) (left-branch n) (right-branch n) ;; 3 different orders - a sequence of events (define (pre-order t) (cond ((null? t) '()) ((else (display (entry t)) (pre-order (left-branch t)) (pre-order (right-branch t)))))) (define (in-order t) (cond ((null? t) '()) (else (in-order (left-branch t)) (display (entry t)) (in-order (right-branch t))))) (define (post-order t) (cond ((null? t) '()) (else (post-order (left-branch t)) (post-order (right-branch t)) (display (entry t))))) ;; a Path is a List of names (of visited Places) ;; if the range of a procedure are lists, return a list ;; Example (define make-tree cons) (define datum car) (define children cdr) (define (city x) (make-tree x '())) (define (leaf? n) (null? (children n))) ;; domain: Place (a Symbol) and Tree ;; range: Path (a List of Places) (define (find-place p t) (cond ((eq? p (datum t)) (cons (datum t) '())) ; return a Path (a list of places) ((leaf? t) '()) ; a Leaf Node (no children) - fail (else (let ((path (find-subtree p (children t)))) (if (not (null? path)) ; found any path? (cons (datum t) path) '()))))) ;; domain: Place and a Forest (a List of Trees/Nodes) ;; range: Path (a List of Places) (define (find-subtree p l) (if (null? l) '() (let ((path (find-place p (car l)))) (if (not (null? path)) path ; a Path is a List (find-subtree p (cdr l)))))) ; proceed ;; use Hash Tables for lookups

Last modified
3 years ago
Last modified on Aug 31, 2017, 9:01:06 AM

**Note:**See TracWiki for help on using the wiki.