From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8956 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: tdelete() may break the AVL tree balance property? Date: Sat, 5 Dec 2015 04:19:33 +0100 Message-ID: <20151205031933.GT23362@port70.net> References: Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="o0ZfoUVt4BxPQnbU" X-Trace: ger.gmane.org 1449285593 9265 80.91.229.3 (5 Dec 2015 03:19:53 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 5 Dec 2015 03:19:53 +0000 (UTC) Cc: musl@lists.openwall.com To: Ed Schouten Original-X-From: musl-return-8969-gllmg-musl=m.gmane.org@lists.openwall.com Sat Dec 05 04:19:50 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1a53O1-0004k8-AK for gllmg-musl@m.gmane.org; Sat, 05 Dec 2015 04:19:49 +0100 Original-Received: (qmail 7780 invoked by uid 550); 5 Dec 2015 03:19:45 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 7759 invoked from network); 5 Dec 2015 03:19:45 -0000 Mail-Followup-To: Ed Schouten , musl@lists.openwall.com Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.24 (2015-08-30) Xref: news.gmane.org gmane.linux.lib.musl.general:8956 Archived-At: --o0ZfoUVt4BxPQnbU Content-Type: text/plain; charset=us-ascii Content-Disposition: inline * Ed Schouten [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, --o0ZfoUVt4BxPQnbU Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="avl.diff" diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c index 8620092..e53cf32 100644 --- a/src/search/tsearch_avl.c +++ b/src/search/tsearch_avl.c @@ -105,11 +105,17 @@ static struct node *insert(struct node **n, const void *k, return r; } -static struct node *movr(struct node *n, struct node *r) { - if (!n) - return r; - n->right = movr(n->right, r); - return balance(n); +static struct node *poprightmost(struct node **p, struct node *n) +{ + struct node *r; + + if (!n->right) { + *p = n->left; + return n; + } + r = poprightmost(&n->right, n->right); + *p = balance(n); + return r; } static struct node *remove(struct node **n, const void *k, @@ -122,7 +128,13 @@ static struct node *remove(struct node **n, const void *k, c = cmp(k, (*n)->key); if (c == 0) { struct node *r = *n; - *n = movr(r->left, r->right); + if (r->left) { + *n = poprightmost(&r->left, r->left); + (*n)->left = r->left; + (*n)->right = r->right; + *n = balance(*n); + } else + *n = r->right; free(r); return parent; } --o0ZfoUVt4BxPQnbU--