RBT

Red black tree: BST data structure with extra color field for each nodes

1. every node is either red or black
2. root and leaves(nils) are all black
3. every red node has black parent
4. all single paths from a node x to a descendant leaf of x has same number of black nodes = black-height of x(not counts x itself)

REF:

• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/lec10.pdf
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/
• http://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/