CSCI 4117 Lecture 6: van Emde Boas Trees
20 Sep 2018
School
Department
Course
Professor
Document Summary
1. problem (1) maintain an ordered set of elements, to support (strict) (2) most well- known solution: balanced search trees time space (3) lower bound for under the binary decision tree model: Decision trees correspond to algorithms that only use comparisons to gain knowledge about the input. Any binary decision tree for membership must have leaves, one for each element + not found . As a binary tree on leaves must have height. , this lower bound applies. (4) counterexample : dynamic perfect hashing. Space cost: (5) not really di erent machine models! C-style operations (2) universe size : elements have values in element ts in a machine word, 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 (2) carve into widgets of size denotes if contains a. , that gives us the widget containing the successor . : update the position in the widget containing the element, and in summary.
