CPSC 110 Lecture 11: CPSC Lecture 11.docx

23
CPSC 110 Full Course Notes
Verified Note
23 documents
Document Summary
List, bst (list 3 2 1) = (list 3 2 1) Append appends 2 lists (append (list 1 2 3) (list 5 7 8)) = (list 1 2 3 5 7 8) Cons will add an element to your list (cons 0 (list 1 2 3)) = (list 0 1 2 3) : something that never varies, makes sure your tree is ok. Invariant (left/right subtrees are > or < than the mom) e. g. ;; invariant for a given node. ;; key is > htan all keysin the left subtree. ;; key is < than all keys in the right subtree. ;; the same key never appears twice in the tree (lookup-key t k) : t is bst (the tree you are searching in) , k is the key you"re searching for . Template changes when you have an extra (atomic distinct) k to work with: Changes from (define (fn-for-bst t) (cond [(false? t) ()]