Annotated edit history of
RedBlackTree version 2, including all changes.
View license author blame.
| Rev |
Author |
# |
Line |
| 1 |
PhilMurray |
1 |
A RedBlackTree is an extended type of BinaryTree which satisfies the following conditions: |
| |
|
2 |
|
| 2 |
PhilMurray |
3 |
* Every node is coloured either red or black |
| |
|
4 |
* Every leaf node is coloured black |
| 1 |
PhilMurray |
5 |
* If a node is red, then both of its children are black |
| |
|
6 |
* Every path from the root to a leaf contains the same number of black nodes. This number is called the black-height of the tree. |
| |
|
7 |
|
| |
|
8 |
They guarantee O(log n) time per access. |
