Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Googmeister
Date : Mon Sep 12 2005 06:53 pm


Joe Seigh wrote:
> Speaking of balenced trees, which ones do the least
> amount of moving nodes around on inserts and deletes?
> In other works, least amount of nodes (their link
> pointers) getting modified.  That's probably more
> important for what I have in mind than minimum
> average depth.

Not quite sure about deletes, but it's possible
to implement red-black trees so that they
perform at most one single or double rotation
per insert,  and none per search.

.