CS115 Study Guide - Final Guide: Binary Search Tree, Phylogenetic Tree, General Service Corps

• School: University of Waterloo
• Department: Computer Science
• Course: CS115
• Professor: Sandy Graham

Document Summary

Phylogenetic tree: data structure recording information about evolution of species. Two kinds of information: modern species and ancient ancestors of modern species. Speciation event: leads to splitting of one species into two distinct species. Taxon: a t-modern or a t-ancient (define-struct t-modern (name pop)) (define-struct t-ancient (name age left right)) T-modern: structure (make-t-modern n p), where n is string and p is number. T-ancient: structure (make-t-ancient n a l r), where n is string, a is number, and l and r are taxons. ;; my-taxon-fun: taxon any (define (my-taxon-fun t) (cond. Binary search trees (define-struct node (key val left right)) A bst (binary search tree, or bst) is either empty or a structure (make-node k v l r), where k is a number, v is a string, and l and r are bsts. Keys in the left are all less than k. Keys in the right are all greater than k. ;; my-bst-fun: bst any (define (my-bst-fun t) (cond.