[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[patch #5827] Plain balanced tree data structure

From: Ben Pfaff
Subject: [patch #5827] Plain balanced tree data structure
Date: Sat, 31 Mar 2007 17:13:11 +0000
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv: Gecko/20061205 Iceweasel/ (Debian-

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 

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:


  Message sent via/by Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]