红黑树实现代码

红黑树演变过程可参考该网站动画演示Red/Black Tree Visualization (usfca.edu)

红黑树平衡树通过左旋 右旋 

四种旋转情况 LL->R（祖父节点） LR->L（父节点） R（祖父节点） RR->L（祖父节点） RL->R(父节点) L（祖父节点）

共有两个难点：

插入难点：  父节点 和叔父节点均为红色，需要 先将父节点和叔父节点变为黑色，祖父节点变为红色，

                    若祖父节点为根节点则变为黑色，结束。否则，将祖父节点作为参数重新传入插入节点函数  进行递归递归检查

删除节点难点：节点、父节点、兄弟节点均为黑色，且兄弟节点两个子节点均为nil。这种情况下，叔父节点变为红色，将父节点带入平衡递归函数

以下是c代码实现

// rbtree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
typedef int RBTYPE;
#define RED 0
#define BLACK 1

// 红黑树节点
typedef struct RBNode {
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
    unsigned char color;
    RBTYPE value;
}RBNODE, *PRBNODE;


typedef struct RBTree {
    PRBNODE root;
    PRBNODE nil;
}RBTREE, *PRBTREE;

PRBTREE create_tree() {
    PRBTREE rbtree = new RBTREE;
    rbtree->nil = new RBNODE;
    rbtree->nil->color = BLACK;
    rbtree->nil->left = rbtree->nil->right = NULL;
    rbtree->root = rbtree->nil;
    return rbtree;
}

PRBNODE create_rbnode(RBTYPE value, PRBNODE nil) {
    PRBNODE pnode = new RBNODE;
    pnode->color = RED;
    pnode->left = pnode->right = pnode->parent = nil;
    pnode->value = value;
    return pnode;
}

//1.插入节点到叶子节点  success 1 failed 0
PRBNODE insert_leaf_node(PRBTREE rbtree, RBTYPE value) {
    PRBNODE node = rbtree->root, node_parent = rbtree->nil;
    while (node != rbtree->nil) {
        node_parent = node;
        if (value < node->value) {
            node = node->left;
        }
        else if (value > node->value) {
            node = node->right;
        }
        else {
            return rbtree->nil;
        }
    }

    // 找到节点插入位置
    PRBNODE leaf_node = create_rbnode(value, rbtree->nil);
    if (node_parent != rbtree->nil) {
        leaf_node->parent = node_parent;
        if (value < node_parent->value) {
            node_parent->left = leaf_node;
        }
        else {
            node_parent->right = leaf_node;
        }
    }
    else {
        // 插入节点为根节点
        leaf_node->color = BLACK;
        rbtree->root = leaf_node;
    }
    return leaf_node;
}

void left_rotate(PRBTREE rbtree, PRBNODE node) {
    PRBNODE node_right = node->right;
    node->right = node_right->left;
    if (node_right->left != rbtree->nil) {
        node_right->left->parent = node;
    }
    
    if (node->parent == rbtree->nil) {
        rbtree->root = node_right;
    }
    else if (node == node->parent->left) {
        node->parent->left = node_right;
    }
    else if (node == node->parent->right) {
        node->parent->right = node_right;
    }
    node_right->parent = node->parent;
    node_right->left = node;
    node->parent = node_right;
}

//LL
void left_left_rotate(PRBTREE rbtree, PRBNODE node) {
    node->color = RED;
    node->right->color = BLACK;
    left_rotate(rbtree, node);
}

// 右旋
void right_rotate(PRBTREE rbtree, PRBNODE node) {
    PRBNODE node_left = node->left;
    node->left = node_left->right;
    if (node_left->right != rbtree->nil) {
        node_left->right->parent = node;
    }

    if (node->parent == rbtree->nil) {
        rbtree->root = node_left;
    }
    else if (node == node->parent->left) {
        node->parent->left = node_left;
    }
    else {
        node->parent->right = node_left;
    }

    node_left->parent = node->parent;
    node_left->right = node;
    node->parent = node_left;
}

// RR
void right_right_rotate(PRBTREE rbtree, PRBNODE node) {
    node->color = RED;
    node->left->color = BLACK;
    right_rotate(rbtree, node);
}

