avltree.h

常用的数据结构和算法函数库

/*

Copyright (c) 2005, Simon Howard
All rights reserved.

Redistribution and use in source and binary forms, with or without 
modification, are permitted provided that the following conditions 
are met:

 * Redistributions of source code must retain the above copyright 
   notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright 
   notice, this list of conditions and the following disclaimer in 
   the documentation and/or other materials provided with the 
   distribution.
 * Neither the name of the C Algorithms project nor the names of its 
   contributors may be used to endorse or promote products derived 
   from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
POSSIBILITY OF SUCH DAMAGE.

*/

/** @file avltree.h
 *
 * @brief Balanced binary tree
 *
 * The AVL tree structure is a balanced binary tree which stores 
 * a collection of nodes (see @ref AVLTreeNode).  Each node has
 * a key and a value associated with it.  The nodes are sorted
 * within the tree based on the order of their keys. Modifications
 * to the tree are constructed such that the tree remains 
 * balanced at all times (there are always roughly equal numbers
 * of nodes on either side of the tree).
 *
 * Balanced binary trees have several uses.  They can be used
 * 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 destroy
 * an AVL tree, use @ref avltree_free.
 *
 * To insert a new key-value pair into an AVL tree, use
 * @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.
 *
 * Tree nodes can be queried using the 
 * @ref avltree_node_left_child,
 * @ref avltree_node_right_child,
 * @ref avltree_node_parent,
 * @ref avltree_node_key and
 * @ref avltree_node_value functions.
 */

#ifndef ALGORITHM_AVLTREE_H
#define ALGORITHM_AVLTREE_H

#ifdef __cplusplus
extern "C" {
#endif

/**
 * An AVL tree balanced binary tree.
 *
 * @see avltree_new
 */

typedef struct _AVLTree AVLTree;

/**
 * A node in an AVL tree.
 *
 * @see avltree_node_left_child
 * @see avltree_node_right_child
 * @see avltree_node_parent
 * @see avltree_node_key 
 * @see avltree_node_value
 */

typedef struct _AVLTreeNode AVLTreeNode;

/**
 * Type of function used to compare keys in an AVL tree.
 *
 * @param data1            The first key.
 * @param data2            The second key.
 * @return                 A negative number if data1 should be sorted
 *                         before data2, a positive number if data2 should 
 *                         be sorted before data1, zero if the two keys
 *                         are equal.
 */

typedef int (*AVLTreeCompareFunc)(void *data1, void *data2);

/**
 * Create a new AVL tree.
 *
 * @param compare_func    Function to use when comparing keys in the tree.
 * @return                A new AVL tree.
 */

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.
 *
 * @param tree            The tree.
 * @param key             The key to insert.
 * @param value           The value to insert.
 * @return                The newly created tree node containing the
 *                        key and value.
 */

AVLTreeNode *avltree_insert(AVLTree *tree, void *key, void *value);

/**
 * Remove a node from a tree.
 *
 * @param tree            The tree.
 * @param node            The node to remove
 */

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.
 *
 * @param tree            The AVL tree to search.
 * @param key             The key to search for.
 * @return                The tree node containing the given key, or NULL
 *                        if no entry with the given key is found.
 */

AVLTreeNode *avltree_lookup_node(AVLTree *tree, void *key);

/**
 * Search an AVL tree for a value corresponding to a particular key.
 * This uses the tree as a mapping.  Note that this performs 
 * identically to @ref avltree_lookup_node, except that the value
 * at the node is returned rather than the node itself.
 *
 * @param tree            The AVL tree to search.
 * @param key             The key to search for.
 * @return                The value associated with the given key, or NULL
 *                        if no entry with the given key is found.
 */

void *avltree_lookup(AVLTree *tree, void *key);

/**
 * Find the root node of a tree.
 *
 * @param tree            The tree.
 * @return                The root node of the tree, or NULL if the tree is 
 *                        empty.
 */

AVLTreeNode *avltree_root_node(AVLTree *tree);

/**
 * Retrieve the key for a given tree node.
 *
 * @param node            The tree node.
 * @return                The key to the given node.
 */

void *avltree_node_key(AVLTreeNode *node);

/** 
 * Retrieve the value at a given tree node.
 *
 * @param node            The tree node.
 * @return                The value at the given node.
 */

void *avltree_node_value(AVLTreeNode *node);

/**
 * Find the left child of a given tree node.
 *
 * @param node            The tree node.
 * @return                The left child of the tree node, or NULL if the
 *                        node has no left child.
 */

AVLTreeNode *avltree_node_left_child(AVLTreeNode *node);

/**
 * Find the right child of a given tree node.
 *
 * @param node            The tree node.
 * @return                The right child of the tree node, or NULL if the
 *                        node has no right child.
 */

AVLTreeNode *avltree_node_right_child(AVLTreeNode *node);

/**
 * Find the parent node of a given tree node.
 *
 * @param node            The tree node.
 * @return                The parent node of the tree node, or NULL if 
 *                        this is the root node.
 */

AVLTreeNode *avltree_node_parent(AVLTreeNode *node);

/**
 * Find the height of a subtree.
 *
 * @param node            The root node of the subtree.
 * @return                The height of the subtree.
 */

int avltree_subtree_height(AVLTreeNode *node);

/**
 * Convert the keys in an AVL tree into a C array.  This allows 
 * the tree to be used as an ordered set.
 *
 * @param tree            The tree.
 * @return                A newly allocated C array containing all the keys
 *                        in the tree, in order.  The length of the array
 *                        is equal to the number of entries in the tree
 *                        (see @ref avltree_num_entries).
 */

void **avltree_to_array(AVLTree *tree);

/**
 * Retrieve the number of entries in the tree.
 *
 * @param tree            The tree.
 * @return                The number of key-value pairs stored in the tree.
 */

int avltree_num_entries(AVLTree *tree);

#ifdef __cplusplus
}
#endif

#endif /* #ifndef ALGORITHM_AVLTREE_H */