AVL Tree в C с итеративной вставкой - PullRequest
Новая
       34

AVL Tree в C с итеративной вставкой

0 голосов
/ 07 марта 2019

Я кодирую общее дерево AVL как вызов самому себе, и, если я могу сделать это правильно, ресурс для других студентов CS там.

Как обычно, я начал с реализации рекурсивной функции вставки, которая работает. Однако из-за эффективности я пытался реализовать ту же функцию, но итеративно. Я искал в Интернете и нашел много реализаций, но остальная часть кода всегда слишком отличалась от моей, что побудило меня продолжать попытки создания реализации с нуля.

Это соответствующие определенные типы: 

typedef struct info {
    int id;
    char name[200];
} data;

typedef struct avl_node {
    void * data;
    struct avl_node * left;
    struct avl_node * right;
    int height;
} * avl_node_t;

typedef struct avl_tree {
    avl_node_t root;
    int num_nodes;
    int (*less)(const void * first, const void * second);
    int (*key)(const void * data);
} * avl_t;

И вот итеративная функция вставки (которая не работает должным образом): 

avl_node_t
avl_insert(avl_node_t node, void * data)
{
    long key1 = 0, key2 = 0;
    avl_node_t aux = NULL;

    while (1) {
        if (node == NULL) {
            node = avl_node_create(data);
            break;
        }

        key1 = key((void*)&data);
        key2 = key((void*)&(node->data));

        aux = node;

        if (less((void*)&key1, (void*)&key2))
            node = node->left;
        else
            node = node->right;
    }

    if (aux != NULL) {
        if (less((void*)&key1, (void*)&key2))
            aux->right = node;
        else if (less((void*)&key2, (void*)&key1))
            aux->left = node;
    }

    node = avl_balance(node);

    return node;
}

, в котором функция avl_balance определяется следующим образом: 

static short
balance(avl_node_t node)
{
    if (node == NULL)
        return 0;

    return avl_node_height(node->left) - avl_node_height(node->right);
}
static avl_node_t
avl_balance(avl_node_t node)
{
    short balance_factor;

    if (node == NULL)
        return node;

    balance_factor = balance(node);

    if (balance_factor > 1)
        if (balance(node->left) >= 0)
            node = avl_rotRight(node);
        else
            node = avl_rotLeftRight(node);
    else if (balance_factor < -1)
        if (balance(node->right) <= 0)
            node = avl_rotLeft(node);
        else
            node = avl_rotRightLeft(node);
    else
        update_height(node);

    return node;
}

Это код, который я использую для проверки дерева AVL: 

int main()
{
    data d1 = { 1, "we are number one" };
    data d2 = { 2, "boneless pizza" };
    data d3 = { 3, "hehe" };
    data d4 = { 4, "achoo" };
    data d5 = { 5, "I like C" };
    data d6 = { 6, "Assembly is cool too" };
    data d7 = { 7, "SIGSEGV" };

    avl_t tree = avl_create();

    avl_node_t root = tree->root;

    root = avl_insert(root, (void*)&d1);
    traverse(root);
    root = avl_insert(root, (void*)&d2);
    traverse(root);
    root = avl_insert(root, (void*)&d3);
    root = avl_insert(root, (void*)&d4);
    root = avl_insert(root, (void*)&d5);
    root = avl_insert(root, (void*)&d6);
    root = avl_insert(root, (void*)&d7);
    traverse(root);

    free(tree);

    exit(0);
}

, в котором traverse определяется как: 

void visit(void * d)
{
    data * my_data = (data*)d;
    printf("I am element number %d named %s\n", (*my_data).id, (*my_data).name);
    fflush(stdout);
}
void traverse(avl_node_t node)
{
    if (node == NULL)
        return;

    traverse(node->left);
    traverse(node->right);
    visit(node->data);
}

И, наконец, вот что я получаю из этого теста: 

I am element number 1 named we are number one
I am element number 2 named boneless pizza
I am element number 7 named SIGSEGV

Заранее спасибо.

...