void color_position_adjustment(PRBTREE rbtree, PRBNODE node);
// 将叔父和父节点由红色都变成黑色，若祖父节点不是根节点，则变为红色
void node_uncle_parent_red(PRBTREE rbtree, PRBNODE node_parent, PRBNODE node_uncle) {
    PRBNODE node_grandparent = node_parent->parent;
    node_parent->color = BLACK;
    node_uncle->color = BLACK;
    if (node_grandparent == rbtree->root) {
        return;
    }

    node_grandparent->color = RED;

    color_position_adjustment(rbtree, node_grandparent);
}


void color_position_adjustment(PRBTREE rbtree, PRBNODE node) {
    PRBNODE node_parent = node->parent;
    if (node_parent == rbtree->nil) return;
    PRBNODE node_grandparent = node->parent->parent;
    if (node_grandparent == rbtree->nil) return;
    PRBNODE node_uncle = rbtree->nil;
    
    //1.判断父节点是否为黑色
    if (node_parent->color == BLACK) return;

    //2.父节点为红色
    //2.1 若父节点为祖父节点左子节点
    if (node_parent == node_grandparent->left) {
        node_uncle = node_grandparent->right;
        // 叔父节点是右子节点 
        // 叔父节点为黑色 nil也是黑色
        if (node_uncle == rbtree->nil || node_uncle->color == BLACK) {
            // LR 先左旋转为LL
            if (node == node_parent->right) {
                left_rotate(rbtree, node_parent);
            }
            // LL -> 右旋
            right_right_rotate(rbtree, node_grandparent);
        }
        // 叔父节点红色
        else {
            // 将叔父和父节点都变成黑色，若祖父节点不是根节点，则变为红色
            node_uncle_parent_red(rbtree, node_parent, node_uncle);
        }
    }
    // 2.2若父节点为祖父节点右子节点
    else {
        node_uncle = node_grandparent->left;
        // 叔父节点为左子节点 且为黑色
        if (node_uncle == rbtree->nil || node_uncle->color == BLACK) {
            // RL -> 先右旋为RR
            if (node == node_parent->left) {
                right_rotate(rbtree, node_parent);
            }

            // RR -> 左旋
            left_left_rotate(rbtree, node_grandparent);
        }
        // 叔父节点为红色
        else {
            node_uncle_parent_red(rbtree, node_parent, node_uncle);
        }
    }
}

// 插入节点
bool insert_rbnode(PRBTREE rbtree, RBTYPE value) {
    PRBNODE node = insert_leaf_node(rbtree, value);
    if (node == rbtree->nil) return false;

    // 颜色位置调整
    color_position_adjustment(rbtree, node);
    return true;
}

void free_node(PRBNODE nil, PRBNODE node) {
    if (node == nil) {
        return;
    }

    free_node(nil, node->left);
    free_node(nil, node->right);
    delete node;
}
void clear_rbtree(PRBTREE rbtree) {
    if (rbtree == nullptr) return;
    free_node(rbtree->nil, rbtree->root);
    rbtree->root = rbtree->nil;
}

void free_rbtree(PRBTREE* rbtree) {
    if (*rbtree == nullptr) return;
    clear_rbtree(*rbtree);
    delete (*rbtree)->nil;
    delete *rbtree;
    *rbtree = nullptr;
}

bool isempty_rbtree(PRBTREE rbtree) {
    if (rbtree == nullptr || rbtree->root == rbtree->nil) return true;
    return false;
}

// 查找节点
PRBNODE search_rbnode(RBTYPE value, PRBNODE node, PRBNODE nil) {
    if (node == nil || node->value == value) return node;

    PRBNODE result = search_rbnode(value, node->left, nil);
    if (nil == result) {
        result = search_rbnode(value, node->right, nil);
    }
    return result;
}
// 查找红黑树键所在位置
PRBNODE search_rbtree(PRBTREE rbtree, RBTYPE value) {
    if (isempty_rbtree(rbtree)) return rbtree->nil;
    return search_rbnode(value, rbtree->root, rbtree->nil);
}

// 中序前驱
PRBNODE mid_order_pre(PRBNODE node, PRBNODE nil) {
    PRBNODE node_pre = nil;
    node = node->left;
    while (node != nil) {
        node_pre = node;
        node = node->right;
    }
    return node_pre;
}

