C Árvore Rubro Negra LLRB

[Unvolk]

Estou tentando implementar uma árvore rubro negra caída para a esquerda utilizando um material disponível no GeeksforGeeks. O programa deve ler um sequência de números inteiros positivos e construir a árvore com eles. Depois, ler uma nova sequência, na qual os números que não forem encontrados devem ser inseridos na árvore. No entanto, para a entrada {6, 4, 3, 2, 1, 5, 7, 8, -1} a árvore fica 4(2(1()3())6(5()8(7()))) ao invés de 4(2(1()3())6(5()7(8()))), e daí pra frente o balanceamento fica todo errado... Não consegui identificar qual é o problema.

 

[Matheus Maldi]

Sem o código fica difícil, mas não iria analisar seu código, rbtree é difícil.

 

Vou deixar a minha implementação

 

//  rbtree.h
#ifndef _RBTREE_H_
#define _RBTREE_H_
#if __cplusplus
extern "C"
{
#endif

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define BLACK (true)
#define RED   (false)
typedef int (*compare_func)(const void*, const void*);
typedef int rbtree_status;

struct rbnode
{
    bool color;
    struct rbnode* left;
    struct rbnode* right;
    struct rbnode* parent;   
};

struct rbtree
{
    struct rbnode* root;
    size_t element_size;
    size_t length;
    compare_func cmp;
};

void           rbtree_ctor    (struct rbtree* tree, size_t element_size, compare_func cmp);
void           rbtree_dtor    (struct rbtree* tree);
size_t         rbtree_length  (struct rbtree* tree);
void*          rbtree_lookup  (struct rbtree* tree, void* element);
rbtree_status  rbtree_insert  (struct rbtree* tree, void* element);
void           rbtree_delete  (struct rbtree* tree, void* element);

static inline
bool rbnode_color(struct rbnode* node)
{
    return node == NULL ? BLACK : node->color;
}

static inline
void* rbnode_get_data_address(struct rbnode* node)
{
    return &node[1];
}

static
struct rbnode* rbnode_new(size_t element_size, void* element)
{
    struct rbnode* node = (struct rbnode*)calloc(1, sizeof(struct rbnode) + element_size);
    if (node == NULL)
        return NULL;

    void* target = rbnode_get_data_address(node);
    memcpy(target, element, element_size);
    return node;
}

static
void rbnode_free(struct rbnode* node)
{
    if (node != NULL)
    {
        rbnode_free(node->left);
        rbnode_free(node->right);
        free(node);
    }
}

static inline
struct rbnode* rbnode_grandparent(struct rbnode* node)
{
    return node->parent->parent;
}

static inline
struct rbnode* rbnode_sibling(struct rbnode* node)
{
    return node == node->parent->left ? node->parent->right : node->parent->left;
}

static inline
struct rbnode* rbnode_uncle(struct rbnode* node)
{
    return rbnode_sibling(node->parent);
}

static
struct rbnode* rbnode_maximum(struct rbnode* node)
{
    while (node->right != NULL)
        node = node->right;
    return node;
}

static inline
struct rbnode* rbnode_lookup(struct rbtree* tree, void* element, compare_func cmp)
{
    struct rbnode* node = tree->root;
    while (node != NULL)
    {
        int result = cmp(element, rbnode_get_data_address(node));
        if (result == 0)
            return node;
        else if (result < 0)
            node = node->left;
        else
            node = node->right;
    }
    return node;
}

static inline
void replace_node(struct rbtree* tree, struct rbnode* old_node, struct rbnode* new_node)
{
    if (old_node->parent == NULL)
        tree->root = new_node;
    else if (old_node == old_node->parent->left)
        old_node->parent->left = new_node;
    else
        old_node->parent->right = new_node;
    
    if (new_node != NULL)
        new_node->parent = old_node->parent;
}

static inline
void rotate_left(struct rbtree* tree, struct rbnode* node)
{
    struct rbnode* right = node->right;
    replace_node(tree, node, right);
    node->right = right->left;
    if (right->left != NULL)
        right->left->parent = node;
    
    right->left = node;
    node->parent = right;
}

static inline
void rotate_right(struct rbtree* tree, struct rbnode* node)
{
    struct rbnode* left = node->left;
    replace_node(tree, node, left);
    node->left = left->right;
    if (left->right != NULL)
        left->right->parent = node;
    
    left->right = node;
    node->parent = left;
}

static void insert_case_1(struct rbtree* tree, struct rbnode* node);
static void insert_case_2(struct rbtree* tree, struct rbnode* node);
static void insert_case_3(struct rbtree* tree, struct rbnode* node);
static void insert_case_4(struct rbtree* tree, struct rbnode* node);
static void insert_case_5(struct rbtree* tree, struct rbnode* node);

static
void insert_case_1(struct rbtree* tree, struct rbnode* node)
{
    if (node->parent == NULL)
        node->color = BLACK;
    else 
        insert_case_2(tree, node);
}

static
void insert_case_2(struct rbtree* tree, struct rbnode* node)
{
    if (rbnode_color(node->parent) == BLACK)
        return;
    else
        insert_case_3(tree, node);
}

static
void insert_case_3(struct rbtree* tree, struct rbnode* node)
{
    if (rbnode_color(rbnode_uncle(node)) == RED)
    {
        node->parent->color = BLACK;
        rbnode_uncle(node)->color = BLACK;
        rbnode_grandparent(node)->color = RED;
        insert_case_1(tree, rbnode_grandparent(node));
    }
    else
        insert_case_4(tree, node);
}

static
void insert_case_4(struct rbtree* tree, struct rbnode* node)
{
    if (node == node->parent->right && node->parent == rbnode_grandparent(node)->left)
    {
        rotate_left(tree, node->parent);
        node = node->left;
    }
    else if (node == node->parent->left && node->parent == rbnode_grandparent(node)->right)
    {
        rotate_right(tree, node->parent);
        node = node->right;
    }
    insert_case_5(tree, node);
}

static
void insert_case_5(struct rbtree* tree, struct rbnode* node)
{
    node->parent->color = BLACK;
    rbnode_grandparent(node)->color = RED;
    if (node == node->parent->left && node->parent == rbnode_grandparent(node)->left)
        rotate_right(tree, rbnode_grandparent(node));
    else
        rotate_left(tree, rbnode_grandparent(node));
}

void rbtree_ctor(struct rbtree* tree, size_t element_size, compare_func cmp)
{
    tree->root = NULL;
    tree->element_size = element_size;
    tree->length = 0;
    tree->cmp = cmp;
}

void rbtree_dtor(struct rbtree* tree)
{
    rbnode_free(tree->root);
}

size_t rbtree_length(struct rbtree* tree)
{
    return tree->length;
}

rbtree_status rbtree_insert(struct rbtree* tree, void* element)
{
    struct rbnode* inserted_node = rbnode_new(tree->element_size, element);
    if (inserted_node == NULL)
        return ENOMEM;
    if (tree->root == NULL)
        tree->root = inserted_node;
    else
    {
        struct rbnode* n = tree->root;
        while (true)
        {
            void* target = rbnode_get_data_address(n);
            int result = tree->cmp(element, target);
            if (result == 0)
            {
                rbnode_free(inserted_node);
                memcpy(target, element, tree->element_size);
                return EXIT_SUCCESS;
            }
            else if (result < 0)
            {
                if (n->left == NULL)
                {
                    n->left = inserted_node;
                    break;
                }
                else
                    n = n->left;
            }
            else
            {
                if (n->right == NULL)
                {
                    n->right = inserted_node;
                    break;
                }
                else
                    n = n->right;
            }
        }
        inserted_node->parent = n;
    }
    insert_case_1(tree, inserted_node);
    tree->length++;
    return EXIT_SUCCESS;
}

void* rbtree_lookup(struct rbtree* tree, void* element)
{
    struct rbnode* node = rbnode_lookup(tree, element, tree->cmp);
    return node == NULL ? NULL : rbnode_get_data_address(node);
}

static void delete_case1(struct rbtree* tree, struct rbnode* node);
static void delete_case2(struct rbtree* tree, struct rbnode* node);
static void delete_case3(struct rbtree* tree, struct rbnode* node);
static void delete_case4(struct rbtree* tree, struct rbnode* node);
static void delete_case5(struct rbtree* tree, struct rbnode* node);
static void delete_case6(struct rbtree* tree, struct rbnode* node);

void rbtree_delete(struct rbtree* tree, void* element)
{
    struct rbnode* node = rbnode_lookup(tree, element, tree->cmp);
    if (node == NULL)
        return;
    if (node->left != NULL && node->right != NULL)
    {
        struct rbnode* pred = rbnode_maximum(node->left);
        memcpy(rbnode_get_data_address(node), rbnode_get_data_address(pred), tree->element_size);
        node = pred;
    }
    struct rbnode* child = node->right == NULL ? node->left : node->right;
    if (rbnode_color(node) == BLACK)
    {
        node->color = rbnode_color(child);
        delete_case1(tree, node);
    }
    replace_node(tree, node, child);
    if (node->parent == NULL && child != NULL)
        child->color = BLACK;
    free(node);

    tree->length--;
}

static void delete_case1(struct rbtree* tree, struct rbnode* node)
{
    if (node->parent == NULL)
        return;
    else
        delete_case2(tree, node);
}

static void delete_case2(struct rbtree* tree, struct rbnode* node)
{
    if (rbnode_color(rbnode_sibling(node)) == RED)
    {
        node->parent->color = RED;
        rbnode_sibling(node)->color = BLACK;
        if (node == node->parent->left)
            rotate_left(tree, node->parent);
        else
            rotate_right(tree, node->parent);
    }
    delete_case3(tree, node);
}

static void delete_case3(struct rbtree* tree, struct rbnode* node)
{
    if (rbnode_color(node->parent) == BLACK &&
        rbnode_color(rbnode_sibling(node)) == BLACK &&
        rbnode_color(rbnode_sibling(node)->left) == BLACK &&
        rbnode_color(rbnode_sibling(node)->right) == BLACK)
    {
        rbnode_sibling(node)->color = RED;
        delete_case1(tree, node->parent);
    }
    else
        delete_case4(tree, node);
}

static void delete_case4(struct rbtree* tree, struct rbnode* node)
{
    if (rbnode_color(node->parent) == RED &&
        rbnode_color(rbnode_sibling(node)) == BLACK &&
        rbnode_color(rbnode_sibling(node)->left) == BLACK &&
        rbnode_color(rbnode_sibling(node)->right) == BLACK)
    {
        rbnode_sibling(node)->color = RED;
        node->parent->color = BLACK;
    }
    else
        delete_case5(tree, node);
}

static void delete_case5(struct rbtree* tree, struct rbnode* node)
{
    if (node == node->parent->left &&
        rbnode_color(rbnode_sibling(node)) == BLACK &&
        rbnode_color(rbnode_sibling(node)->left) == RED &&
        rbnode_color(rbnode_sibling(node)->right) == BLACK)
    {
        rbnode_sibling(node)->color = RED;
        rbnode_sibling(node)->left->color = BLACK;
        rotate_right(tree, rbnode_sibling(node));
    }
    else if (node == node->parent->right &&
             rbnode_color(rbnode_sibling(node)) == BLACK &&
             rbnode_color(rbnode_sibling(node)->right) == RED &&
             rbnode_color(rbnode_sibling(node)->left) == BLACK)
    {
        rbnode_sibling(node)->color = RED;
        rbnode_sibling(node)->right->color = BLACK;
        rotate_left(tree, rbnode_sibling(node));
    }
    delete_case6(tree, node);
}

static void delete_case6(struct rbtree* tree, struct rbnode* node)
{
    rbnode_sibling(node)->color = rbnode_color(node->parent);
    node->parent->color = BLACK;
    if (node == node->parent->left)
    {
        rbnode_sibling(node)->right->color = BLACK;
        rotate_left(tree, node->parent);
    }
    else
    {
        rbnode_sibling(node)->left->color = BLACK;
        rotate_right(tree, node->parent);
    }
}

#if __cplusplus
}
#endif
#endif

 

