[m-dev.] for review: balance in 234-trees

[Mark Brown]

On 05-Apr-2002, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> +% If the child we want to insert into and its parent node are both 4-nodes,
> +% then insertion will not preserve balance.

I disagree with this analysis.  According to the algorithm in Sedgewick,
this situation should present no problem -- the 4-nodes should be split
on the way down, in which case either the middle value will be added to
its parent node, or (if the 4-node is the root) the middle value will
become the new root.  In the former case, the parent node increases from
size 2 to size 3, or size 3 to size 4 (the parent cannot be a 4-node
because we process the nodes top-down), and the height of the tree does
not change.  In the latter case, the height of the entire tree increases
by 1.  In both cases balance is preserved.

Note that the invariant in Sedgewick is not that there can _never_ be a
parent and child which are both 4-nodes.  Rather, it is that at the point
where a 4-node is split, it cannot have a parent which is also a 4-node.
Looking at the code, it does appear to satisfy this.  Perhaps I am mistaken
about this; do you have a test case that demonstrates that tree234__insert
is the culprit?

If you do have an example where the invariant fails, or where we deviate
from Sedgewick in some other way, then I suggest you remove the part of the
comment that says we follow the appproach described in Sedgewick, and
replace it with an XXX which says we do not follow this approach.

Cheers,
Mark.

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------