C语言实现通用版AVL树

！！！！！！！！！！2018年03月06日有重要更新！！！！！！！！！！！！！，以下为原文：

=========================原文=======================

最近工作中需要用到AVL树，而且需要C语言实现。我在GitHub上找到了一个C++版的，点这里。由于C++的类可以进行运算符重载，重载<和=运算符，所以就是通用的了。C语言没有这么多语法特性，但是有啥是C语言做不到的呢？！我就把这个C++实现改成了C语言实现，而且实现了通用的AVL树。

这里就记录一下，以后可以直接复制粘贴了。

avl.h

#ifndef AVL_H
#define AVL_H

#include <stdlib.h>

// AVL树节点
struct avl_node
{
    void* val;
    ssize_t height;
    struct avl_node* left;
    struct avl_node* right;
};

// 向AVL树插入一个值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待插入的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1。
//   返回：新的AVL树根节点
struct avl_node* avl_insert(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2));

// 从AVL树中删除一个值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待删除的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1。
//   found: 如果找到，则置为1（应事先置为0）
//   返回：新的AVL树根节点
struct avl_node* avl_delete(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* found);

// get 在AVL树中搜索指定值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待插入的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1。
//   返回：如果站到该值，则返回包含该值的树节点，否则返回0
struct avl_node* avl_search(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2));

// 获取指定AVL树中节点总数
//   root: AVL树根节点
size_t avl_node_count(struct avl_node* root);

#endif

avl.c

#include "avl.h"
#include <assert.h>

#define get_height(node) (((node)==0)?(-1):((node)->height))

#define max(a,b) ((a)>(b)?(a):(b))

/* RR(Y rotates to the right):
        k2                 k1
       / \                / \
      k1  Z     ======   X  k2
     / \                    / \
    X   Y                  Y   Z
*/
/*
 Return which the root pointer(at a higher level) should point to
 */
static struct avl_node* rr_rotate(struct avl_node* k2)
{
    assert(k2 != 0);

    struct avl_node* k1 = k2 -> left;
    k2 -> left = k1 -> right;
    k1 -> right = k2;
    k2 -> height = max(get_height(k2 -> left), get_height(k2 -> right)) + 1;
    k1 -> height = max(get_height(k1 -> left), k2 -> height) + 1;
    return k1;
}

/* LL(Y rotates to the left):
        k2                     k1
       / \                    / \
      X  k1       ======     k2  Z
        / \                 / \
        Y  Z               X   Y
 */
static struct avl_node* ll_rotate(struct avl_node* k2)
{
    assert(k2 != 0);

    struct avl_node* k1 = k2 -> right;
    k2 -> right = k1 -> left;
    k1 -> left = k2;
    k2 -> height = max(get_height(k2 -> left), get_height(k2 -> right)) +1;
    k1 -> height = max(get_height(k1 -> right), k2 -> height) +1;
    return k1;
}

/* LR(B rotates to the left, then C rotates to the right):
      k3                       k3                    k2
     / \                      / \                   / \
    k1  D                    k2  D                k1   k3
   / \      ======          / \     ======        / \  / \
  A   k2                   k1  C                 A  B C   D
      / \                 / \
     B  C                A   B
*/
/*
 Return which the root pointer should point to
 */
static struct avl_node* lr_rotate(struct avl_node* k3)
{
    assert(k3 != 0);

    k3 -> left = ll_rotate(k3 -> left);
    return rr_rotate(k3);
}

/* RL(D rotates to the right, then C rotates to the left):
       k3                      k3                       k2
      / \                     / \                      / \
     A  k1                   A   k2                   k3  k1 
        / \      ======          / \        ======    / \ / \
       k2  B                    C   k1               A  C D  B
       / \                         / \
      C   D                       D   B 
 */
static struct avl_node* rl_rotate(struct avl_node* k3)
{
    assert(k3 != 0);

    k3 -> right = rr_rotate(k3 -> right);
    return ll_rotate(k3);
}