Exemplo de uso para seus números:

 

#include "include/rbtree.h"

int intcmp(const void *vl, const void *vr)
{
    int lhs = *(int*)vl;
    int rhs = *(int*)vr;
    if (lhs > rhs)
        return 1;
    if (lhs < rhs)
        return -1;
    return 0;
}

void walk_node(struct rbnode *node, int depth)
{
    if (node)
    {
        walk_node(node->left, depth + 1);
        
        int node_value = *(int*)rbnode_get_data_address(node);
        printf("Profundidade %d: %d\n", depth, node_value);

        walk_node(node->right, depth + 1);
    }
}

void walk_tree(struct rbtree *tree)
{
    walk_node(tree->root, 0);
}

int main()
{
    struct rbtree tree;
    rbtree_ctor(&tree, sizeof(int), intcmp);
    
#define VET_LEN 8
    int vet[VET_LEN] = { 6, 4, 3, 2, 1, 5, 7, 8 };

    for (int i = 0; i < VET_LEN; i++)
        rbtree_insert(&tree, &vet[i]); 

    walk_tree(&tree);
    //             4                
    //        2         6                
    //      1   3     5   7          
    //                      8        
                                 

    rbtree_dtor(&tree);

    return 0;
}

 

E teste da minha implementação da arvore

 

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

