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.