/* return which the root pointer(at an outer/higher level) should point to,
   the root_node of AVL tree may change frequently during delete/insert,
   so the Root pointer should point to the REAL root node.
 */
struct avl_node* avl_insert(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2))
{
    assert(comparator != 0);
    
    if(root == 0)
    {
        root = malloc(sizeof(struct avl_node));
        root -> val = val;
        root -> left = 0;
        root -> right = 0;
        root -> height = 0;
        return root;
    }

    if(comparator(val , root -> val) < 0)
        root -> left = avl_insert(root -> left, val, comparator);
    else
        root -> right = avl_insert(root -> right, val, comparator);

    root -> height = max(get_height(root -> left), get_height(root -> right)) + 1;

    ssize_t height_delta= get_height(root -> left) - get_height(root -> right);
    if(height_delta == 2)
    {
        if(comparator(val, root -> left -> val) < 0)
            root = rr_rotate(root);
        else
            root = lr_rotate(root);
    }
    else if(height_delta == -2)
    {
        if(comparator(val, root -> right -> val) < 0)
            root = rl_rotate(root);
        else
            root = ll_rotate(root);
    }
    return root;
}

/* return which the root pointer(at an outer/higher level) should pointer to,
   cause the root_node of AVL tree may change frequently during delete/insert,
   so the Root pointer should point to the REAL root node.
 */
struct avl_node* avl_delete(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* found)
{
    assert(comparator != 0);
    
    if(root == 0)
        return 0;

    int comp = comparator(val, root -> val);
    if(comp == 0)
    {
        if(root -> right == 0)
        {
            struct avl_node* temp = root;
            root = root -> left;
            free(temp);
            if(found != 0)
                (*found) = 1;
            return root;
        }
        else
        {
            struct avl_node* temp = root -> right;
            while(temp -> left)
                temp = temp -> left;
            root -> val = temp -> val;
            root -> right = avl_delete(root -> right, temp -> val, comparator, found);
        }
    }
    else if(comp < 0)
        root -> left = avl_delete(root -> left, val, comparator, found);
    else
        root -> right = avl_delete(root -> right, val, comparator, found);

    root -> height = max(get_height(root -> left), get_height(root -> right)) + 1;

    ssize_t height_delta = get_height(root -> left) - get_height(root -> right);
    if(height_delta == 2)
    {
        if(get_height(root -> left -> left) >= get_height(root -> left -> right))
            root = rr_rotate(root);
        else
            root = lr_rotate(root);
    }
    else if(height_delta == -2)
    {
        if(get_height(root -> right -> right) >= get_height(root -> right -> left))
            root = ll_rotate(root);
        else
            root = rl_rotate(root);
    }
    return root;
}

// get the node that contains the value that equals to the given one
struct avl_node* avl_search(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2))
{
    assert(comparator != 0);

    if(root == 0)
        return 0;

    int comp = comparator(val, root -> val);
    if(comp == 0)
        return root;
    else if(comp < 0)
        return avl_search(root -> left, val, comparator);
    else
        return avl_search(root -> right, val, comparator);
}

// get how many nodes in the tree
size_t avl_node_count(struct avl_node* root)
{
    if(root == 0)
        return 0;
    return 1 + avl_node_count(root -> left) + avl_node_count(root -> right);
}

来个测试：

#include <stdio.h>
#include <string.h>
#include "avl.h"

int compare(const void* v1, const void* v2)
{
    return strcmp((const char*)v1, (const char*)v2);
}

int main()
{
    struct avl_node* root = 0;
    root = avl_insert(root, "anal", compare);
    root = avl_insert(root, "bra", compare);
    root = avl_insert(root, "cock", compare);
    printf("%s\n", root -> val);
    return 0;
}

输出"bra"，所以就知道AVL确实发生了旋转~

==============================2018年03月06日更新=================================

最近的工作中，遇到这样一个需求：当把一个数据插入AVL树中时，可能需要取消插入动作。举个简单的例子：如果需要保证AVL树中元素不重复，那么当插入一个新元素时，在比较器中可能会发现两个元素相等，那么就需要向AVL树报告，取消这次插入动作。

