BALANCED SEARCH TREES
2 Jul 2022
School
Department
Course
Professor
Document Summary
Add new key to 3-node to create temporary 4-node. If you reach the root and it"s a 4-node, split it into three 2-nodes. all of the possibilities we may do: https://cs. ericyy. me/algorithms-1/week-5/index. html. Best case: log 3 n . 631 lg n . Between 12 and 20 for a million nodes. Between 18 and 30 for a billion nodes. This course focuses on left-leaning red-black bsts: represent 2 3 tree as a bst, use internal left-leaning links as glue for 3 nodes. Orient a (temporarily) right-leaning red link to lean left/right. Node x = h. right; h. right = x. left; x. left = h; x. color = h. color; h. color = red; return x; 5 private void flipcolors(node h) { h. color = red; h. left. color = black; h. right. color = black; https://cs. ericyy. me/algorithms-1/week-5/index. html. Search is the same as for elementary bst (ignore color). Height of tree is 2 lg n in the worst case. Every path from root to null link has same number of black links.
