c++ - 如何在红黑树节点中插入节点？

Question

我在 [github][1] 中找到了这个实现，我做了一些改变，比如向节点添加第二个值，并使用每个左右节点作为指针节点它是树的问题，每当插入节点然后搜索在树中的节点中，它仅在使用 TMapFind 时从第一个指针到最后一个指针迭代树，它调用函数指针 TMapNodeComparison_F 来比较指针。我想知道是什么导致了这个错误，我怀疑这是 TMapInsertNode 检查节点是否为黑色/红色的逻辑？

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>



#define ASSERT_NOT_NULL(x) if(x)
#define ASSERT_NULL(x) if(x ==NULL)
#define ASSERT_NULL_(x,y) if(x== NULL && y==NULL)


typedef struct CByte
{
    unsigned char* value;
    size_t index;
    size_t length;
}BYTES;

//struct Data;
struct Node;
struct TMap;





struct Node
{
    CByte* value;
    size_t index;
    struct  Node* Left;
    struct  Node* Right;
    struct  Node* Parent;
    bool color;
};


typedef int  (*TMapNodeComparison_F) (struct TMap* map, struct Node* a, struct Node* b);
typedef void (*TMapNode_F)     (struct TMap* map, struct Node* node);

struct TMap
{
   struct Node* root;
   size_t TSize;
   TMapNodeComparison_F compareNodeFunction;

};


struct Node* TMapNodeAlloc() 
{
    return (Node*)malloc(sizeof(Node));
}

struct Node* TMapNodeCalloc()
{
  return (Node*)calloc(1,sizeof(Node));
}

struct Node* TMapInitializationNodeTree(struct Node* node,struct CByte* _data)
{
    ASSERT_NOT_NULL (node) 
    {
        node->value = _data;
        std::string s  = reinterpret_cast<char const*>(_data->value);
        std::cout << s << std::endl;
        node->color = 1;//Initialize as Black
        node->Left = node->Right = NULL;
        node->index = _data->index;
       
    }
    return node;
}

struct Node* TMapInitializationCreateNode(CByte* _data)
{
    return TMapInitializationNodeTree(TMapNodeAlloc(), _data);
}

void TMapNodeDeAlloc(struct Node* node)
{
    ASSERT_NOT_NULL(node)
        free(node);
}

int AreNodesRed(struct Node* nodeA, struct Node* nodeB)
{
    return (nodeA && nodeB) ? !nodeA->color && !nodeB->color : 0;
}


static bool TMapIsNodeBlack (struct Node* node)
{
    return node ? node->color == 1 : false;
}
static bool TMapIsNodeRed(struct Node* node)
{
    return node ? !node->color : false;
}
static bool TMapAreNodesBlack(struct Node* nodeA,struct Node* nodeB)
{
    return nodeA && nodeB ? nodeA->color == 1  && nodeB->color ==1 : false;
}


static struct Node* TMapNodeRotateL(struct TMap* map,struct Node* node , int side)
{
    struct Node* blackNode = NULL;

    ASSERT_NOT_NULL (node) 
    {
        blackNode = !side == 0 ? node->Left : node->Right;
       /* blackNode->Left = blackNode->Right = (Node*)calloc(1, sizeof(Node));*/
        !side == 0 ? node->Left : node->Right = side == 0 ? blackNode->Left : blackNode->Right;


        node->color = 0;     //Red
        blackNode->color = 1;//Black


        side == 0 ? blackNode->Left : blackNode->Right = node;
        node->Parent = blackNode;
    }

    return blackNode;
}


static struct Node* TMapNodeRotateR(TMap* map,struct Node* node,int side) 
{
    struct Node* rightNode = NULL;

    ASSERT_NULL(node) 
    {
       

       !side ==0 ?  node->Left :node->Right = TMapNodeRotateL(map,!side == 0 ? node->Left : node->Right,!side);
        rightNode = TMapNodeRotateL(map,node,side);
    }

    return rightNode;
}

int TMapNodeComparison(struct TMap* map, struct Node* a, struct Node* b)
{
    return (a->value > b->value) - (a->value < b->value);
}


void TMapNodeDealloc(struct TMap* map, struct Node* node) 
{

    ASSERT_NOT_NULL (map) 
    {
        ASSERT_NOT_NULL (node) 
        {
            TMapNodeDeAlloc(node);
        }
    }
}


struct TMap* TMapAlloc()
{
    return (TMap*)malloc(sizeof(TMap));
}

struct TMap* TMapInitialize(struct TMap* map, TMapNodeComparison_F node_cmp_cb) 
{
    ASSERT_NOT_NULL (map)
    {
        map->root = NULL;
        map->TSize = 0;
        map->compareNodeFunction = node_cmp_cb ? node_cmp_cb : TMapNodeComparison;
    }
    return map;
}


