ordered linked list—> binary search tree or skip list (out of course) BST Definitions A tree consists of: A set of nodes. A set of edges that connect those nodes. Constraint: There is exactly one path between any two nodes. In a rooted tree, we call one node the root. Every node N except the root has exactly one parent, defined as the first node on the path from N to the root.

To avoid the worst-case time complexity of O(n), we need to use a balanced binary search tree. Tree Rotation Non-obvious fact: Rotation allows balancing of any BST. One way to achieve balance: Rotate after each insertion and deletion to maintain balance. … the mystery is to know which rotations. We’ll come back to this. B-trees / 2-3 trees / 2-3-4 trees search tree weird solution to achieve balance add leaf overstuff leaf, but can not be too juicy!

起因，无序array Using data as an Index One extreme approach: All data is really just bits. Use data itself as an array index. Store true and false in the array. Extremely wasteful of memory. To support checking presence of all positive integers, we need 2 billion booleans. Need some way to generalize beyond integers. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class DataIndexedIntegerSet { boolean[] present; public DataIndexedIntegerSet() { present = new boolean[16]; } public insert(int i) { present[i] = true; } public contains(int i) { return present[i]; } } Binary Representations DataIndexedSet insert a cat 但是有弱点↓ collision handling & computing a hashCode！