Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : A. Bolmarcich
Date : Sun Sep 11 2005 04:59 am

On 2005-09-10, Ben Pfaff <blp@cs.stanford.edu> wrote:
> "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> writes:
>
>> My general conclusions are that AVL trees have the best performance and
>> least average node depth.  Red-Black trees have slightly lower
>> performance than AVL tress and slightly greater average node depth.
>> trees.  Binary B-Trees have slightly lower performance than Red-Black
>> trees and even greater average node depth.  However, when parent
>> pointers are not present the performance of the insert node function
>> of Red-Black trees is much worse than that of AVL trees and Binary
>> B-Trees.
>
> It is difficult to compare the performance of data structures in
> the absence of description of how they are being used.  In what
> situation do you obtain the above results?

Adding nodes to a tree in random order.  Searching the tree for all
the nodes in it and for the same number of nodes not in it.  Deleting
node from the tree in random order.

.