struct TMap* TMapCreate(TMapNodeComparison_F node_cb) 
{
    return TMapInitialize(TMapAlloc(), node_cb);
}

void TMapDealloc(struct TMap* map, TMapNode_F node_cb)
{
    ASSERT_NOT_NULL(map) 
    {
        ASSERT_NOT_NULL(node_cb)
        {
            struct Node* node = map->root;
            struct Node* save = NULL;

         
            while (node) 
            {
                ASSERT_NULL (node->Left) 
                {

                   
                    save = node->Right;
                    node_cb(map, node);
                    node = NULL;
                }
                else 
                {

                   
                    save = node->Left;
                    node->Left = save->Right;
                    save->Right = node;
                }
                node = save;
            }
        }

        free(map);
    }
}


int
rb_tree_test(struct TMap* map, struct Node* root) 
{
    int lh, rh;

    if (root == NULL)
        return 1;
    else 
    {
        struct Node* ln = root->Left;
        struct Node* rn = root->Right;

        /* Consecutive red links */
        if (TMapIsNodeRed(root))
        {
            if (AreNodesRed(ln,rn)) 
            {
                printf("Red violation");
                return 0;
            }
        }

        lh = rb_tree_test(map, ln);
        rh = rb_tree_test(map, rn);

        /* Invalid binary search tree */
        if
          ((ln != NULL && map->compareNodeFunction(map, ln, root) >= 0)
        || (rn != NULL && map->compareNodeFunction(map, rn, root) <= 0))
        {
            puts("Binary tree violation");
            return 0;
        }

        /* Black height mismatch */
        if (lh != 0 && rh != 0 && lh != rh) 
        {
            puts("Black violation");
            return 0;
        }

        /* Only count black links */
        if (lh != 0 && rh != 0)
            return TMapIsNodeRed(root) ? lh : lh + 1;
        else
            return 0;
    }
}

void* TMapFind(struct TMap* map, CByte* value) 
{
    void* result = NULL;

    ASSERT_NOT_NULL (map) 
    {
        struct Node node;
        node.value = value;


        struct Node* it = map->root;
        int cmp = 0;
        while (it) 
        {
            if ((cmp = map->compareNodeFunction(map, it, &node))) 
            {

                it = cmp < 0   ? it->Right : it->Left;
            }
            else
                break;
        }
        result = it ? it->value : NULL;


    }
    return result;
}

#define CompareANullElement(nonNull,Null) ((!Null || !nonNull)  ? (0) : nonNull==Null)


int TMapInsertNode(struct TMap* self, struct Node* node) 
{
    int result = 0;
    if (self && node) 
    {
        ASSERT_NULL (self->root) 
        {
            self->root = node;
            result = 1;
        }
        else
        {
            struct Node head = { NULL };
            struct Node* g, * t;       
            struct Node* p, * q;       
            int dir = 0, last = 0;

            // Set up our helpers
            t = &head;
            g = p = NULL;
            q = t->Right = self->root;

           

            while (1) 
            {
                ASSERT_NULL (q) 
                {

                    // Insert node at the first null link.
                    p->Left = q = node;
                }
                else if (AreNodesRed(q->Left,q->Right))
                {
                   
                
                    q->color = 0;//red
                    q->Left->color = 1;// black 
                    q->Right->color = 1;// black 
                }

                if (AreNodesRed(q,p)) 
                {



                    int dir2 = CompareANullElement(t->Right,g);
                    
                    if (CompareANullElement(q,(last  == 0 ? p->Left : p->Right)))
                    {
                        t->Right = TMapNodeRotateL(self,g,!last);
                    }
                    else 
                    {
                        t->Left = TMapNodeRotateR(self,g,!last);
                    }
                }

                // Stop working if we inserted a node. This
                // check also disallows duplicates in the tree
                if (self->compareNodeFunction(self, q, node) == 0) 
                {
                    break;
                }

                last = dir;
                dir = self->compareNodeFunction(self, q, node) < 0;

                // Move the helpers down
                if (g != NULL) 
                {
                    t = g;
                }

                g = p, p = q;

                q = dir ==0 ? q->Left : q->Right;
            }

            // Update the root (it may be different)
            self->root = head.Right;
        }

        // Make the root black for simplified logic
        self->root->color = 1;
        ++self->TSize;
    }

    return 1;
}

int TMapInsert(struct TMap* map, CByte* value) 
{
    return TMapInsertNode(map, TMapInitializationCreateNode(value));
}

