当前位置： 首页 > article >正文

红黑树C/CPP

article 2025/1/4 5:38:08 
#include <stdio.h>
#include <stdlib.h>

// 红黑树节点颜色定义
typedef enum { RED, BLACK } NodeColor;

// 红黑树节点结构
typedef struct RBTreeNode {
    int key;                        // 节点的键值
    NodeColor color;                // 节点的颜色（红或黑）
    struct RBTreeNode *left;        // 左子节点
    struct RBTreeNode *right;       // 右子节点
    struct RBTreeNode *parent;      // 父节点
} RBTreeNode;

// 红黑树结构
typedef struct RBTree {
    RBTreeNode *root;               // 根节点
    RBTreeNode *nil;                // 哨兵节点（所有空节点指向这个）
} RBTree;

// 创建一个新节点
RBTreeNode *createNode(RBTree *tree, int key) {
    RBTreeNode *node = (RBTreeNode *)malloc(sizeof(RBTreeNode));
    if (node == NULL) {
        fprintf(stderr, "Memory allocation failed for new node.\n");
        exit(EXIT_FAILURE);
    }
    node->key = key;
    node->color = RED;              // 新插入节点默认为红色
    node->left = tree->nil;
    node->right = tree->nil;
    node->parent = tree->nil;
    return node;
}

// 初始化红黑树
RBTree *createTree() {
    RBTree *tree = (RBTree *)malloc(sizeof(RBTree));
    if (tree == NULL) {
        fprintf(stderr, "Memory allocation failed for tree.\n");
        exit(EXIT_FAILURE);
    }
    // 初始化哨兵节点
    tree->nil = (RBTreeNode *)malloc(sizeof(RBTreeNode));
    if (tree->nil == NULL) {
        fprintf(stderr, "Memory allocation failed for sentinel node.\n");
        exit(EXIT_FAILURE);
    }
    tree->nil->color = BLACK;
    tree->root = tree->nil;
    return tree;
}

// 左旋转
void leftRotate(RBTree *tree, RBTreeNode *x) {
    RBTreeNode *y = x->right;
    x->right = y->left;
    if (y->left != tree->nil)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == tree->nil)
        tree->root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

// 右旋转
void rightRotate(RBTree *tree, RBTreeNode *x) {
    RBTreeNode *y = x->left;
    x->left = y->right;
    if (y->right != tree->nil)
        y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == tree->nil)
        tree->root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

// 插入修复（保持红黑树性质）
void insertFixup(RBTree *tree, RBTreeNode *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBTreeNode *y = z->parent->parent->right; // 叔叔节点
            if (y->color == RED) {                  // Case 1: 叔叔是红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {       // Case 2: 叔叔是黑色，当前节点是右子节点
                    z = z->parent;
                    leftRotate(tree, z);
                }
                z->parent->color = BLACK;         // Case 3: 叔叔是黑色，当前节点是左子节点
                z->parent->parent->color = RED;
                rightRotate(tree, z->parent->parent);
            }
        } else {
            RBTreeNode *y = z->parent->parent->left; // 叔叔节点
            if (y->color == RED) {                  // Case 1: 叔叔是红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {        // Case 2: 叔叔是黑色，当前节点是左子节点
                    z = z->parent;
                    rightRotate(tree, z);
                }
                z->parent->color = BLACK;         // Case 3: 叔叔是黑色，当前节点是右子节点
                z->parent->parent->color = RED;
                leftRotate(tree, z->parent->parent);
            }
        }
    }
    tree->root->color = BLACK; // 根节点必须为黑色
}

// 插入节点
void rbInsert(RBTree *tree, int key) {
    RBTreeNode *z = createNode(tree, key);
    RBTreeNode *y = tree->nil;
    RBTreeNode *x = tree->root;

    // 查找插入位置
    while (x != tree->nil) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;

    // 插入为根节点或子节点
    if (y == tree->nil)
        tree->root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    z->left = tree->nil;
    z->right = tree->nil;
    z->color = RED;

    // 修复红黑树性质
    insertFixup(tree, z);
}

// 中序遍历（调试用）
void inorderTraversal(RBTree *tree, RBTreeNode *node) {
    if (node != tree->nil) {
        inorderTraversal(tree, node->left);
        printf("%d(%s) ", node->key, node->color == RED ? "R" : "B");
        inorderTraversal(tree, node->right);
    }
}

// 释放节点
void freeNode(RBTree *tree, RBTreeNode *node) {
    if (node != tree->nil) {
        freeNode(tree, node->left);
        freeNode(tree, node->right);
        free(node);
    }
}

// 释放红黑树
void freeTree(RBTree *tree) {
    freeNode(tree, tree->root);
    free(tree->nil);
    free(tree);
}

