Differences between current version and previous revision of RedBlackTree.
Other diffs: Previous Major Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 2 | Last edited on Sunday, October 10, 2004 11:57:49 pm | by PhilMurray | |
| Older page: | version 1 | Last edited on Sunday, October 10, 2004 10:21:02 pm | by PhilMurray | Revert |
@@ -1,8 +1,8 @@
A RedBlackTree is an extended type of BinaryTree which satisfies the following conditions:
-* Every node is colored
either red or black
-* Every leaf node is colored
black
+* Every node is coloured
either red or black
+* Every leaf node is coloured
black
* If a node is red, then both of its children are black
* 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.
They guarantee O(log n) time per access.