// 中序后继
PRBNODE mid_order_next(PRBNODE node, PRBNODE nil) {
    PRBNODE node_next = nil;
    node = node->right;
    while (node != nil) {
        node_next = node;
        node = node->left;
    }
    return node_next;
}

// 查找最接近node 键的节点
PRBNODE search_closest_rbnode(PRBNODE node, PRBNODE nil) {
    PRBNODE closest_node = mid_order_pre(node, nil);
    if (closest_node == nil) {
        closest_node = mid_order_next(node, nil);
    }
    return closest_node;
}


// 交换两个节点位置以及颜色
void swap_rbnode_positioin(PRBNODE oldnode, PRBNODE newnode, PRBNODE nil) {
    PRBNODE tmpleftnode = oldnode->left,
        tmprightnode = oldnode->right,
        tmpparentnode = oldnode->parent;
    int color = oldnode->color;
    oldnode->left = newnode->left;
    oldnode->right = newnode->right;
    oldnode->color = newnode->color;

    if (oldnode == newnode->parent) {
        oldnode->parent = newnode;
        if (tmpleftnode == newnode) {
            newnode->left = oldnode;
            newnode->right = tmprightnode;
        }
        else if (tmprightnode == newnode) {
            newnode->left = tmpleftnode;
            newnode->right = oldnode;
        }
    }
    else {
        oldnode->parent = newnode->parent;
        if (newnode->parent->left = newnode) {
            newnode->parent->left = oldnode;
        }
        else {
            newnode->parent->right = oldnode;
        }
        newnode->left = tmpleftnode;
        newnode->right = tmprightnode;
    }

    newnode->parent = tmpparentnode;
    if (tmpparentnode != nil) {
        if (oldnode == tmpparentnode->left) {
            tmpparentnode->left = newnode;
        }
        else {
            tmpparentnode->right = newnode;
        }
    }
    newnode->color = color;
    if (tmpleftnode == newnode) {
        newnode->left = oldnode;
        newnode->right = tmprightnode;
    }
    else if(tmprightnode == newnode) {
        newnode->left = tmpleftnode;
        newnode->right = oldnode;
    }
    else {
        newnode->left = tmpleftnode;
        newnode->right = tmprightnode;
    }
}

