[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <CABh_MKki7dL2=dsH03W+JwXbcNcWO5SVd+JQTpriJOa+Mcn4Nw@mail.gmail.com>
Date: Fri, 4 Dec 2015 23:55:30 +0100
From: Ed Schouten <ed@...i.nl>
To: musl@...ts.openwall.com
Subject: tdelete() may break the AVL tree balance property?
Hi there,
If my interpretation of tsearch_avl.c is correct, it seems to be the
case that the implementation of tdelete() is different from how
removal of nodes in AVL trees is described in literature.
It looks as if the removal of a node in the middle of a tree is
implemented by attaching its right subtree to the rightmost node of
the left subtree (its predecessor) through the movr() function. Though
this maintains order correctly, the problem with this approach is that
it yields trees that have an absolute balance factor greater than 2.
As far as I know, the rotation operations are not sufficient to
rebalance in those situations.
The conventional approach of implementing deletion is not by attaching
the two subtrees to another, but by completely extracting the
predecessor from the left subtree. This predecessor can then be used
to join both subtrees together, as shown in this image:
https://en.wikipedia.org/wiki/AVL_tree#/media/File:Binary_search_tree_delete.svg
As the left subtree has its height decreased by at most one, the
absolute balance factor should be at most 2, meaning that rebalancing
should always be possible.
Best regards,
--
Ed Schouten <ed@...i.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