因此需要两个要素：

• 比较器能够向AVL报告取消动作
• 调用者需要能得知动作是完成了还是取消了

代码的改动很简单，与上文代码中的区别我将用红色字体标出。

avl.h

#ifndef AVL_H
#define AVL_H

#include <stdlib.h>

// 如果比较器返回该结果，那么取消动作
#define AVL_CANCEL ((int)123456789)

// AVL树节点
struct avl_node
{
    void* val;
    ssize_t height;
    struct avl_node* left;
    struct avl_node* right;
};

// 向AVL树插入一个值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待插入的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1,
//          如果返回AVL_CANCEL，那么取消插入
//   cancelled: 是否被取消（应事先置为0）
//   返回：新的AVL树根节点
struct avl_node* avl_insert(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* cancelled);

// 从AVL树中删除一个值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待删除的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1,
//          如果返回AVL_CANCEL，那么取消插入
//   cancelled: 是否被取消（应事先置为0）
//   found: 如果找到，则置为1（应事先置为0）
//   返回：新的AVL树根节点
struct avl_node* avl_delete(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* cancelled, int* found);

// get 在AVL树中搜索指定值，使用指定函数进行值与值之间的比较
//   root: AVL树根节点
//   val: 待插入的值
//   comparator: 自定义比较函数：如果v1<v2，返回-1；如果v1=v2，返回0；如果v1>v2，返回1。
//   返回：如果站到该值，则返回包含该值的树节点，否则返回0
struct avl_node* avl_search(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2));

// 获取指定AVL树中节点总数
//   root: AVL树根节点
size_t avl_node_count(struct avl_node* root);

#endif

avl.c

#include <avl.h>
#include <assert.h>

#define get_height(node) (((node)==0)?(-1):((node)->height))

#define max(a,b) ((a)>(b)?(a):(b))

/* RR(Y rotates to the right):
        k2                 k1
        / \                / \
        k1  Z     ======   X  k2
        / \                    / \
    X   Y                  Y   Z
*/
/*
    Return which the root pointer(at a higher level) should point to
    */
static struct avl_node* rr_rotate(struct avl_node* k2)
{
    assert(k2 != 0);

    struct avl_node* k1 = k2 -> left;
    k2 -> left = k1 -> right;
    k1 -> right = k2;
    k2 -> height = max(get_height(k2 -> left), get_height(k2 -> right)) + 1;
    k1 -> height = max(get_height(k1 -> left), k2 -> height) + 1;
    return k1;
}

/* LL(Y rotates to the left):
        k2                     k1
        / \                    / \
        X  k1       ======     k2  Z
        / \                 / \
        Y  Z               X   Y
    */
static struct avl_node* ll_rotate(struct avl_node* k2)
{
    assert(k2 != 0);

    struct avl_node* k1 = k2 -> right;
    k2 -> right = k1 -> left;
    k1 -> left = k2;
    k2 -> height = max(get_height(k2 -> left), get_height(k2 -> right)) +1;
    k1 -> height = max(get_height(k1 -> right), k2 -> height) +1;
    return k1;
}

/* LR(B rotates to the left, then C rotates to the right):
        k3                       k3                    k2
        / \                      / \                   / \
    k1  D                    k2  D                k1   k3
    / \      ======          / \     ======        / \  / \
    A   k2                   k1  C                 A  B C   D
        / \                 / \
        B  C                A   B
*/
/*
    Return which the root pointer should point to
    */
static struct avl_node* lr_rotate(struct avl_node* k3)
{
    assert(k3 != 0);

    k3 -> left = ll_rotate(k3 -> left);
    return rr_rotate(k3);
}

/* RL(D rotates to the right, then C rotates to the left):
        k3                      k3                       k2
        / \                     / \                      / \
        A  k1                   A   k2                   k3  k1 
        / \      ======          / \        ======    / \ / \
        k2  B                    C   k1               A  C D  B
        / \                         / \
        C   D                       D   B 
    */
