c - AVL 树平衡 - C

Question

我一直在尝试用 C 编写一个简单的 AVL 树实现。它也支持重复值。一切似乎都很好，但时不时地我会得到一棵不平衡的树。对我来说，轮换功能似乎可以正常工作。我认为高度检查有问题，但我似乎找不到问题。

我刚刚从插入得到的树是不平衡的，所以插入是有问题的。然后，在此之前，删除后树通常是不平衡的。不过，它有时会得到适当的平衡，我似乎无法确定是如何平衡的。

这个实现的代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

#define SPACE_PER_NODE 2
#define MAX(x, y) (x) > (y) ? (x) : (y)


enum delete_flags {
    DELETE_NO_FORCE,
    DELETE_FORCE
};

typedef unsigned int uint;

struct tree_elem {
    int data;
    uint dup_count;
    int height;
    struct tree_elem* left;
    struct tree_elem* right;
};

typedef struct tree_elem node;

node* create_bst();
void insert(node**, int);
void delete_elem(node**, int, uint);
node* search(node*, int);
node* get_parent(node*, node*);
node* find_min(node*);
node* get_successor(node*, node*);
uint max_depth(node*);
void display_helper(node*, int);
void display_tree(node*);
int get_height(node*);
void rotate_once_left(node**);
void rotate_once_right(node**);
void rotate_twice_left(node**);
void rotate_twice_right(node**);

void* s_malloc (const uint t) {
    void* p = malloc(t);
    if(!p) {
        printf("Out of memory.\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

void s_free (void* p) {
    if(!p) {
        printf("Error: Tried to free NULL ptr.\n");
        exit(EXIT_FAILURE);     
    }
    else
        free(p);
}

node* create_bst(int data) {
    node* tree = (node*) s_malloc(sizeof(node));
    tree->left = tree->right = NULL;
    tree->data = data;
    return tree;
}

void insert(node** t, int val) {
    if(!(*t)) {
        *t = (node*) s_malloc(sizeof(node));
        (*t)->data = val;
        (*t)->left = (*t)->right = NULL;
        (*t)->dup_count = 0;
        (*t)->height = 0;
        return;
    }
    if((*t)->data < val) {
        insert(&(*t)->right, val);

        if(get_height((*t)->right) - get_height((*t)->left) >= 2) {
            if((*t)->right->data < val)
                rotate_once_right(&(*t));
            else if((*t)->right->data > val)
                rotate_twice_right(&(*t));
        }
    }
    else if((*t)->data > val) {
        insert(&(*t)->left, val);

        if(get_height((*t)->left) - get_height((*t)->right) >= 2) {
            if((*t)->left->data > val)
                rotate_once_left(&(*t));
            else if((*t)->left->data < val)
                rotate_twice_left(&(*t));
        }
    }
    else {
        ++(*t)->dup_count;
        return;                                                             // this is important! if there are duplicates, they might cause an unwanted height change!
    }
    (*t)->height = MAX(get_height((*t)->left), get_height((*t)->right)) + 1;
}

node* get_successor(node* t, node* s) {
    if(s->right)
        return find_min(s->right);
    node* suc = NULL;
    node* temp = t;
    // Start from root and search for successor in the tree
    while (temp) {
        if (s->data < temp->data) {
            suc = temp;
            temp = temp->left;
        }
        else if (s->data > temp->data)
            temp = temp->right;
        else
           break;
    }
    return suc;
}

void free_tree (node* t) {
    if (!t)
        return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

node* search(node* t, int val) {
    if(!t)
        return NULL;
    if(t->data == val)
        return t;
    else if(t->data < val)
        return search(t->right, val);
    return search(t->left, val);
}

node* find_min(node* t) {
    node* temp = t;
    while(temp->left)
        temp = temp->left;
    return temp;
}

uint max_depth(node* t) {
   if (!t)
       return 0;
   int ldepth = max_depth(t->left);
   int rdepth = max_depth(t->right);
   if (ldepth > rdepth)
       return ldepth + 1;
   return rdepth + 1;
}

void display_helper(node* t, int spaces) {
    int width = ceil(log10(max_depth(t)+0.01)) + 2;
    wchar_t* sp64 = L"                                                                ";
    if (!t) {
        wprintf(L"\n");
        return;
    }
    display_helper(t->right, spaces + width);
    wprintf(L"%*.*s%d\n", 0, spaces, sp64, t->data);
    display_helper(t->left, spaces + width);
}

void display_tree(node* t) {
    if(t)
        display_helper(t, SPACE_PER_NODE);
}

int get_height(node* t) {
    if(!t)
        return 0;
    return t->height;
}

void rotate_once_left(node** k1) {
    node* temp = (*k1)->left;
    (*k1)->left = temp->right;
    temp->right = *k1;

    (*k1)->height = MAX(get_height((*k1)->left), get_height((*k1)->right)) + 1;
    temp->height = MAX(get_height(temp->left), (*k1)->height) + 1;

    *k1 = temp;
}


void rotate_once_right(node** k1) {
    node* temp = (*k1)->right;
    (*k1)->right = temp->left;
    temp->left = *k1;

    (*k1)->height = MAX(get_height((*k1)->left), get_height((*k1)->right)) + 1;
    temp->height = MAX(get_height(temp->right), (*k1)->height) + 1;

    *k1 = temp;
}

void rotate_twice_left(node** k1) {
    rotate_once_right(&(*k1)->left);
    rotate_once_left(k1);
}

void rotate_twice_right(node** k1) {
    rotate_once_left(&(*k1)->right);
    rotate_once_right(k1);
}

int main() {
    srand(time(NULL));
    node* tree = create_bst(rand() % 15 + 1);
    for(uint i = 0; i < 14; ++i) {
        int elem;
        // create unique elements from 1 to 20.
        do {
            elem = rand() % 15 + 1;
        } while (search(tree, elem));
        insert(&tree, elem);
    }
    display_tree(tree);
    int input;
    do {
        printf("Enter value to delete: ");
        scanf("%d", &input);
        delete_elem(&tree, input, DELETE_NO_FORCE);
        display_tree(tree);
    } while(input != -1);
    return 0;
}

Answer 1

一个地方是你的 MAX 宏。

MAX(get_height((*t)->left), get_height((*t)->right)) + 1;

可能不会计算您认为它所做的事情。

在当今这个时代，当编译器以如此沉着的方式内联时，您不应该使用宏来进行这种计算。这不仅不正确，而且几乎可以肯定效率较低。

我将在这里重复我在评论中所说的话:您应该认真考虑测试驱动开发。编写一个谓词来检查给定树是否满足 AVL 条件，包括它是否是有效的 BST。现在将项目添加到空树并在每个项目之后运行谓词。当它报告树不是 AVL 时，您将能够看到哪里出了问题。如果没有，您将更有信心您的代码按预期工作。

编辑

好的，手动展开宏(添加一些空格):

(get_height((*t)->left)) > (get_height((*t)->right)) 
    ? (get_height((*t)->left))
    : (get_height((*t)->right)) + 1;

+ 1 只影响 else 分支。您需要一组额外的括号才能获得正确答案。

此外，高度被计算了两次。使用函数，它只会发生一次。诚然，积极的优化器也可能会消除重复计算，但这种优化比仅仅内联 max() 函数要复杂得多，因此也更脆弱。为什么使用宏来使编译器的工作更难？