From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8955 Path: news.gmane.org!not-for-mail From: Ed Schouten Newsgroups: gmane.linux.lib.musl.general Subject: tdelete() may break the AVL tree balance property? Date: Fri, 4 Dec 2015 23:55:30 +0100 Message-ID: Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1449271753 10895 80.91.229.3 (4 Dec 2015 23:29:13 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 4 Dec 2015 23:29:13 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-8968-gllmg-musl=m.gmane.org@lists.openwall.com Sat Dec 05 00:29:09 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 1a4zmj-0001Lm-9h for gllmg-musl@m.gmane.org; Sat, 05 Dec 2015 00:29:05 +0100 Original-Received: (qmail 26001 invoked by uid 550); 4 Dec 2015 23:29:02 -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 9699 invoked from network); 4 Dec 2015 22:55:42 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nuxi-nl.20150623.gappssmtp.com; s=20150623; h=mime-version:date:message-id:subject:from:to:content-type; bh=TqTVotiGXv8A//s9K6xRU7Asg9QINM8eRV99w43UXQs=; b=EFK8hqV8Mqw1nMKP/JSHO3CfsldTm+UoGPxZjEw90ztjT7WuM8hhmbgAwwG/hP7SGY Vsnwx0n7QiAPLZ/gU7Nmr59MuWCsprBG7yEpx4DZWvTr3YZ32yKRhLt52FmXTMGm0s/+ jwYbk+Pb6hpOPwch8Tpk2q7KL2+qhbwnMtPAnlZWvNnaVQUn0l9FpyqXBLYwljaSERlb b6JfrU0mjbHedpFbN7ur9DqT3woI6G4GHvpmiUZs8ZWrNrLMbEFytKNXqjdSvAalcZ0t 7K9H37Itlx5muqi93tbjAlI+bvc6+FLgBKWKOFqRmEoPEDdYios5x0H3UModXab2IRUp JHOg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to :content-type; bh=TqTVotiGXv8A//s9K6xRU7Asg9QINM8eRV99w43UXQs=; b=P/J0JV9SlryJMCOV6SyFDW5qkDl2mhRMKfxuKu4iEJxDEfd5Qy/CA3TsIe52i9j30D a4dyp3VrL2/5eQuycECjM4RFjd0KfKrvJz8nneAY9v8SDonTBr/yhbBwl6xCNbhBTyT1 E7kPMzhc5tpK4eg9ZGc2TVIdQQLZoowlUa/CjaycDnOZgAA6e59kCrUgQ2X8nfGVSBsl 6GziYysrdcBNMIGw7BztyInnjuhalnY8mPcyG57t76ttJnROPkdmQNOLSpxZGUkgkIkF NnPP/H+ZCWjMwWywOCbzGf5zcrQrCgvLPLDgBd3HDiXSIlKOaUoym+AUFMFYRhFYKFmN jabA== X-Gm-Message-State: ALoCoQkxFG6JiLGCYg+m2us0FDtkrAruwb3x14bDExWSkIK6BbUYRWvHt/Vx9XGkAphGa19IIZic X-Received: by 10.129.96.84 with SMTP id u81mr13380637ywb.80.1449269730507; Fri, 04 Dec 2015 14:55:30 -0800 (PST) Xref: news.gmane.org gmane.linux.lib.musl.general:8955 Archived-At: 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 Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717