 |
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
|
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
Simple implementation of a red-black tree. More...
Simple implementation of a red-black tree.
This implementation is based on BinarySearchTree and in particular BinarySearchTree#restructure for rebalancing.
Similarly to AVLTree, the implementation is based on BinarySearchTree#restructure (which is called from the onInsert callback. See Goodrich and Tamassia (2nd ed, chapter 13.3) for details!
This implementation is considerably simpler than the "standard" implementations based on rotations and split (see, e.g., Saake or Sedgewick) and the analogy to top-down 2-3-4 trees.
However, note that here the red-black property is enforced entirely bottom-up as either "restructuring" or "recoloring" in remedyDoubleRed. (One particular advantage is that we don't have to reimplement BinarySearchTree#insert; the onInsert callback is sufficient.)
The onRestructuring and onRecoloring callbacks provide additional hooks for visualization.
This implementation does not implement removal of nodes! remove always throws
UnsupportedOperationException
Note: The construction of red-black trees is not unique. A remarkable alternative are left-leaning red-black trees. The original article features a nice explanation and a short and elegant implementation.
Definition at line 39 of file RedBlackTree.java.
1.9.5