source: trunk/src/zAVLTree.c@ 107

Last change on this file since 107 was 16, checked in by rainer, 19 years ago

minor optimization in zAVLtree

File size: 12.3 KB
Line 
1/*
2 * zAVLTree.c: Source code for zAVLTrees.
3 * Copyright (C) 1998,2001 Michael H. Buselli
4 * This is version 0.1.3 (alpha).
5 * Generated from $Id: xAVLTree.c.sh,v 1.5 2001/06/07 06:58:28 cosine Exp $
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Library General Public License for more details.
16 *
17 * You should have received a copy of the GNU Library General Public
18 * License along with this library; if not, write to the Free
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 * The author of this library can be reached at the following address:
22 * Michael H. Buselli
23 * 30051 N. Waukegan Rd. Apt. 103
24 * Lake Bluff, IL 60044-5412
25 *
26 * Or you can send email to <cosine@cosine.org>.
27 * The official web page for this product is:
28 * http://www.cosine.org/project/AVLTree/
29 */
30
31#include <stdlib.h>
32#include <string.h>
33#include "zAVLTree.h"
34
35/* Wed Nov 23 17:57:42 CET 2005 rw: introduce third argument in
36 * zAVLCloseSearchNode() to avoid redundant strcmp
37 */
38static zAVLNode *zAVLCloseSearchNode (zAVLTree const *avltree, zAVLKey key,
39 int * ok);
40static void zAVLRebalanceNode (zAVLTree *avltree, zAVLNode *avlnode);
41static void zAVLFreeBranch (zAVLNode *avlnode, void (freeitem)(void *item));
42static void zAVLFillVacancy (zAVLTree *avltree,
43 zAVLNode *origparent, zAVLNode **superparent,
44 zAVLNode *left, zAVLNode *right);
45
46#define MAX(x, y) ((x) > (y) ? (x) : (y))
47#define MIN(x, y) ((x) < (y) ? (x) : (y))
48#define L_DEPTH(n) ((n)->left ? (n)->left->depth : 0)
49#define R_DEPTH(n) ((n)->right ? (n)->right->depth : 0)
50#define CALC_DEPTH(n) (MAX(L_DEPTH(n), R_DEPTH(n)) + 1)
51
52#define ZAVL_OK 1
53#define ZAVL_NO 0
54
55
56/*
57 * AVLAllocTree:
58 * Allocate memory for a new AVL tree and set the getkey function for
59 * that tree. The getkey function should take an item and return an
60 * AVLKey that is to be used for indexing this object in the AVL tree.
61 * On success, a pointer to the malloced AVLTree is returned. If there
62 * was a malloc failure, then NULL is returned.
63 */
64zAVLTree *zAVLAllocTree (zAVLKey (*getkey)(void const *item))
65{
66 zAVLTree *rc;
67
68 rc = malloc(sizeof(zAVLTree));
69 if (rc == NULL)
70 return NULL;
71
72 rc->top = NULL;
73 rc->count = 0;
74 rc->getkey = getkey;
75 return rc;
76}
77
78
79/*
80 * AVLFreeTree:
81 * Free all memory used by this AVL tree. If freeitem is not NULL, then
82 * it is assumed to be a destructor for the items reference in the AVL
83 * tree, and they are deleted as well.
84 */
85void zAVLFreeTree (zAVLTree *avltree, void (freeitem)(void *item))
86{
87 if (NULL == avltree) /* R.W. Mon Nov 19 21:15:44 CET 2001 */
88 return;
89 if (avltree->top)
90 zAVLFreeBranch(avltree->top, freeitem);
91 free(avltree);
92}
93
94
95/*
96 * AVLInsert:
97 * Create a new node and insert an item there.
98 *
99 * Returns 0 on success,
100 * -1 on malloc failure,
101 * 3 if duplicate key.
102 */
103int zAVLInsert (zAVLTree *avltree, void *item)
104{
105 zAVLNode *newnode;
106 zAVLNode *node;
107 zAVLNode *balnode;
108 zAVLNode *nextbalnode;
109 int ok;
110
111 newnode = malloc(sizeof(zAVLNode));
112 if (newnode == NULL)
113 return -1;
114
115 newnode->key = avltree->getkey(item);
116 newnode->item = item;
117 newnode->depth = 1;
118 newnode->left = NULL;
119 newnode->right = NULL;
120 newnode->parent = NULL;
121
122 if (avltree->top != NULL) {
123 node = zAVLCloseSearchNode(avltree, newnode->key, &ok);
124
125 if (ok == ZAVL_OK) { /* exists already */
126 free(newnode);
127 return 3;
128 }
129
130 newnode->parent = node;
131
132 if (zAVLKey_cmp(avltree, newnode->key, node->key) < 0) {
133 node->left = newnode;
134 node->depth = CALC_DEPTH(node);
135 }
136
137 else {
138 node->right = newnode;
139 node->depth = CALC_DEPTH(node);
140 }
141
142 for (balnode = node->parent; balnode; balnode = nextbalnode) {
143 nextbalnode = balnode->parent;
144 zAVLRebalanceNode(avltree, balnode);
145 }
146 }
147
148 else {
149 avltree->top = newnode;
150 }
151
152 avltree->count++;
153 return 0;
154}
155
156
157/*
158 * zAVLSearch:
159 * Return a pointer to the item with the given key in the AVL tree. If
160 * no such item is in the tree, then NULL is returned.
161 */
162void *zAVLSearch (zAVLTree const *avltree, zAVLKey key)
163{
164 zAVLNode *node;
165 int ok;
166
167 if (NULL == avltree) /* R.W. Mon Nov 19 21:15:44 CET 2001 */
168 return NULL;
169
170 node = zAVLCloseSearchNode(avltree, key, &ok);
171
172 if (node && ok == ZAVL_OK)
173 return node->item;
174
175 return NULL;
176}
177
178
179/*
180 * zAVLDelete:
181 * Deletes the node with the given key. Does not delete the item at
182 * that key. Returns 0 on success and -1 if a node with the given key
183 * does not exist.
184 */
185int zAVLDelete (zAVLTree *avltree, zAVLKey key)
186{
187 zAVLNode *avlnode;
188 zAVLNode *origparent;
189 zAVLNode **superparent;
190 int ok;
191
192 avlnode = zAVLCloseSearchNode(avltree, key, &ok);
193 if (avlnode == NULL || ok == ZAVL_NO) /* does not exist */
194 return -1;
195
196 origparent = avlnode->parent;
197
198 if (origparent) {
199 if (zAVLKey_cmp(avltree, avlnode->key, avlnode->parent->key) < 0)
200 superparent = &(avlnode->parent->left);
201 else
202 superparent = &(avlnode->parent->right);
203 }
204 else
205 superparent = &(avltree->top);
206
207 zAVLFillVacancy(avltree, origparent, superparent,
208 avlnode->left, avlnode->right);
209 free(avlnode);
210 avltree->count--;
211 return 0;
212}
213
214
215/*
216 * zAVLFirst:
217 * Initializes an zAVLCursor object and returns the item with the lowest
218 * key in the zAVLTree.
219 */
220void *zAVLFirst (zAVLCursor *avlcursor, zAVLTree const *avltree)
221{
222 const zAVLNode *avlnode;
223
224 if (NULL == avltree) /* R.W. Mon Nov 19 21:15:44 CET 2001 */
225 return NULL;
226
227 avlcursor->avltree = avltree;
228
229 if (avltree->top == NULL) {
230 avlcursor->curnode = NULL;
231 return NULL;
232 }
233
234 for (avlnode = avltree->top;
235 avlnode->left != NULL;
236 avlnode = avlnode->left);
237 avlcursor->curnode = avlnode;
238 return avlnode->item;
239}
240
241
242/*
243 * zAVLNext:
244 * Called after an zAVLFirst() call, this returns the item with the least
245 * key that is greater than the last item returned either by zAVLFirst()
246 * or a previous invokation of this function.
247 */
248void *zAVLNext (zAVLCursor *avlcursor)
249{
250 const zAVLNode *avlnode;
251
252 avlnode = avlcursor->curnode;
253
254 if (avlnode->right != NULL) {
255 for (avlnode = avlnode->right;
256 avlnode->left != NULL;
257 avlnode = avlnode->left);
258 avlcursor->curnode = avlnode;
259 return avlnode->item;
260 }
261
262 while (avlnode->parent && avlnode->parent->left != avlnode) {
263 avlnode = avlnode->parent;
264 }
265
266 if (avlnode->parent == NULL) {
267 avlcursor->curnode = NULL;
268 return NULL;
269 }
270
271 avlcursor->curnode = avlnode->parent;
272 return avlnode->parent->item;
273}
274
275
276/*
277 * zAVLCloseSearchNode:
278 * Return a pointer to the node closest to the given key.
279 * Returns NULL if the AVL tree is empty.
280 */
281static zAVLNode *zAVLCloseSearchNode (zAVLTree const *avltree, zAVLKey key,
282 int * ok)
283{
284 zAVLNode *node;
285
286 *ok = ZAVL_NO;
287
288 node = avltree->top;
289
290 if (!node)
291 return NULL;
292
293 for (;;) {
294 if (!zAVLKey_cmp(avltree, node->key, key))
295 {
296 *ok = ZAVL_OK;
297 return node;
298 }
299
300 if (zAVLKey_cmp(avltree, node->key, key) < 0) {
301 if (node->right)
302 node = node->right;
303 else
304 return node;
305 }
306
307 else {
308 if (node->left)
309 node = node->left;
310 else
311 return node;
312 }
313 }
314}
315
316
317/*
318 * zAVLRebalanceNode:
319 * Rebalances the AVL tree if one side becomes too heavy. This function
320 * assumes that both subtrees are AVL trees with consistant data. This
321 * function has the additional side effect of recalculating the depth of
322 * the tree at this node. It should be noted that at the return of this
323 * function, if a rebalance takes place, the top of this subtree is no
324 * longer going to be the same node.
325 */
326static void zAVLRebalanceNode (zAVLTree *avltree, zAVLNode *avlnode)
327{
328 long depthdiff;
329 zAVLNode *child;
330 zAVLNode *gchild;
331 zAVLNode *origparent;
332 zAVLNode **superparent;
333
334 origparent = avlnode->parent;
335
336 if (origparent) {
337 if (zAVLKey_cmp(avltree, avlnode->key, avlnode->parent->key) < 0)
338 superparent = &(avlnode->parent->left);
339 else
340 superparent = &(avlnode->parent->right);
341 }
342 else
343 superparent = &(avltree->top);
344
345 depthdiff = R_DEPTH(avlnode) - L_DEPTH(avlnode);
346
347 if (depthdiff <= -2) {
348 child = avlnode->left;
349
350 if (L_DEPTH(child) >= R_DEPTH(child)) {
351 avlnode->left = child->right;
352 if (avlnode->left != NULL)
353 avlnode->left->parent = avlnode;
354 avlnode->depth = CALC_DEPTH(avlnode);
355 child->right = avlnode;
356 if (child->right != NULL)
357 child->right->parent = child;
358 child->depth = CALC_DEPTH(child);
359 *superparent = child;
360 child->parent = origparent;
361 }
362
363 else {
364 gchild = child->right;
365 avlnode->left = gchild->right;
366 if (avlnode->left != NULL)
367 avlnode->left->parent = avlnode;
368 avlnode->depth = CALC_DEPTH(avlnode);
369 child->right = gchild->left;
370 if (child->right != NULL)
371 child->right->parent = child;
372 child->depth = CALC_DEPTH(child);
373 gchild->right = avlnode;
374 if (gchild->right != NULL)
375 gchild->right->parent = gchild;
376 gchild->left = child;
377 if (gchild->left != NULL)
378 gchild->left->parent = gchild;
379 gchild->depth = CALC_DEPTH(gchild);
380 *superparent = gchild;
381 gchild->parent = origparent;
382 }
383 }
384
385 else if (depthdiff >= 2) {
386 child = avlnode->right;
387
388 if (R_DEPTH(child) >= L_DEPTH(child)) {
389 avlnode->right = child->left;
390 if (avlnode->right != NULL)
391 avlnode->right->parent = avlnode;
392 avlnode->depth = CALC_DEPTH(avlnode);
393 child->left = avlnode;
394 if (child->left != NULL)
395 child->left->parent = child;
396 child->depth = CALC_DEPTH(child);
397 *superparent = child;
398 child->parent = origparent;
399 }
400
401 else {
402 gchild = child->left;
403 avlnode->right = gchild->left;
404 if (avlnode->right != NULL)
405 avlnode->right->parent = avlnode;
406 avlnode->depth = CALC_DEPTH(avlnode);
407 child->left = gchild->right;
408 if (child->left != NULL)
409 child->left->parent = child;
410 child->depth = CALC_DEPTH(child);
411 gchild->left = avlnode;
412 if (gchild->left != NULL)
413 gchild->left->parent = gchild;
414 gchild->right = child;
415 if (gchild->right != NULL)
416 gchild->right->parent = gchild;
417 gchild->depth = CALC_DEPTH(gchild);
418 *superparent = gchild;
419 gchild->parent = origparent;
420 }
421 }
422
423 else {
424 avlnode->depth = CALC_DEPTH(avlnode);
425 }
426}
427
428
429/*
430 * zAVLFreeBranch:
431 * Free memory used by this node and its item. If the freeitem argument
432 * is not NULL, then that function is called on the items to free their
433 * memory as well. In other words, the freeitem function is a
434 * destructor for the items in the tree.
435 */
436static void zAVLFreeBranch (zAVLNode *avlnode, void (freeitem)(void *item))
437{
438 if (avlnode->left)
439 zAVLFreeBranch(avlnode->left, freeitem);
440 if (avlnode->right)
441 zAVLFreeBranch(avlnode->right, freeitem);
442 if (freeitem)
443 freeitem(avlnode->item);
444 free(avlnode);
445}
446
447
448/*
449 * zAVLFillVacancy:
450 * Given a vacancy in the AVL tree by it's parent, children, and parent
451 * component pointer, fill that vacancy.
452 */
453static void zAVLFillVacancy (zAVLTree *avltree,
454 zAVLNode *origparent, zAVLNode **superparent,
455 zAVLNode *left, zAVLNode *right)
456{
457 zAVLNode *avlnode;
458 zAVLNode *balnode;
459 zAVLNode *nextbalnode;
460
461 if (left == NULL) {
462 if (right)
463 right->parent = origparent;
464
465 *superparent = right;
466 balnode = origparent;
467 }
468
469 else {
470 for (avlnode = left; avlnode->right != NULL; avlnode = avlnode->right);
471
472 if (avlnode == left) {
473 balnode = avlnode;
474 }
475 else {
476 balnode = avlnode->parent;
477 balnode->right = avlnode->left;
478 if (balnode->right != NULL)
479 balnode->right->parent = balnode;
480 avlnode->left = left;
481 left->parent = avlnode;
482 }
483
484 avlnode->right = right;
485 if (right != NULL)
486 right->parent = avlnode;
487 *superparent = avlnode;
488 avlnode->parent = origparent;
489 }
490
491 for (; balnode; balnode = nextbalnode) {
492 nextbalnode = balnode->parent;
493 zAVLRebalanceNode(avltree, balnode);
494 }
495}
Note: See TracBrowser for help on using the repository browser.