int TMapRemoveFrom(struct TMap* map, CByte* value, TMapNode_F node_cb)
{
    ASSERT_NOT_NULL (map->root)
    {
        struct Node head = { 0 }; 
        struct Node node;
        node.value = value ; 
        struct Node* q, * p, * g;
        struct Node* f = NULL;  
        int dir = 1;

        q = &head;
        g = p = NULL;
        q->Right = map->root;

        
        while ((dir == 0 ? q->Left : q->Right) != NULL) 
        {
            int last = dir;

        
            g = p, p = q;
            q = dir == 0 ? q->Left : q->Right;
            dir = map->compareNodeFunction(map, q, &node) < 0;

           
            if (map->compareNodeFunction(map, q, &node) == 0) 
            {
                f = q;
            }

            // Push the red node down with rotations and color flips
            if (TMapIsNodeBlack(q) && TMapIsNodeBlack(dir == 0 ? q->Left : q->Right)) 
            {
                if (TMapIsNodeRed(!dir == 0 ? q->Left : q->Right))
                {
                    p = last == 0 ? p->Left : p->Right = TMapNodeRotateL(map,q,dir);
                }
                else if (TMapIsNodeBlack(!dir == 0 ? q->Left : q->Right))
                {
                    struct Node* s = !last == 0 ? p->Left : p->Right;
                    if (s) 
                    {
                        if (TMapAreNodesBlack(!last == 0 ? s->Left : s->Right,last == 0 ? s->Left : s->Right)) 
                        {

                            // Color flip
                            p->color = 1;
                            s->color = 0;
                            q->color = 0;
                        }
                        else 
                        {
                            int dir2 = g->Right == p;
                            if (TMapIsNodeRed(last == 0 ? s->Left : s->Right)) //check for red
                            {
                                dir2 == 0 ? s->Left : s->Right  = TMapNodeRotateR(map,p,last);
                            }
                            else if (TMapIsNodeBlack((last != 0 ? s->Left : s->Right)))
                            {
                                dir2 == 0 ? g->Left: g->Right = TMapNodeRotateL(map,p,last);
                            }

                            // Ensure correct coloring
                            q->color = dir2 == 0 ? g->Left->color  : g->Right->color = 0;
                            dir2==0 ?   g->Left->Left->color : g->Right->Left->color = 1;
                            dir2 == 0 ? g->Left->Right->color :  g->Right->Right->color = 1;
                        }
                    }
                }
            }
        }

        // Replace and remove the saved node
        ASSERT_NOT_NULL (f) 
        {
            CByte* tmp = f->value;
            f->value = q->value;
            q->value = tmp;

            p->Right == q ?  p->Right : p->Left =  ((q->Left == NULL) ?  q->Right: q->Left);

            ASSERT_NOT_NULL (node_cb) 
            {
                node_cb(map, q);
            }
            q = NULL;
        }

        // Update the root (it may be different)
        map->root = head.Right;

        // Make the root black for simplified logic
        if (map->root != NULL) 
        {
            map->root->color = 1;
        }

        --map->TSize;
    }
    return 1;
}

int TMapRemoveTree(struct TMap* map, CByte* value)
{
    int result = 0;
    ASSERT_NOT_NULL (map)
    {
        result = TMapRemoveFrom(map, value, TMapNodeDealloc);
    }
    return result;
}

size_t TMapGetSize(struct TMap* map) 
{
    size_t result = 0;

    ASSERT_NOT_NULL(map)
    {
        result = map->TSize;
    }

    return result;
}



int my_cmp_cb(struct TMap* self, struct Node* node_a, struct Node* node_b)
{
    BYTES* a = (BYTES*) node_a->value;
    BYTES* b = (BYTES*) node_b->value;
    return  (a->value > b->value) - (a->value < b->value);
}
int main()
{
    int t = true;
    int d,c = 1;
    (t ? d : c) = 2;

    struct TMap* tree =  TMapCreate(my_cmp_cb);
    std::cout << sizeof(*tree) << std::endl;


    ASSERT_NOT_NULL (tree) 
    {

        BYTES* bytes = (BYTES*)calloc(1000,sizeof(BYTES));
        std::stringstream ss;
        // Use the tree here...

        
        for (int i = 0; i < 1000; i++) 
        {
            // Default insert, which allocates internal rb_nodes for you.
            ss << i;
            auto message = std::string("Hello " + ss.str());
            unsigned char* val = new unsigned char[message.length() + 1];

            strcpy((char*)val, message.c_str());

            bytes[i].value = val;
            bytes[i].index = i;
            bytes[i].length = sizeof(message) / sizeof(unsigned char*);
            TMapInsert(tree, &bytes[i]);
            ss.str("");
            ss.clear();
        }
        std::string str ="Hello 2";

         BYTES b { (unsigned char*)str.c_str(), 2, 8 };
        // To f

        BYTES* f = (BYTES*)TMapFind(tree, &b);
        
        
        
        
        
        
        if (f) 
        {
            fprintf(stdout, "found BYTES(value = %s, index = %ull, length = %ull )\n", f->value,f->index,f->length);
        }
        else {
            printf("not found\n");
        }

        TMapDealloc(tree, NULL);
    }
    
}


  [1]: https://github.com/mirek/rb_tree/blob/master/rb_tree.c

标签： c++calgorithmdata-structuresred-black-tree