분야
pptx-History
-related information
2.Red Black properties
3.Operations
-Insert & delete
-code samples
-running times
-Advantage & Disadvantage
-Comparison to other algorithms
4.Applications
The Red Black Tree was first invented by Rudolf Bayer (1972), who called them “symmetric binary B-trees”.
In 1978, Leo J Guibas and Robert Sedgewick came up with the term, Red Black Binary Tree.
In 2008, Sedgewick introduced a simpler version of red-black trees called Left-Leaning Red-Black Trees
A RED-BLACK tree is a type of binary search tree that is self balancing.
Each node holds one extra piece of data, Color (red or black).
Besides following the rules of Binary Search Trees, Red Black Trees have 5 addition rules that keep them balanced.
Note1: leaves are nil (no value) and act just as place holder.
Note2: A Red Black Tree has a height of 2log(n + 1) at most
All rules pertaining to a Binary Search Tree.
A node is either RED or BLACK.
The root is always BLACK.
All leaves are BLACK.
Both Children of a node that is RED, are BLACK. (no RED node can have a RED child).
Every (simple) path from a node to a descendant leaf contains the same number of black Nodes (leaves not included). This is called BLACK height.
