avltree_remove, avltree_free functions.

fragglet · fragglet · commit 06f9f758a5aa · 2005-12-23T18:24:43.000Z
diff --git a/src/avltree.c b/src/avltree.c
@@ -64,6 +64,29 @@ AVLTree *avltree_new(AVLTreeCompareFunc compare_func)
 	return new_tree;
 }
 
+static void avltree_free_subtree(AVLTree *tree, AVLTreeNode *node)
+{
+	if (node == NULL) {
+		return;
+	}
+
+	avltree_free_subtree(tree, node->left_child);
+	avltree_free_subtree(tree, node->right_child);
+
+	free(node);
+}
+
+void avltree_free(AVLTree *tree)
+{
+	/* Destroy all nodes */
+	
+	avltree_free_subtree(tree, tree->root_node);
+
+	/* Free back the main tree data structure */
+
+	free(tree);
+}
+
 int avltree_subtree_height(AVLTreeNode *node)
 {
 	if (node == NULL) {
@@ -508,6 +531,29 @@ void avltree_remove_node(AVLTree *tree, AVLTreeNode *node)
 	}
 }
 
+/* Remove a node by key */
+
+int avltree_remove(AVLTree *tree, void *key)
+{
+	AVLTreeNode *node;
+
+	/* Find the node to remove */
+
+	node = avltree_lookup_node(tree, key);
+
+	if (node == NULL) {
+		/* Not found in tree */
+		
+		return 0;
+	}
+
+	/* Remove the node */
+
+	avltree_remove_node(tree, node);
+
+	return 1;
+}
+
 AVLTreeNode *avltree_lookup_node(AVLTree *tree, void *key)
 {
 	AVLTreeNode *node;
diff --git a/src/avltree.h b/src/avltree.h
@@ -49,10 +49,12 @@ POSSIBILITY OF SUCH DAMAGE.
  * as a mapping (searching for a value based on its key), or
  * as a set of keys which is always ordered.
  *
- * To create a new AVL tree, use @ref avltree_new.
+ * To create a new AVL tree, use @ref avltree_new.  To destroy
+ * an AVL tree, use @ref avltree_free.
  *
  * To insert a new key-value pair into an AVL tree, use
- * @ref avltree_insert.
+ * @ref avltree_insert.  To remove an entry from an
+ * AVL tree, use @ref avltree_remove or @ref avltree_remove_node.
  *
  * To search an AVL tree, use @ref avltree_lookup or 
  * @ref avltree_lookup_node.
@@ -114,6 +116,14 @@ typedef int (*AVLTreeCompareFunc)(void *data1, void *data2);
 
 AVLTree *avltree_new(AVLTreeCompareFunc compare_func);
 
+/**
+ * Destroy an AVL tree.
+ * 
+ * @param tree            The tree to destroy.
+ */
+
+void avltree_free(AVLTree *tree);
+
 /**
  * Insert a new key-value pair into an AVL tree.
  *
@@ -135,6 +145,19 @@ AVLTreeNode *avltree_insert(AVLTree *tree, void *key, void *value);
 
 void avltree_remove_node(AVLTree *tree, AVLTreeNode *node);
 
+/**
+ * Remove an entry from a tree, specifying the key of the node to
+ * remove.
+ *
+ * @param tree            The tree.
+ * @param key             The key of the node to remove.
+ * @return                Zero (false) if no node with the specified key was
+ *                        found in the tree, non-zero (true) if a node with
+ *                        the specified key was removed.
+ */
+
+int avltree_remove(AVLTree *tree, void *key);
+
 /**
  * Search an AVL tree for a node with a particular key.  This uses
  * the tree as a mapping.
@@ -228,12 +251,6 @@ AVLTreeNode *avltree_node_parent(AVLTreeNode *node);
 
 int avltree_subtree_height(AVLTreeNode *node);
 
-
-/******************** debug for removal ******************************/
-
-void avltree_print_tree(AVLTree *tree);
-int avltree_check_balanced(AVLTree *tree);
-
 #ifdef __cplusplus
 }
 #endif