static struct avl_node* rl_rotate(struct avl_node* k3)
{
    assert(k3 != 0);

    k3 -> right = rr_rotate(k3 -> right);
    return ll_rotate(k3);
}

/* return which the root pointer(at an outer/higher level) should point to,
    the root_node of AVL tree may change frequently during delete/insert,
    so the Root pointer should point to the REAL root node.
    */
struct avl_node* avl_insert(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* cancelled)
{
    assert(comparator != 0);
    
    if(root == 0)
    {
        root = malloc(sizeof(struct avl_node));
        root -> val = val;
        root -> left = 0;
        root -> right = 0;
        root -> height = 0;
        return root;
    }

    int comp = comparator(val , root -> val);
    if(comp == AVL_CANCEL)
    {
        if(cancelled)
            (*cancelled) = 1;
        return root;
    }
    else if(comp < 0)
        root -> left = avl_insert(root -> left, val, comparator, cancelled);
    else
        root -> right = avl_insert(root -> right, val, comparator, cancelled);

    root -> height = max(get_height(root -> left), get_height(root -> right)) + 1;

    ssize_t height_delta= get_height(root -> left) - get_height(root -> right);
    if(height_delta == 2)
    {
        if(comparator(val, root -> left -> val) < 0)
            root = rr_rotate(root);
        else
            root = lr_rotate(root);
    }
    else if(height_delta == -2)
    {
        if(comparator(val, root -> right -> val) < 0)
            root = rl_rotate(root);
        else
            root = ll_rotate(root);
    }
    return root;
}

/* return which the root pointer(at an outer/higher level) should pointer to,
    cause the root_node of AVL tree may change frequently during delete/insert,
    so the Root pointer should point to the REAL root node.
    */
struct avl_node* avl_delete(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2), int* cancelled, int* found)
{
    assert(comparator != 0);
    
    if(root == 0)
        return 0;

    int comp = comparator(val, root -> val);
    if(comp == AVL_CANCEL)
    {
        if(cancelled)
            (*cancelled) = 1;
        return root;
    }
    else if(comp == 0)
    {
        if(root -> right == 0)
        {
            struct avl_node* temp = root;
            root = root -> left;
            free(temp);
            if(found)
                (*found) = 1;
            return root;
        }
        else
        {
            struct avl_node* temp = root -> right;
            while(temp -> left)
                temp = temp -> left;
            root -> val = temp -> val;
            root -> right = avl_delete(root -> right, temp -> val, comparator, cancelled, found);
        }
    }
    else if(comp < 0)
        root -> left = avl_delete(root -> left, val, comparator, cancelled, found);
    else
        root -> right = avl_delete(root -> right, val, comparator, cancelled, found);

    root -> height = max(get_height(root -> left), get_height(root -> right)) + 1;

    ssize_t height_delta = get_height(root -> left) - get_height(root -> right);
    if(height_delta == 2)
    {
        if(get_height(root -> left -> left) >= get_height(root -> left -> right))
            root = rr_rotate(root);
        else
            root = lr_rotate(root);
    }
    else if(height_delta == -2)
    {
        if(get_height(root -> right -> right) >= get_height(root -> right -> left))
            root = ll_rotate(root);
        else
            root = rl_rotate(root);
    }
    return root;
}

// get the node that contains the value that equals to the given one
struct avl_node* avl_search(struct avl_node* root, void* val,
    int (*comparator)(const void* v1, const void* v2))
{
    assert(comparator != 0);

    if(root == 0)
        return 0;

    int comp = comparator(val, root -> val);
    if(comp == 0)
        return root;
    else if(comp < 0)
        return avl_search(root -> left, val, comparator);
    else
        return avl_search(root -> right, val, comparator);
}

// get how many nodes in the tree
size_t avl_node_count(struct avl_node* root)
{
    if(root == 0)
        return 0;
    return 1 + avl_node_count(root -> left) + avl_node_count(root -> right);
}

非常简单吧～