Subj : Re: Balanced trees vs. B-trees To : comp.programming From : Ben Pfaff Date : Sat Sep 10 2005 10:39 pm "A. Bolmarcich" writes: > On 2005-09-10, Ben Pfaff wrote: >> "A. Bolmarcich" 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. That's going to seriously bias performance in favor of the simplest possible data structure. When insertions, searches, and deletions are done in random order, there is no advantage to balancing. -- Ben Pfaff email: blp@cs.stanford.edu web: http://benpfaff.org .