// 处理情况：被删节点和父节点以及兄弟节点（兄弟节点两个子节点都是nil）需要平衡
void balance_rbtree(PRBTREE rbtree, PRBNODE node) {
    if (node == rbtree->nil || node->parent == rbtree->nil) return;

    PRBNODE node_parent = node->parent;
    // 父节点为红色
    if (node_parent->color == RED) {
        // node节点是左子节点
        if (node == node_parent->left) {
            left_rotate(rbtree, node_parent);
        }
        // node节点是右子节点
        else {
            right_rotate(rbtree, node_parent);
        }
    }
    // 父节点为黑色
    else {
        // node节点是左子节点 
        if (node == node_parent->left) {
            // node兄弟节点为红色
            PRBNODE node_sibling = node_parent->right;
            if (node_sibling->color == RED) {
                right_rotate(rbtree, node_parent);
                node_sibling->color = BLACK;
            }
            // 兄弟节点为黑色
            else {
                // 若兄弟节子节点都存在
                if (node_sibling->right->color == RED) {
                    // SR 均为红色  SL 是黑色或红色
                    node_sibling->right->color = BLACK;
                    left_rotate(rbtree, node_parent);
                }
                else if (node_sibling->left->color == RED) {
                    // SL 红色  SR 黑色
                    node_sibling->left->color = BLACK;
                    right_rotate(rbtree, node_sibling);
                    left_rotate(rbtree, node_parent);
                }
                else {
                    PRBNODE node_sibling_left = node_sibling->left;
                    PRBNODE node_sibling_right = node_sibling->right;

                    if (node_sibling_right->left != rbtree->nil
                        && node_sibling_right->right != rbtree->nil) {
                        // SL two son 红色   SR son <=1
                        node_sibling_left->left->color = BLACK;
                        node_sibling_left->right->color = BLACK;
                        left_rotate(rbtree, node_parent);
                    }
                    else if (node_sibling_left->left != rbtree->nil
                        && node_sibling_left->right != rbtree->nil) {
                        // SL two son 红色   SR son <=1
                        node_sibling_right->right->color = BLACK;
                        right_rotate(rbtree, node_sibling_left);
                        left_rotate(rbtree, node_parent);
                    }
                    else {
                        // SL SR 黑色 且  SL SR son <=1
                        // 当走到这一步 说明已经没有可替换的红色节点了，只能向上检查
                        node_sibling->color = RED;
                        balance_rbtree(rbtree, node_parent);
                    }
                }
            }
        }
        // node节点是右子节点
        else {
            // node兄弟节点为红色
            PRBNODE node_sibling = node_parent->left;
            if (node_sibling->color == RED) {
                right_rotate(rbtree, node_parent);
                node_sibling->color = BLACK;
            }
            // 兄弟节点为黑色
            else {
                // 若兄弟节子节点都存在
                if (node_sibling->left->color == RED) {
                    // SR 均为红色  SL 是黑色或红色
                    node_sibling->left->color = BLACK;
                    right_rotate(rbtree, node_parent);
                }
                else if (node_sibling->right->color == RED) {
                    // SL 红色  SR 黑色
                    node_sibling->right->color = BLACK;
                    left_rotate(rbtree, node_sibling);
                    right_rotate(rbtree, node_parent);
                }else {
                    PRBNODE node_sibling_left = node_sibling->left;
                    PRBNODE node_sibling_right = node_sibling->right;

                    if (node_sibling_left->left != rbtree->nil
                        && node_sibling_left->right != rbtree->nil) {
                        // SL two son 红色   SR son <=1
                        node_sibling_left->left->color = BLACK;
                        node_sibling_left->right->color = BLACK;
                        right_rotate(rbtree, node_parent);
                    }
                    else if (node_sibling_right->left != rbtree->nil
                        && node_sibling_right->right != rbtree->nil) {
                        // SL two son 红色   SR son <=1
                        node_sibling_right->right->color = BLACK;
                        left_rotate(rbtree, node_sibling_right);
                        right_rotate(rbtree, node_parent);
                    }
                    else {
                        // SL SR 黑色 且  SL SR son <=1
                        // 当走到这一步 说明已经没有可替换的红色节点了，只能向上检查
                        node_sibling->color = RED;
                        balance_rbtree(rbtree, node_parent);
                    }
                }
            }
        }
    }
}

