RED BLACK TREE & TRIES

SEARCH STRUCTURES

Red Black Tree  click here

Red Black Tree Algorithm  click here

Tries click here

Red-Black Properties

1. Every node is either red or black.
2. Every leaf (NULL pointer) is black.
   ■ Note: this means every “real” node has 2 children
3. If a node is red, both children are black
   ■ Note: can’t have 2 consecutive reds on a path
4. Every path from node to descendent leaf contains the same number of black nodes.
5. The root is always black

RB Trees: Worst-Case Time

• So we’ve proved that a red-black tree has  O(lg n) height
• Corollary: These operations take O(lg n) time:

                        ■Minimum(), Maximum()
                        ■Successor(), Predecessor()
                        ■Search()

• Insert() and Delete():

                        ■Will also take O(lg n) time

                        ■But will need special care since they modify tree