Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : A. Bolmarcich
Date : Mon Sep 12 2005 07:47 pm

On 2005-09-11, Ben Pfaff <blp@cs.stanford.edu> wrote:
>> 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.

Just because the insertion order is random does not mean that a
binary tree build by unbalanced tree insertion will necessarily be as
well balanced as a binary tree built by a balanced tree insertion.
Using the same random insertation order I get the following minimum and
maximun leaf node depths for unbalanced and AVL trees.

              minimum      maximum
tree type   leaf depth   leaf depth

unbalanced       7           46
AVL             15           23

Having to traverse 23 more levels of a tree to reach some nodes will
effect the search time.

The order in which insertions and deletions are done will effect how
often the different types of rebalancing actions are done, such a
single rotation and double rotations with an AVL tree.  These
different rebalancing actions execute different number of instructions
and will likely take different amounts of time.

For a binary tree type, the order in which searches are done should not
effect the total number of instructions executed to do all the searches.
However, there will be virtual memory performance effects due to the
number and order of page faults.

Do you have recommended orders for the insertions, searches, and
deletions?

.