Originally Posted by
MacNilly
Having implemented both an AVL tree and a RB tree, I can say that the AVL tree was MUCH MUCH simpler than the RB tree, especially for deleting a node. For instance, in the RB tree you have 6 or 7 cases (can be reduced to 3 using case-reduction) for deletion, and 3 for insertion and all the cases are different. For AVL tree, you have 3 cases for both insertion and deletion and they are almost exactly the same.
Also, doing some simple timing tests, the AVL tree outperformed the RB tree for search and insert, and was only very slightly slower for deletion; not enough to justify the complexity of the RB tree, IMO.