void reset_parent_node(PRBNODE node, PRBNODE nil) {
    if (node == node->parent->left) {
        node->parent->left = nil;
    }
    else {
        node->parent->right = nil;
    }
}
// 删除节点
void delete_rbnode(PRBTREE rbtree, RBTYPE value) {
    PRBNODE node = search_rbtree(rbtree, value);
    if (node == rbtree->nil) return;

    PRBNODE closest_node = search_closest_rbnode(node, rbtree->nil);
    // 若没有最接近的节点，则删除根节点
    if (closest_node == rbtree->nil) {
        // 是根节点 且就一个节点
        if (closest_node == rbtree->root) {
            rbtree->root = rbtree->nil;
            delete closest_node;
            return;
        }
    }
    // 被删节点非叶子节点，且不是一个根节点
    else {
        // 替换两个键 指向 和颜色
        swap_rbnode_positioin(node, closest_node, rbtree->nil);
    }


    // 若最终被删除节点为红色
    if (node->color == RED) {
        reset_parent_node(node, rbtree->nil);
        delete node;
        return;
    }

    // 被删节点为黑色
    // 若左子节不是nil 则点必定是红色
    if (node->left != rbtree->nil) {
        PRBNODE node_left = node->left;
        node_left->parent = node->parent;
        if (node = node->parent->left) {
            node->parent->left = node_left;
        }
        else {
            node->parent->right = node_left;
        }
    }
    // 若右子节不是nil 则点必定是红色
    else if (node->right != rbtree->nil) {
        PRBNODE node_right = node->right;
        node_right->parent = node->parent;
        if (node = node->parent->left) {
            node->parent->left = node_right;
        }
        else {
            node->parent->right = node_right;
        }
    }
    // 被删节点为叶子节点 黑色
    else {
        // 若最终被删除节点为黑色
        PRBNODE node_parent = node->parent;
        PRBNODE node_brother = rbtree->nil;
        PRBNODE node_brother_left = rbtree->nil;
        PRBNODE node_brother_right = rbtree->nil;

        if (node_parent->left == node) {
            node_brother = node_parent->right;
        }
        else {
            node_brother = node_parent->left;
        }
        if (node_brother != rbtree->nil) {
            node_brother_left = node_brother->left;
            node_brother_right = node_brother->right;
        }

        // 若父节点为红色，则兄弟节点必为黑色
        if (node_parent->color == RED) {
            // 被删node为左子节点
            if (node == node_parent->left) {
                node_parent->left = rbtree->nil;
                // 若兄弟节点存在子节点 必是红色
                if (node_brother_right != rbtree->nil) {
                    node_parent->color = BLACK;
                    node_brother_right->color = BLACK;
                    node_brother->color = RED;
                    left_rotate(rbtree, node_parent);
                }
                else if (node_brother_left != rbtree->nil) {
                    node_parent->color = BLACK;
                    right_rotate(rbtree, node_brother);
                    left_rotate(rbtree, node_parent);
                }
                else {
                    node_parent->color = BLACK;
                    node_brother->color = RED;
                }
            }// 被删节点为右子节点
            else {
                node_parent->right = rbtree->nil;
                // 若兄弟节点存在子节点 必是红色
                if (node_brother_left != rbtree->nil) {
                    right_rotate(rbtree, node_parent);
                }
                else if (node_brother_right != rbtree->nil) {
                    left_rotate(rbtree, node_brother);
                    right_rotate(rbtree, node_parent);
                }
                else {
                    node_parent->color = BLACK;
                    node_brother->color = RED;
                }
            }
        }
        // 父节点为黑色
        else {
            // 被删节点为左子节点
            if (node == node_parent->left) {
                node_parent->left = rbtree->nil;
                if (node_brother_right != rbtree->nil&&
                    node_brother_right->color == RED) {
                    node_brother_right->color = BLACK;
                    left_rotate(rbtree, node_parent);
                }
                else if (node_brother_left != rbtree->nil &&
                    node_brother_left->color == RED) {
                    node_brother_left->color = BLACK;
                    right_rotate(rbtree, node_brother);
                    left_rotate(rbtree, node_parent);
                }
                else {
                    balance_rbtree(rbtree, node_parent);
                }
            }
            // 被删节点为右边
            else {
                node_parent->right = rbtree->nil;
                if (node_brother_left != rbtree->nil &&
                    node_brother_left->color == RED) {
                    node_brother_left->color = BLACK;
                    right_rotate(rbtree, node_parent);
                }
                else if (node_brother_right != rbtree->nil &&
                    node_brother_right->color == RED) {
                    node_brother_right->color = BLACK;
                    left_rotate(rbtree, node_brother);
                    right_rotate(rbtree, node_parent);
                }
                else {
                    balance_rbtree(rbtree, node_parent);
                }
            }
        }
    }
    delete node;
}


// 遍历显示节点
void print_node(PRBNODE nil, PRBNODE node) {
    if (nil == node) return;

    print_node(nil, node->left);
    std::cout << "[" << node->value << ", " << (node->color == RED ? "RED" : "BALCK") << "] ";
    print_node(nil, node->right);
}
void print_rbtree(PRBTREE rbtree) {
    if (rbtree == nullptr) return;
    print_node(rbtree->nil, rbtree->root);
    std::cout << std::endl;
}

#define SIZE 8
int main()
{
    PRBTREE rbtree = create_tree();
    for (size_t i = 0; i < SIZE; i++)
    {
        if (!insert_rbnode(rbtree, i)) {
            std::cout << "插入失败: " << i << std::endl;
        }
    }
    print_rbtree(rbtree);

    RBTYPE value = 5;
    std::cout << "查找：" << value << std::endl;
    PRBNODE node = search_rbtree(rbtree, value);
    if (node != rbtree->nil)
    {
        std::cout << "[" << node->value << ", " << (node->color == RED ? "RED" : "BALCK") << "] " << std::endl;
    }
    else {
        std::cout << "未找到" << std::endl;
    }

    std::cout << value << " 父节点：" << node->parent->value << std::endl;
    RBTYPE dvalue = 5;
    std::cout << "删除点：" << dvalue << std::endl;
    delete_rbnode(rbtree, dvalue);
    print_rbtree(rbtree);
    free_rbtree(&rbtree);
    return 0;
}