1
/* ----------------------------------------------------------------------
4
* AVL style self balancing tree support.
6
* Copyright (c) 2007-2009, PostgreSQL Global Development Group
7
* Author: Jan Wieck, Afilias USA INC.
9
* $Id: avl_tree.c,v 1.3 2009-08-17 17:25:50 devrim Exp $
10
* ----------------------------------------------------------------------
16
* local function declarations
19
static AVLnode *avl_makenode(void);
20
static void avl_reset_node(AVLnode *node, AVLfreefunc *freefunc);
21
static int avl_insertinto(AVLtree *tree, AVLnode **node,
22
void *cdata, AVLnode **result);
23
static void avl_rotate_left(AVLnode **node);
24
static void avl_rotate_right(AVLnode **node);
30
* Initilize an AVL tree structure.
32
* compfunc is a user supplied tri-state comparision function that compares
33
* two tree elements and returns <0, 0 or >0 (like strcmp).
35
* If freefunc is specified, it is called to free no longer used elements.
36
* Note that the element will not immediately be free'd on avl_delete(),
37
* but only on a avl_delete, avl_insert sequence using the same key.
41
avl_init(AVLtree *tree, AVLcompfunc *compfunc, AVLfreefunc *freefunc)
44
tree->compfunc = compfunc;
45
tree->freefunc = freefunc;
52
* Reset an AVL tree to empty. This will call the user defined
53
* free function for all elements in the tree, destroy all nodes
54
* and declare the tree empty again.
58
avl_reset(AVLtree *tree)
60
avl_reset_node(tree->root, tree->freefunc);
68
* avl_reset()'s workhorse.
72
avl_reset_node(AVLnode *node, AVLfreefunc *freefunc)
77
avl_reset_node(node->lnode, freefunc);
78
avl_reset_node(node->rnode, freefunc);
81
freefunc(node->cdata);
89
* Insert an element into an AVL tree. On return AVL_DATA(node) might
90
* point to an existing entry with the same key. If the caller replaces
91
* the entry, it must free the existing one since AVL will no longer
96
avl_insert(AVLtree *tree, void *cdata)
102
* If this is an empty tree, create the root node.
104
if (tree->root == NULL)
105
return (tree->root = avl_makenode());
108
* Traverse the tree to find the insert point.
111
depth = avl_insertinto(tree, &(tree->root), cdata, &result);
119
* Search for an existing key in the tree.
123
avl_lookup(AVLtree *tree, void *cdata)
131
cmp = tree->compfunc(cdata, node->cdata);
135
* Found the node. If it is marked deleted, return NULL anyway.
136
* Otherwise return this node.
153
* No such element found
162
* Mark a given element as deleted. Subsequent lookups for the element
163
* will return NULL. Note that the caller should NOT free the memory
164
* of the element, as it is AVL's property altogether after the delete.
166
* avl_delete() returns 1 on success, 0 if no such element was found.
170
avl_delete(AVLtree *tree, void *cdata)
174
if ((node = avl_lookup(tree, cdata)) == NULL)
185
* The heart of avl_insert().
189
avl_insertinto(AVLtree *tree, AVLnode **node,
190
void *cdata, AVLnode **result)
195
* Compare the node at hand with the new elements key.
197
cmp = (tree->compfunc) (cdata, (*node)->cdata);
202
* New element is > than node. Insert to the right.
204
if ((*node)->rnode == NULL)
207
* Right side of current node is empty. Create a new node there
208
* and return new maximum depth. Note that this can only be 1
209
* because otherwise this node would have been unbalanced before.
211
(*node)->rnode = *result = avl_makenode();
217
* Right hand node exists. Recurse into that and remember the new
218
* right hand side depth.
220
(*node)->rdepth = avl_insertinto(tree, &((*node)->rnode),
224
* A right hand side insert can unbalance this node only to the right.
226
if (AVL_BALANCE(*node) > 1)
228
if (AVL_BALANCE((*node)->rnode) > 0)
231
* RR situation, rebalance the tree by left rotating this
234
avl_rotate_left(node);
239
* RL situation, rebalance the tree by first right rotating
240
* the right hand side, then left rotating this node.
242
avl_rotate_right(&((*node)->rnode));
243
avl_rotate_left(node);
247
return AVL_MAXDEPTH(*node);
252
* New element is < than node. Insert to the left.
254
if ((*node)->lnode == NULL)
257
* Left side of current node is empty. Create a new node there and
258
* return new maximum depth. Note that this can only be 1 because
259
* otherwise this node would have been unbalanced before.
261
(*node)->lnode = *result = avl_makenode();
263
return AVL_MAXDEPTH(*node);
267
* Left hand node exists. Recurse into that and remember the new left
270
(*node)->ldepth = avl_insertinto(tree, &((*node)->lnode),
274
* A left hand side insert can unbalance this node only to the left.
276
if (AVL_BALANCE(*node) < -1)
278
if (AVL_BALANCE((*node)->lnode) < 0)
281
* LL situation, rebalance the tree by right rotating this
284
avl_rotate_right(node);
289
* LR situation, rebalance the tree by first left rotating the
290
* left node, then right rotating this node.
292
avl_rotate_left(&((*node)->lnode));
293
avl_rotate_right(node);
297
return AVL_MAXDEPTH(*node);
302
* The new element is equal to this node. If it is marked for
303
* deletion, free the user element data now. The caller is supposed to
304
* replace it with a new element having the the key.
306
if ((*node)->deleted && tree->freefunc != NULL)
308
(tree->freefunc) ((*node)->cdata);
309
(*node)->cdata = NULL;
310
(*node)->deleted = 0;
313
return AVL_MAXDEPTH(*node);
321
* Create a new empty node.
329
new = (AVLnode *) malloc(sizeof(AVLnode));
330
memset(new, 0, sizeof(AVLnode));
337
* avl_rotate_left() -
339
* Rebalance a node to the left.
343
avl_rotate_left(AVLnode **node)
350
rtmp = (*node)->rnode;
353
* move right nodes left side to this nodes right
355
(*node)->rnode = rtmp->lnode;
356
if (rtmp->lnode != NULL)
357
(*node)->rdepth = AVL_MAXDEPTH(rtmp->lnode) + 1;
362
* Move this node to right nodes left side
365
rtmp->ldepth = AVL_MAXDEPTH(*node) + 1;
368
* Let parent point to right node
375
* avl_rotate_right() -
377
* Rebalance a node to the right.
381
avl_rotate_right(AVLnode **node)
388
ltmp = (*node)->lnode;
391
* move left nodes right side to this nodes left
393
(*node)->lnode = ltmp->rnode;
394
if (ltmp->rnode != NULL)
395
(*node)->ldepth = AVL_MAXDEPTH(ltmp->rnode) + 1;
400
* Move this node to left nodes right side
403
ltmp->rdepth = AVL_MAXDEPTH(*node) + 1;
406
* Let parent point to left node
added
removed
src/misc/avl_tree.c
