赤黒木の挿入、削除、探索をするＣ言語のサンプルコード(ChatGPT)

以下は、C言語で赤黒木（Red-Black Tree）を挿入、削除、および探索するためのサンプルコードです。コード内にはコメントが追加されており、それぞれの手順の説明が含まれています。なお、このコードはあくまで簡単なサンプルであり、完全な実装ではありませんが、基本的なアイデアと手順を理解するのに役立つでしょう。

#include <stdio.h>
#include <stdlib.h>

// 赤黒木のノード構造体
typedef struct Node {
    int data;               // ノードに格納されるデータ
    int color;              // ノードの色 (0: 黒, 1: 赤)
    struct Node* parent;    // 親ノードへのポインタ
    struct Node* left;      // 左の子ノードへのポインタ
    struct Node* right;     // 右の子ノードへのポインタ
} Node;

// 新しいノードを作成する関数
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->color = 1;  // 新しいノードは赤で初期化
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 左回転を行う関数
void rotateLeft(Node** root, Node* node) {
    Node* rightChild = node->right;
    node->right = rightChild->left;

    if (node->right != NULL)
        node->right->parent = node;

    rightChild->parent = node->parent;

    if (node->parent == NULL)
        *root = rightChild;
    else if (node == node->parent->left)
        node->parent->left = rightChild;
    else
        node->parent->right = rightChild;

    rightChild->left = node;
    node->parent = rightChild;
}

// 右回転を行う関数
void rotateRight(Node** root, Node* node) {
    Node* leftChild = node->left;
    node->left = leftChild->right;

    if (node->left != NULL)
        node->left->parent = node;

    leftChild->parent = node->parent;

    if (node->parent == NULL)
        *root = leftChild;
    else if (node == node->parent->left)
        node->parent->left = leftChild;
    else
        node->parent->right = leftChild;

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

// 赤黒木への挿入を行う関数
void insert(Node** root, Node* node) {
    // 親ノードと祖父ノードのポインタ
    Node* parent = NULL;
    Node* grandParent = NULL;

    // 赤黒木の挿入は通常の二分木の挿入と同様に行う
    while ((node !=

 *root) && (node->color != 0) && (node->parent->color == 1)) {
        parent = node->parent;
        grandParent = parent->parent;

        // 親ノードが祖父ノードの左の子の場合
        if (parent == grandParent->left) {
            Node* uncle = grandParent->right;

            // Case 1: 叔父ノードが赤の場合
            if (uncle != NULL && uncle->color == 1) {
                grandParent->color = 1;
                parent->color = 0;
                uncle->color = 0;
                node = grandParent;
            } else {
                // Case 2: 叔父ノードが黒で、新しいノードが右の子の場合
                if (node == parent->right) {
                    rotateLeft(root, parent);
                    node = parent;
                    parent = node->parent;
                }

                // Case 3: 叔父ノードが黒で、新しいノードが左の子の場合
                rotateRight(root, grandParent);
                int temp = parent->color;
                parent->color = grandParent->color;
                grandParent->color = temp;
                node = parent;
            }
        } else {  // 親ノードが祖父ノードの右の子の場合 (左右対称の処理)
            Node* uncle = grandParent->left;

            // Case 1
            if ((uncle != NULL) && (uncle->color == 1)) {
                grandParent->color = 1;
                parent->color = 0;
                uncle->color = 0;
                node = grandParent;
            } else {
                // Case 2
                if (node == parent->left) {
                    rotateRight(root, parent);
                    node = parent;
                    parent = node->parent;
                }

                // Case 3
                rotateLeft(root, grandParent);
                int temp = parent->color;
                parent->color = grandParent->color;
                grandParent->color = temp;
                node = parent;
            }
        }
    }

    (*root)->color = 0;  // 根ノードは常に黒にする
}

// 赤黒木からノードを削除する関数
void deleteNode(Node** root, int data) {
    // TODO: ノードの削除の実装
}

// 赤黒木を探索する関数
Node* search(Node* root, int data) {
    while (root != NULL) {
        if (data < root->data)
            root = root->left;
        else if (data > root->data)
            root = root->right;
        else
            return root;  // データが一致した場合、ノードを返す
    }
    return NULL;  // データが見つからない場合はNULLを返す
}

// 赤黒木を中間順で表示する関数 (デバッグ用)
void inorderTraversal(Node* node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->data);
        inorderTraversal(node->right);
    }
}

int main() {
    Node* root = NULL;

    // サンプルデ

ータの挿入
    insert(&root, createNode(10));
    insert(&root, createNode(20));
    insert(&root, createNode(30));
    insert(&root, createNode(40));
    insert(&root, createNode(50));
    insert(&root, createNode(60));
    insert(&root, createNode(70));

    printf("赤黒木の中間順序: ");
    inorderTraversal(root);
    printf("\n");

    int searchData = 40;
    Node* searchResult = search(root, searchData);
    if (searchResult != NULL)
        printf("%d が見つかりました\n", searchData);
    else
        printf("%d は見つかりませんでした\n", searchData);

    // TODO: 削除操作のテスト

    return 0;
}

このコードでは、赤黒木にデータを挿入し、中間順序で赤黒木のノードを表示し、指定されたデータを探索します。また、削除操作の部分は実装されていませんが、TODOコメントがありますので、削除操作を追加する際には、それを実装することができます。

ただし、赤黒木は複雑なデータ構造であり、実装には注意が必要です。このサンプルコードは基本的なアルゴリズムを示すものであり、完全な実装や詳細なエラーハンドリングが含まれているわけではありません。実際の使用に際しては、より詳細なテストとエラーハンドリングを追加することが推奨されます。