int intcmp(const void *vl, const void *vr)
{
    int lhs = *(int*)vl;
    int rhs = *(int*)vr;
    if (lhs > rhs)
        return 1;
    if (lhs < rhs)
        return -1;
    return 0;
}

// 1. Each node is either red or black.
static void verify_property_1(struct rbnode* node);

// 2. The root is black
static void verify_property_2(struct rbnode* root);

// 3. All leaves (NULL) are black.
static void verify_property_3();

// 4. If a node is red, then both its children are black.
static void verify_property_4(struct rbnode* node);

// 5. Every path from a given node to any of its descendant 
// NULL nodes goes through the same number of black nodes.
static void verify_property_5_helper(struct rbnode* node, int black_count, int* path_black_count);
static void verify_property_5(struct rbnode* root);

static void verify_properties(struct rbtree* tree);

int main()
{
    struct rbtree tree;
    rbtree_ctor(&tree, sizeof(int), intcmp);
    verify_properties(&tree);
 
    size_t len = 0;
    for (int i = 0; i < 100; i += 2)
    {
        rbtree_insert(&tree, &i);
        verify_properties(&tree);
        len++;
    }
    assert(rbtree_length(&tree) == len);

    for (int i = 99; i > 0; i -= 2)
    {
        rbtree_insert(&tree, &i);
        verify_properties(&tree);
        len++;
    }
    assert(rbtree_length(&tree) == len);

    for (int i = 99; i >= 0; i--)
    {
        rbtree_delete(&tree, &i);
        len--;
    }
    assert(rbtree_length(&tree) == len);

    rbtree_dtor(&tree);

    return 0;
}

