[patch #5827] Plain balanced tree data structure

[Ben Pfaff]

Follow-up Comment #2, patch #5827 (project pspp):

>If you need a binary tree without augmentations, couldn't you 
>just use the augmented binary tree, but ignore the augmentation 
>stuff?

Yes.  The reason to have two different trees is performance tuning: in a
plain balanced tree it is relatively cheap to rotate nodes, so you may want
to have a relatively strict balancing rule, say that of an AVL tree or a
red-black tree.  But in an augmented balanced tree it is more expensive to
rotate nodes (because every rotation requires calling the reaugmentation
function on multiple nodes), so you want to have a relatively loose balancing
rule that tends to minimize the number of rotations.

Or so goes my personal theory, anyhow.  I do not have a testing harness
rigged up to actually demonstrate these effects.  But I think it is a
reasonable claim.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?5827>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/