CSC 226 Lecture Notes - Lecture 9: Binary Search Tree
3 Oct 2016
School
Department
Course
Professor
Document Summary
The height of a 2-3 is o(logn) A different representation of a 2-3 tree: if you had 3-node subtree, then the left key would be a red child to the left. All red links go to the left. No node will have two red links connected to it. The tree has a perfect height: every path from the root to a leaf has the same number of black links. All links to external nodes are black. Link to a new node is red-black. We show: for every red-black tree there is a 2-3 tree. Given a red-black tree t, we build a 2-3 tree t"