// 1. Each node is either red or black.
static void verify_property_1(struct rbnode* node)
{
    assert(rbnode_color(node) == RED || rbnode_color(node) == BLACK);
    if (node == NULL)
        return;
    verify_property_1(node->left);
    verify_property_1(node->right);
}

// 2. The root is black
static void verify_property_2(struct rbnode* root)
{
    assert(rbnode_color(root) == BLACK);
}

// 3. All leaves (NULL) are black.
static void verify_property_3()
{
    struct rbnode* node = NULL;
    assert(rbnode_color(node) == BLACK);
}

// 4. if a node is red, then both its children are black.
static void verify_property_4(struct rbnode* node)
{
    if (rbnode_color(node) == RED)
    {
        assert (rbnode_color(node->left)   == BLACK);
        assert (rbnode_color(node->right)  == BLACK);
        assert (rbnode_color(node->parent) == BLACK);
    }
    if (node == NULL)
        return;
    verify_property_4(node->left);
    verify_property_4(node->right);
}

// 5. Every path from a given node to any of its descendant 
// NULL nodes goes through the same number of black nodes.
static void verify_property_5_helper(struct rbnode* node, int black_count, int* path_black_count)
{
    if (rbnode_color(node) == BLACK)
        black_count++;
    
    if (node == NULL)
    {
        if (*path_black_count == -1)
            *path_black_count = black_count;
        else
            assert(black_count == *path_black_count);
        
        return;
    }
    verify_property_5_helper(node->left,  black_count, path_black_count);
    verify_property_5_helper(node->right, black_count, path_black_count);
}

// 5. Every path from a given node to any of its descendant 
// NULL nodes goes through the same number of black nodes.
static void verify_property_5(struct rbnode* root)
{
    int black_count_path = -1;
    verify_property_5_helper(root, 0, &black_count_path);
}

static void verify_properties(struct rbtree* tree)
{
    verify_property_1(tree->root);
    verify_property_2(tree->root);
    verify_property_3();
    verify_property_4(tree->root);
    verify_property_5(tree->root);
}

 

Está arvore foi escrita com base neste código:

https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C)

 

[Unvolk]

@Matheus Maldi Erro meu mesmo não ter colocado, desculpe. Mas valeu mesmo, vai ser de grande ajuda nos estudos!