// 主函数
int main() {
    RBTree *tree = createTree();

    // 插入数据
    rbInsert(tree, 10);
    rbInsert(tree, 20);
    rbInsert(tree, 30);
    rbInsert(tree, 15);
    rbInsert(tree, 25);

    // 中序遍历
    printf("Inorder Traversal of Red-Black Tree:\n");
    inorderTraversal(tree, tree->root);
    printf("\n");

    // 释放红黑树
    freeTree(tree);
    return 0;
}

 C语言版本

  • 结构设计：

    • RBTree 包含根节点和哨兵节点。
    • 哨兵节点用于表示空节点，避免频繁的空指针检查。

  • 关键功能：

    • createNode() 创建一个红色的新节点。
    • leftRotate() 和 rightRotate() 实现红黑树的旋转操作。
    • insertFixup() 修复红黑树插入后的平衡性。

  • 增强健壮性：

    • 内存分配失败时打印错误并终止程序。
    • 所有空节点使用哨兵节点，避免空指针操作。

  • 调试功能：

    • 中序遍历函数 inorderTraversal() 输出红黑树的节点及其颜色，便于调试。

  • 内存管理：

    • 在程序结束时释放分配的内存，避免内存泄漏。
#include <iostream>
#include <memory> // 用于智能指针
using namespace std;

// 红黑树节点颜色定义
enum NodeColor { RED, BLACK };

// 红黑树节点类
struct RBTreeNode {
    int key;                         // 节点的键值
    NodeColor color;                 // 节点的颜色
    shared_ptr<RBTreeNode> left;     // 左子节点
    shared_ptr<RBTreeNode> right;    // 右子节点
    weak_ptr<RBTreeNode> parent;     // 父节点（使用 weak_ptr 避免循环引用）

    // 构造函数
    RBTreeNode(int k, NodeColor c)
        : key(k), color(c), left(nullptr), right(nullptr), parent() {}
};

// 红黑树类
class RBTree {
private:
    shared_ptr<RBTreeNode> root;     // 根节点
    shared_ptr<RBTreeNode> nil;      // 哨兵节点

