红黑树实现

Question

我想要一些关于我的红黑树实现的反馈。一切都很好。我已经调试了这个，它看起来很好，但是我可能错过了一些东西。

基本上，这是一棵红色的黑树，它将字符串作为键存储，而包含这些字符串的段落作为值存储。由于这些键可以重复使用，所以它们也形成了一个链接列表。

    TNODE *tree_add(TNODE *root, const KEY k, const VALUE v) {
        LNODE *lnode = NULL;
        if (root == NULL) {
                TNODE *node = talloc(k);
                lnode = lalloc(v);
                node->head = lnode;
                node->tail = lnode;
                node->is_red = true;
                return node;
        }
        if (strcmp(k, root->key) < 0) { 
                root->left = tree_add(root->left, k, v);
        } else if (strcmp(k, root->key) > 0) {  
                root->right = tree_add(root->right, k, v);
        } else {
                if (strcmp(k, root->key) == 0) {
                        lnode = lalloc(v);
                        root->tail->next = lnode;
                        root->tail = lnode;
                        root->tail->next = NULL;
                }
        }
        if (is_red(root->right) && !is_red(root->left)) {
                root = rotate_left(root);
        }
        if (is_red(root->left) && is_red(root->left->left)) {
                root = rotate_right(root);
        }
        if (is_red(root->left) && is_red(root->right)) {
                flip_colors(root);
        }
        return root;

}

以下是TNODE和LNODE：

    // LNODE is the data structure for a singly linked list.
typedef struct lnode {
  VALUE val;          // A pointer to the value stored in the linked list.
  struct lnode *next; // Pointer to the next item in the list; it should be NULL if there is no successor.
} LNODE;

typedef struct tnode {
  KEY key;             // Search key for this binary search tree node.
  struct tnode *right; // Right child.
  struct tnode *left;  // Left child.

  LNODE *head; // Head of the linked list storing the values for the search key.
  LNODE *tail; // Tail of the linked list storing the values for the search key.

  bool is_red; // Flag use only in red-black trees to denote redness.
} TNODE;

以下是一些更多的功能: TALLOC、LALLOC和rotate

    TNODE *talloc(const KEY k) {
        TNODE *tnode = malloc(sizeof(TNODE));
        if (tnode == NULL) {
                return NULL;
        }
        tnode->key = k;
        tnode->is_red = false;
        tnode->head = NULL;
        tnode->tail = NULL;
        tnode->right = NULL;
        tnode->left = NULL;
        return tnode;
}

LNODE *lalloc(const VALUE v) {
        LNODE *lnode = malloc(sizeof(LNODE));
        if (lnode == NULL) {
                return NULL;
        }
        lnode->val = v;
        lnode->next = NULL;
        return lnode;
}

TNODE *rotate_left(TNODE *h) { 
        TNODE *x = h->right;
        h->right = x->left;
        x->left = h;
        x->is_red = h->is_red;
        h->is_red = true;
        return x;

}

TNODE *rotate_right(TNODE *h) { 
        TNODE *x = h->left;
        h->left = x->right;
        x->right = h;
        x->is_red = h->is_red;
        h->is_red = true;
        return x;
}

void flip_colors(TNODE *h) { 
        h->is_red = true;
        h->left->is_red = false;
        h->right->is_red = false;
}

Answer 1

实现问题：

我会给strcmp(k, root->key)打一次电话：

int cmpval;
if (root == NULL)
{
    ...
}
else
{
    cmpval = strcmp(k, root->key);
    if (cmpval < 0)
    {
        ...
    }
    else if (cmpval > 0)
    {
        ...
    }
    else // if (cmpval == 0)
    {
        ...
    }
}

设计问题：

strcmp的使用实际上将KEY类型与以空结尾的字符串类型耦合在一起。

您应该尝试将它们解耦，以便允许用户轻松地更改KEY类型。

一种方法是在KEY类型旁边实现一个比较函数：

typedef char* KEY;

int compare(const KEY key1,const KEY key2)
{
    return strcmp(key1,key2);
}

当然，这并不能真正地使KEY与char*脱钩，但至少它让用户知道更改KEY类型之后必须更改compare函数的实现。

可能有一个专门针对本案的设计模式.

Answer 2

这并不是一个完整的回顾，但无论如何，下面是这样说的：

• 看上去你用的是8间距的凹痕。那可真是太多了。我认为4更常见，但它是一个偏好的问题，它是一致的，所以绝对没有错
• 您有KEY，大概是char*的类型，但是您可以在它上调用strcmp。如果您希望跨键类型(这是一个非常好的主意，IMO)，您应该传递一个比较器函数，该比较器函数以两个键作为参数。
• 我将假设TNODE的其他字段由于某种原因而存在，但是否有可能将它们移到rbtree_t中，使TNODE变得更小？
• 我不知道C中类型的命名约定，所以不要认为这是含蓄的协议或异议
• talloc和lalloc可能不需要成为它们自己的函数；malloc(sizeof(TNODE))可能就足够了

Answer 3

• (strcmp(k, root->key) == 0)测试似乎是多余的：<0和>0的情况已经排除在外。
• 我相信talloc正确地初始化了right和left指针。尽管如此，看到实现还是很好的。lalloc也一样。
• rotate_left、rotate_right和flip_colors是正确实现RB树的关键.你也能把密码寄给他们吗？