/*
avl_tree.c -- avl_ tree and linked list convenience
Copyright (C) 1998 Michael H. Buselli
- 2000,2001 Ivo Timmermans <itimmermans@bigfoot.com>,
- 2000,2001 Guus Sliepen <guus@sliepen.warande.net>
+ 2000,2001 Ivo Timmermans <ivo@o2w.nl>,
+ 2000,2001 Guus Sliepen <guus@sliepen.eu.org>
2000,2001 Wessel Dankers <wsl@nl.linux.org>
This program is free software; you can redistribute it and/or modify
Cleaned up and incorporated some of the ideas from the red-black tree
library for inclusion into tinc (http://tinc.nl.linux.org/) by
- Guus Sliepen <guus@sliepen.warande.net>.
+ Guus Sliepen <guus@sliepen.eu.org>.
- $Id: avl_tree.c,v 1.1.2.5 2001/02/06 10:13:21 guus Exp $
+ $Id: avl_tree.c,v 1.1.2.9 2002/06/21 10:11:11 guus Exp $
*/
#include <stdio.h>
new->data = data;
avl_insert_after(tree, closest, new);
break;
- case 0:
+ default:
return NULL;
}
}
node->parent = before;
node->prev = before->prev;
+ if(before->left)
+ return avl_insert_after(tree, before->prev, node);
+
if (before->prev)
before->prev->next = node;
else
if (!after)
return tree->head ? avl_insert_before(tree, tree->head, node) : avl_insert_top(tree, node);
+ if(after->right)
+ return avl_insert_before(tree, after->next, node);
+
node->prev = after;
node->parent = after;
node->next = after->next;
}
avl_rebalance(tree, balnode);
+
+ node->next = node->prev = node->parent = node->left = node->right = NULL;
+
+#ifdef AVL_COUNT
+ node->count = 0;
+#endif
+#ifdef AVL_DEPTH
+ node->depth = 0;
+#endif
}
void avl_delete_node(avl_tree_t *tree, avl_node_t *node)