2N/Astatic const char rcsid[] =
"$Id: tree.c,v 1.4 2005/04/27 04:56:39 sra Exp $";
2N/A * tree - balanced binary tree library 2N/A * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names] 2N/A * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes] 2N/A * vix 23jun86 [added delete uar to add for replaced nodes] 2N/A * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224] 2N/A * vix 06feb86 [added tree_mung()] 2N/A * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221] 2N/A * vix 14dec85 [written] 2N/A * This program text was created by Paul Vixie using examples from the book: 2N/A * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN 2N/A * 0-13-022005-1. Any errors in the conversion from Modula-2 to C are Paul 2N/A * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 2N/A * Portions Copyright (c) 1996-1999 by Internet Software Consortium. 2N/A * Permission to use, copy, modify, and distribute this software for any 2N/A * purpose with or without fee is hereby granted, provided that the above 2N/A * copyright notice and this permission notice appear in all copies. 2N/A * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 2N/A * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 2N/A * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 2N/A * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 2N/A * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 2N/A * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 2N/A * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 2N/A/*#define DEBUG "tree"*/ 2N/A /* not higher, not lower... this must be the one. 2N/A /* grounded. NOT found. 2N/A /* are we grounded? if so, add the node "here" and set the rebalance 2N/A MSG(
"grounded. adding new node, setting h=true")
2N/A /* compare the data using routine passed by caller. 2N/A /* if LESS, prepare to move to the left. 2N/A MSG(
"LESS: left branch has grown")
2N/A /* right branch WAS longer; bal is ok now */ 2N/A MSG(
"LESS: case 1.. bal restored implicitly")
2N/A /* balance WAS okay; now left branch longer */ 2N/A MSG(
"LESS: case 0.. balnce bad but still ok")
2N/A /* left branch was already too long. rebal */ 2N/A MSG(
"LESS: case -1: rebalancing")
2N/A }
else {
/*%< double LR */ 2N/A /* if MORE, prepare to move to the right. 2N/A MSG(
"MORE: sprouting to the right")
2N/A MSG(
"MORE: right branch has grown")
2N/A MSG(
"MORE: balance was off, fixed implicitly")
2N/A MSG(
"MORE: balance was okay, now off but ok")
2N/A MSG(
"MORE: balance was off, need to rebalance")
2N/A }
else {
/*%< double RL */ 2N/A /* not less, not more: this is the same key! replace... 2N/A MSG(
"FOUND: Replacing data value")
2N/A MSG(
"right subtree non-null, left subtree null")
2N/A /* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */ 2N/A MSG(
"was imbalanced, fixed implicitly")
2N/A MSG(
"was okay, is now one off")
2N/A MSG(
"was already off, this is too much")
2N/A MSG(
"right branch has shrunk")
2N/A MSG(
"was imbalanced, fixed implicitly")
2N/A MSG(
"was okay, is now one off")
2N/A MSG(
"was already off, this is too much")