Red-black trees key-value pair abstraction, Insert a value with specified key, Search for value given key, Delete value with given key, Different implementations (Array, Linked list, BST (binary search tree)). | Red-black trees anhtt-fit@ Symbol Table Review Symbol table: key-value pair abstraction. Insert a value with specified key. Search for value given key. Delete value with given key. Different implementations Array Linked list BST (binary search tree) 1 Complexity Randomized BST. Guarantee of ~c lg N time per operation (probabilistic). Need subtree count in each node. Need random numbers for each insert/delete op. 2-3-4 tree 2-3-4 tree. Generalize node to allow multiple keys; help to keep tree balanced. Perfect balance. Every path from root to leaf has same length. Allow 1, 2, or 3 keys per node. 2-node: one key, two children. 3-node: two keys, three children. 4-node: three keys, four children. 2 Search Compare search key against keys in node. Find interval containing search key. Ex. Search for L Insert (1) Search to bottom for key. Ex. Insert B 3 Insert (2) 2-node at bottom: convert to 3-node. 3-node at bottom: convert to 4-node. Ex. Insert B Transformation Local transformations should be applied to keep the tree balanced. Ensures that most recently seen node is not a 4-node. Transformations to split 4-nodes: 4 Growth of a tree Growth of a tree .
