CSC 226 Lecture 10: Oct. 3rd
3 Oct 2016
School
Department
Course
Professor
Document Summary
For every red edge and its incident two nodes v(rb) and w(rb) where w(rb) is the parent of v(rb) containing keys k1 and k2 create a 3-node vw(23). The nodes of the red-black tree t" are obtained as follows. For every 2-node v(23) in the ed-black tree with key k create node v(rb) with key ke. For every 3-node vw(23) with keys k1 and k2, k1<= k2, create nodes v(rb) and w(rb) containing keys k1 and k2, respectively. The height of a red-black tree with n keys is o(logn) The black path length from leaf to root is the same as the height of its corresponding 2-3 tree that is o(logn). Let h be the height of the tree: h <= 2d <= 2log(n+1) <= 2log(n+n, h belongs to o(logn)