    // 左旋转
    void leftRotate(shared_ptr<RBTreeNode> x) {
        auto y = x->right;           // y 是 x 的右子节点
        x->right = y->left;          // 将 y 的左子树移动为 x 的右子树
        if (y->left != nil) {
            y->left->parent = x;
        }
        y->parent = x->parent;       // 更新 y 的父节点
        if (x->parent.lock() == nil) {
            root = y;
        } else if (x == x->parent.lock()->left) {
            x->parent.lock()->left = y;
        } else {
            x->parent.lock()->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    // 右旋转
    void rightRotate(shared_ptr<RBTreeNode> x) {
        auto y = x->left;            // y 是 x 的左子节点
        x->left = y->right;          // 将 y 的右子树移动为 x 的左子树
        if (y->right != nil) {
            y->right->parent = x;
        }
        y->parent = x->parent;       // 更新 y 的父节点
        if (x->parent.lock() == nil) {
            root = y;
        } else if (x == x->parent.lock()->right) {
            x->parent.lock()->right = y;
        } else {
            x->parent.lock()->left = y;
        }
        y->right = x;
        x->parent = y;
    }

    // 插入修复
    void insertFixup(shared_ptr<RBTreeNode> z) {
        while (z->parent.lock()->color == RED) {
            if (z->parent.lock() == z->parent.lock()->parent.lock()->left) {
                auto y = z->parent.lock()->parent.lock()->right; // 叔叔节点
                if (y->color == RED) {                          // Case 1: 叔叔是红色
                    z->parent.lock()->color = BLACK;
                    y->color = BLACK;
                    z->parent.lock()->parent.lock()->color = RED;
                    z = z->parent.lock()->parent.lock();
                } else {
                    if (z == z->parent.lock()->right) {         // Case 2: 当前节点是右子节点
                        z = z->parent.lock();
                        leftRotate(z);
                    }
                    z->parent.lock()->color = BLACK;           // Case 3: 当前节点是左子节点
                    z->parent.lock()->parent.lock()->color = RED;
                    rightRotate(z->parent.lock()->parent.lock());
                }
            } else {
                auto y = z->parent.lock()->parent.lock()->left; // 叔叔节点
                if (y->color == RED) {                          // Case 1: 叔叔是红色
                    z->parent.lock()->color = BLACK;
                    y->color = BLACK;
                    z->parent.lock()->parent.lock()->color = RED;
                    z = z->parent.lock()->parent.lock();
                } else {
                    if (z == z->parent.lock()->left) {          // Case 2: 当前节点是左子节点
                        z = z->parent.lock();
                        rightRotate(z);
                    }
                    z->parent.lock()->color = BLACK;           // Case 3: 当前节点是右子节点
                    z->parent.lock()->parent.lock()->color = RED;
                    leftRotate(z->parent.lock()->parent.lock());
                }
            }
        }
        root->color = BLACK; // 根节点必须为黑色
    }

public:
    // 构造函数
    RBTree() {
        nil = make_shared<RBTreeNode>(0, BLACK); // 初始化哨兵节点
        root = nil;
    }

    // 插入节点
    void rbInsert(int key) {
        auto z = make_shared<RBTreeNode>(key, RED); // 创建新节点
        z->left = nil;
        z->right = nil;

        auto y = nil;
        auto x = root;

        // 查找插入位置
        while (x != nil) {
            y = x;
            if (z->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        z->parent = y;

        // 插入为根节点或子节点
        if (y == nil) {
            root = z;
        } else if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }

        // 修复红黑树性质
        insertFixup(z);
    }

    // 中序遍历（调试用）
    void inorderTraversal(shared_ptr<RBTreeNode> node) const {
        if (node != nil) {
            inorderTraversal(node->left);
            cout << node->key << "(" << (node->color == RED ? "R" : "B") << ") ";
            inorderTraversal(node->right);
        }
    }

    // 中序遍历接口
    void inorderTraversal() const {
        inorderTraversal(root);
        cout << endl;
    }

    // 释放节点
    void freeTree() {
        root = nil; // 自动释放内存
    }

    // 析构函数
    ~RBTree() {
        freeTree();
    }
};

// 主函数
int main() {
    RBTree tree;

    // 插入数据
    tree.rbInsert(10);
    tree.rbInsert(20);
    tree.rbInsert(30);
    tree.rbInsert(15);
    tree.rbInsert(25);

    // 中序遍历
    cout << "Inorder Traversal of Red-Black Tree:" << endl;
    tree.inorderTraversal();

    return 0;
}

CPP版本

  1. 类设计：

    • RBTreeNode 表示红黑树的节点。
    • 使用 shared_ptr 和 weak_ptr 管理内存，避免手动释放内存和循环引用问题。
    • RBTree 是红黑树的主体类，包含插入、修复和遍历功能。

  2. 增强健壮性：

    • 使用智能指针避免内存泄漏。
    • nil 节点用作哨兵节点，减少空指针判断的复杂性。

  3. 关键功能：

    • 左旋转和右旋转操作用于维护红黑树的平衡。
    • 插入修复算法确保红黑树性质不被破坏。

  4. 内存管理：

    • 使用智能指针 (shared_ptr 和 weak_ptr) 自动管理内存。
    • 在析构函数中清空树，释放资源。

  5. 调试功能：

    • 提供 inorderTraversal() 函数，按中序输出节点的键值和颜色，便于验证红黑树结构。

http://www.kler.cn/a/459975.html

相关文章：

  • Docker--Docker Container(容器) 之 操作实例
  • webserver的http实现
  • 基于feapder爬虫与flask前后端框架的天气数据可视化大屏
  • AI 助力游戏开发中的常用算法实现
  • OpenCV的人脸检测模型FaceDetectorYN
  • 【unity错误】Unity 6 LTS 打开就报错Assertion failed on expressionxxx？
  • 【ES6复习笔记】对象方法扩展（17）
  • 一个复杂的SQL分析
  • FlaskAPI-交互式文档与includ_router
  • node.js之---事件驱动编程
  • 解决k8s部署dashboard时一直处于Pending状态的问题
  • Kotlin 协程基础知识总结一 —— 挂起、调度器与结构化并发
  • 微信小程序 覆盖组件cover-view
  • Vue.js 使用 Vue CLI 创建项目：快速上手指南
  • 【蓝桥杯选拔赛真题85】python摆放箱子 第十五届青少年组蓝桥杯python选拔赛真题 算法思维真题解析
  • 2-6-1-1 QNX编程入门之进程和线程（六）
  • Linux的诞生与发展、体系结构与发行版本
  • Android使用JAVA调用JNI原生C++方法
  • 【Spark】架构与核心组件：大数据时代的必备技能（上）
  • 【VBA】EXCEL - VBA 遍历工作表的 5 种方法，以及注意事项
  • 网神SecFox FastJson反序列化RCE漏洞复现（附脚本）
  • Java 编程探秘之饿汉式单例设计模式：原理、优势与实战应用全解析，开启高效代码世界的大门
  • android stdudio环境： gradle一直安装失败
  • Linux（13）——网络概述
  • 基于单片机的蓄电池内阻检测系统设计（论文+源码）
  • pytorch torch.nn.LayerNorm类介绍