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.