平衡二叉搜索树(AVL)C实现

AVL在实际服务端应用中较多见，它的主要好处是原理简单并且具有良好的搜索/插入/删除速度（时间复杂度均为O(logN)).这里贴一个我写的简单实现，其接口如下：

struct node_t {
    struct node_t *lchild, *rchild; /* 分别指向左右子树 */
    int height;                     /* 树的高度 */
    /* 以下为用户数据，根据自己的需要进行修改 */
    int data;
};

/**
 *  向根为tree的AVL树插入数据。
 *
 *  tree指向插入数据前AVL树的根。
 *  node指向包含待插入数据的node_t节点。
 *  compar指向节点之间的比较函数，由用户定义。
 *
 *  返回插入数据后AVL树的根。
 */
struct node_t *avlinsert(struct node_t *tree, struct node_t *node,
                         int(*compar)(const void *, const void *));
/**
 *  从根为tree的AVL树删除数据。
 *
 *  tree指向删除数据前AVL树的根。
 *  node指向包含待匹配数据的node_t节点。
 *  rmnode为一个二次指针，删除成功时*rmnode存放的是被删除节点指针，失败则为NULL。
 *  compar指向节点之间的比较函数，由用户定义。
 *
 *  返回删除数据后AVL树的根。
 */
struct node_t *avlremove(struct node_t *tree, struct node_t *node,
                         struct node_t **rmnode,
                         int(*compar)(const void *, const void *));
/**
 *  从根为tree的AVL树中搜索数据。
 *
 *  tree指向AVL树的根。
 *  node指向包含待匹配数据的node_t节点。
 *  compar指向节点之间的比较函数，由用户定义。
 *
 *  返回匹配数据节点，或者NULL。
 */
struct node_t *avlsearch(struct node_t *tree, struct node_t *node,
                         int(*compar)(const void *, const void *));
/**
 *  从根为tree的AVL树中搜索最小数据节点。
 *
 *  返回最小数据节点，或者NULL（空树）。
 */
struct node_t *avlgetmin(struct node_t *tree);
/**
 *  从根为tree的AVL树中搜索最大数据节点。
 *
 *  返回最大数据节点，或者NULL（空树）。
 */
struct node_t *avlgetmax(struct node_t *tree);

在我的主机（AMD Athlon(tm) XP 2000+/bogomips:3317.76/512MB/FC3)上对1,000,000个随机不重复数据进行测试时其数据如下：

[dgang@localhost avl]$ ./mkrdata 1000000 > data
[dgang@localhost avl]$ ./avltree
For search:
------------------------------
found count = 1000000
------------------------------
insert last time: 4.168155 sec
search last time: 1.847335 sec
remove last time: 4.793462 sec

mkrdata用来生成一个包含1，000，000个32bit不重复整数的文件，其本身实现中也用到了AVL。
然后以生成的1,000,000个整数为关键字逐个插入一颗空AVL树，即构造一颗包含1,000,000节点的AVL树，用时为
    insert last time: 4.168155 sec
接着逐个在树中搜索所有数据，用时为
    search last time: 1.847335 sec
最终逐个删除所有数据，用时为
    remove last time: 4.793462 sec
这个速度与二分搜索里最快的二分搜索数组相比还有一些差距（二分搜苏数组大概是0.6秒左右），但也已经相当快了，而且这个代码本身并没有做细致优化，通过对代码本身优化可以提高一些速度，但应该很有限。而当数据多时加一些前置的散列表将能从很大程度上体高搜索/插入/删除等操作的速度。

代码在这里

文件: avl.tar.gz 大小: 3KB 下载: 下载

编辑 webmaster