CSE 214 Lecture Notes - Lecture 25: Natural Number, Null Pointer, Binary Search Tree
31 Oct 2016
School
Department
Course
Professor
Document Summary
Everything up to the last lecture is on the exam. Try to avoid tree of depth n. balanced tree meant to minimize depth. A red-black tree has the advantages of a 2-3-4 tree but requires less storage. Every node is colored either red or black. If a node is red, its children must be black. Every path from the root to a null link must contain the number of black nodes. This is because we don"t want one path to grow more than the other. Here, 85 is not black since when we insert the nodes, it will be red for efficiency. If it was changed to black, the number of blacks from the root to 85 will be 3 while all the other paths have 2 black nodes in the path. Depth o(logn) since it is a blanced binary search tree. You can easily convert red-black trees to 2-3-4 trees, but these trees are not related in any way.
