Red Black Trees Presentation Ultimate Pro

Red Black Tree

1. Red Black Trees By: Group 10

2. Introduction to Red Black Trees Self balancing binary search tree Invented by two researchers at PARC Xerox in 1978 Based on the work of Rudolf Bayer published in 1972 Easier to code and perform better than AVL trees when insertion and deletion operations are a priority.

3. Properties of Red Black Trees Every node is either red or black. The root of the tree must always be black. A red node can only have black children but a black node can either have a red or black child. All leaf(nil) nodes are considered black. Every path from root node to any of its descendant leaf nodes goes through the same number of black nodes.

4. Examples Figure 1 Figure 2 Figure 3 Black Height of the tree is inconsistent Two red nodes in a row and inconsistent black height. Not a red black tree. Adheres to all the rules of red black tree. Hence it is a valid red black tree.