Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 5 Dec 2015 04:19:33 +0100
From: Szabolcs Nagy <nsz@...t70.net>
To: Ed Schouten <ed@...i.nl>
Cc: musl@...ts.openwall.com
Subject: Re: tdelete() may break the AVL tree balance property?

* Ed Schouten <ed@...i.nl> [2015-12-04 23:55:30 +0100]:
> 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.
> 

thanks for the report
yes it's wrong (this code is from me)
i attached a fix, but i'll have to
look at it again tomorrow in case
there is a better approach.

> 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,

View attachment "avl.diff" of type "text/x-diff" (1049 bytes)

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.