Red-black trees anhtt-fit@mail.hut.edu.vn 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 (cont.) 5 Complexity Tree height Worst case: lg N [all 2-nodes] Best case: log4 N = 1/2 lg N [all 4-nodes] Between 10 and 20 for a million nodes. Between 15 and 30 for a billion nodes. Red-black tree Represent 2-3-4 tree as a BST. Use "internal" left-leaning edges for 3- and 4- nodes. 1-1 corresponde