CS136 Lecture Notes - Lecture 22: Symbol Table, Associative Array, Dynamic Array
17 Apr 2018
School
Department
Course
Professor
Document Summary
Mixing paradigms: be careful with functional and imperative paradigm, hard to feel memory. Trees and efficiency: could still be unbalanced, bst_insert is still o (n) Balanced tree: the height is h = o(log n, running time of standard tree functions are all o(log n, if not balanced. 1 university of waterloo, cs 136 winter 2018, 11-linked_data_structure, p 57, snapshotted by author. Size node augmentation: a popular tree node augmentation is to store in each node the size of its subtree, retrieve the size of the tree in o (1, implement select function in o (h) 2 university of waterloo, cs 136 winter 2018, 11-linked_data_structures, p 60 , snapshotted by author. Tuesday, march 27, 2018: map / associative array / key-value store / symbol table, a collection of pairs of keys and values, unique key corresponding to a value, can have same value, similar bstnode structure. For a given key, retrieve the corresponding value or not found : insert.
