MENU
  1. ホーム
  2. C言語
  3. C言語でのレッドブラックツリーの実装方法を徹底解説

C言語でのレッドブラックツリーの実装方法を徹底解説

C言語

レッドブラックツリーは、バランスの取れた二分探索木で、効率的な検索、挿入、削除を実現します。C言語でのレッドブラックツリーの実装方法を学ぶことで、高速なデータ操作が求められるアプリケーションの開発に役立ちます。本記事では、レッドブラックツリーの基本概念から、具体的な実装手順、応用例までを詳しく解説します。

目次

レッドブラックツリーの基本概念

レッドブラックツリーは、特定のルールに従ってノードが色分けされ、バランスを保つ二分探索木です。各ノードは赤または黒の色を持ち、以下のプロパティを満たします：

1. ノードの色

各ノードは赤または黒である。

2. 根ノード

根ノードは常に黒である。

3. 葉ノード

すべての葉（NILノード）は黒である。

4. 赤の親子関係

赤ノードの親は必ず黒である（赤の親子関係はない）。

5. 黒の高さ

任意のノードからその子孫の葉までのすべてのパスは、同じ数の黒ノードを通過する。

これらのプロパティにより、木の高さは常にO(log n)に保たれ、効率的なデータ操作が可能になります。

必要なデータ構造の定義

レッドブラックツリーを実装するために必要なノード構造体や基本的な型を定義します。以下に、C言語でのノードの定義例を示します。

ノード構造体

レッドブラックツリーのノードは、キー、色、親ノード、左子ノード、右子ノードの情報を持ちます。

typedef enum { RED, BLACK } NodeColor;

typedef struct RBTreeNode {
    int key; // ノードのキー
    NodeColor color; // ノードの色（赤または黒）
    struct RBTreeNode *parent; // 親ノードへのポインタ
    struct RBTreeNode *left; // 左子ノードへのポインタ
    struct RBTreeNode *right; // 右子ノードへのポインタ
} RBTreeNode;

木構造体

レッドブラックツリー全体を管理するための木構造体も定義します。この構造体は、根ノードへのポインタとNILノード（すべての葉ノードを表す）を含みます。

typedef struct RBTree {
    RBTreeNode *root; // 根ノードへのポインタ
    RBTreeNode *nil; // NILノードへのポインタ
} RBTree;

初期化関数

木とノードを初期化するための関数を定義します。

// ノードを初期化する関数
RBTreeNode* createNode(int key, NodeColor color, RBTreeNode *nil) {
    RBTreeNode *node = (RBTreeNode *)malloc(sizeof(RBTreeNode));
    node->key = key;
    node->color = color;
    node->parent = nil;
    node->left = nil;
    node->right = nil;
    return node;
}

// 木を初期化する関数
RBTree* createTree() {
    RBTree *tree = (RBTree *)malloc(sizeof(RBTree));
    tree->nil = createNode(0, BLACK, NULL); // NILノードは黒
    tree->root = tree->nil;
    return tree;
}

これらの定義と初期化関数により、レッドブラックツリーの基本的なデータ構造を構築する準備が整いました。次に、ノードの挿入や削除などの操作を実装していきます。

ノードの挿入

レッドブラックツリーへの新しいノードの挿入手順と、その後のバランス調整方法について解説します。ノードの挿入には、まず通常の二分探索木への挿入を行い、その後レッドブラックツリー特有の調整を行います。

挿入手順

新しいノードを挿入する際の基本的な手順は以下の通りです。

  1. 新しいノードを赤色として作成します。
  2. 通常の二分探索木の挿入手順に従って新しいノードを追加します。
  3. 挿入後、レッドブラックツリーのプロパティを保つための調整を行います。
void insertFixup(RBTree *tree, RBTreeNode *node) {
    while (node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            RBTreeNode *uncle = node->parent->parent->right;
            if (uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    leftRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(tree, node->parent->parent);
            }
        } else {
            RBTreeNode *uncle = node->parent->parent->left;
            if (uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rightRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                leftRotate(tree, node->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

void rbInsert(RBTree *tree, int key) {
    RBTreeNode *node = createNode(key, RED, tree->nil);
    RBTreeNode *y = tree->nil;
    RBTreeNode *x = tree->root;

    while (x != tree->nil) {
        y = x;
        if (node->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    node->parent = y;
    if (y == tree->nil) {
        tree->root = node;
    } else if (node->key < y->key) {
        y->left = node;
    } else {
        y->right = node;
    }

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

    insertFixup(tree, node);
}

バランス調整

挿入後のバランス調整は、主に次の2つの操作を使用して行います：

左回転

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 *y) {
    RBTreeNode *x = y->left;
    y->left = x->right;
    if (x->right != tree->nil) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == tree->nil) {
        tree->root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

これで、レッドブラックツリーへのノード挿入とバランス調整の基本が理解できます。次に、ノードの削除手順について解説します。

ノードの削除

レッドブラックツリーから既存のノードを削除する際の手順と、その後のバランス調整方法について詳しく解説します。削除操作は、ノードを削除した後にツリーのプロパティを維持するための修正を行う必要があります。

削除手順

ノードの削除は以下の手順で行います：

  1. 削除するノードを見つけます。
  2. 削除するノードを適切に取り除きます（場合によっては、子ノードを調整する必要があります）。
  3. レッドブラックツリーのプロパティを維持するために調整を行います。

削除関数の実装例

void deleteFixup(RBTree *tree, RBTreeNode *x) {
    while (x != tree->root && x->color == BLACK) {
        if (x == x->parent->left) {
            RBTreeNode *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(tree, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(tree, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(tree, x->parent);
                x = tree->root;
            }
        } else {
            RBTreeNode *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(tree, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(tree, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(tree, x->parent);
                x = tree->root;
            }
        }
    }
    x->color = BLACK;
}

void rbTransplant(RBTree *tree, RBTreeNode *u, RBTreeNode *v) {
    if (u->parent == tree->nil) {
        tree->root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    v->parent = u->parent;
}

RBTreeNode* treeMinimum(RBTree *tree, RBTreeNode *x) {
    while (x->left != tree->nil) {
        x = x->left;
    }
    return x;
}

void rbDelete(RBTree *tree, RBTreeNode *z) {
    RBTreeNode *y = z;
    RBTreeNode *x;
    NodeColor yOriginalColor = y->color;
    if (z->left == tree->nil) {
        x = z->right;
        rbTransplant(tree, z, z->right);
    } else if (z->right == tree->nil) {
        x = z->left;
        rbTransplant(tree, z, z->left);
    } else {
        y = treeMinimum(tree, z->right);
        yOriginalColor = y->color;
        x = y->right;
        if (y->parent == z) {
            x->parent = y;
        } else {
            rbTransplant(tree, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        rbTransplant(tree, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    free(z);
    if (yOriginalColor == BLACK) {
        deleteFixup(tree, x);
    }
}

バランス調整

削除後のバランス調整は、主に次の操作を使用して行います：

左回転

上記の挿入手順で紹介した左回転関数を使用します。

右回転

上記の挿入手順で紹介した右回転関数を使用します。

これにより、レッドブラックツリーからノードを削除し、ツリーのプロパティを維持する方法が理解できます。次に、木の回転操作について詳しく解説します。

木の回転操作

レッドブラックツリーのバランスを保つための回転操作について解説します。回転操作は、ツリーのバランスを修正するために重要な役割を果たします。主に「左回転」と「右回転」の2つの操作があります。

左回転

左回転は、ノードxとその右子ノードyを中心に行います。xが根ノードの場合、新しい根はyになります。そうでない場合、xの親ノードがyにリンクされます。xの右子ノードはyの左子ノードに置き換えられます。

void leftRotate(RBTree *tree, RBTreeNode *x) {
    RBTreeNode *y = x->right; // yをxの右子ノードとする
    x->right = y->left; // yの左子ノードをxの右子ノードに設定
    if (y->left != tree->nil) {
        y->left->parent = x; // yの左子ノードの親をxに設定
    }
    y->parent = x->parent; // yの親をxの親に設定
    if (x->parent == tree->nil) {
        tree->root = y; // xが根ノードの場合、yを新しい根に設定
    } else if (x == x->parent->left) {
        x->parent->left = y; // xが左子ノードの場合、xの親の左子ノードをyに設定
    } else {
        x->parent->right = y; // xが右子ノードの場合、xの親の右子ノードをyに設定
    }
    y->left = x; // xをyの左子ノードに設定
    x->parent = y; // xの親をyに設定
}

右回転

右回転は、左回転の逆の操作です。ノードyとその左子ノードxを中心に行います。yが根ノードの場合、新しい根はxになります。そうでない場合、yの親ノードがxにリンクされます。yの左子ノードはxの右子ノードに置き換えられます。

void rightRotate(RBTree *tree, RBTreeNode *y) {
    RBTreeNode *x = y->left; // xをyの左子ノードとする
    y->left = x->right; // xの右子ノードをyの左子ノードに設定
    if (x->right != tree->nil) {
        x->right->parent = y; // xの右子ノードの親をyに設定
    }
    x->parent = y->parent; // xの親をyの親に設定
    if (y->parent == tree->nil) {
        tree->root = x; // yが根ノードの場合、xを新しい根に設定
    } else if (y == y->parent->right) {
        y->parent->right = x; // yが右子ノードの場合、yの親の右子ノードをxに設定
    } else {
        y->parent->left = x; // yが左子ノードの場合、yの親の左子ノードをxに設定
    }
    x->right = y; // yをxの右子ノードに設定
    y->parent = x; // yの親をxに設定
}

回転操作の適用例

回転操作は、ノードの挿入や削除後のバランス調整において使用されます。以下は、挿入後にバランスを保つための回転操作の例です。

// 挿入後のバランス調整の一部
if (node == node->parent->right) {
    node = node->parent;
    leftRotate(tree, node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rightRotate(tree, node->parent->parent);

これで、木の回転操作の基本が理解できました。次に、カラー修正について詳しく解説します。

カラー修正

レッドブラックツリーのカラー修正は、ノードの色を変更することでツリーのプロパティを維持するための重要な手順です。挿入や削除の際に、バランスを保つための補助として使用されます。ここでは、具体的なカラー修正の手順について説明します。

挿入時のカラー修正

ノードの挿入後、ツリーのプロパティを維持するためにカラー修正を行います。以下の例は、挿入後に赤いノードが連続している場合の修正手順です。

void insertFixup(RBTree *tree, RBTreeNode *node) {
    while (node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            RBTreeNode *uncle = node->parent->parent->right;
            if (uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    leftRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(tree, node->parent->parent);
            }
        } else {
            RBTreeNode *uncle = node->parent->parent->left;
            if (uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rightRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                leftRotate(tree, node->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

削除時のカラー修正

ノードの削除後、ツリーのバランスを維持するためにカラー修正を行います。以下の例は、削除後に黒いノードが足りない場合の修正手順です。

void deleteFixup(RBTree *tree, RBTreeNode *x) {
    while (x != tree->root && x->color == BLACK) {
        if (x == x->parent->left) {
            RBTreeNode *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(tree, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(tree, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(tree, x->parent);
                x = tree->root;
            }
        } else {
            RBTreeNode *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(tree, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(tree, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(tree, x->parent);
                x = tree->root;
            }
        }
    }
    x->color = BLACK;
}

カラー修正の適用例

以下の例は、挿入時のカラー修正の一部です。赤いノードが連続している場合、色を変更し、必要に応じて回転操作を行います。

if (node->parent->color == RED) {
    if (node->parent == node->parent->parent->left) {
        RBTreeNode *uncle = node->parent->parent->right;
        if (uncle->color == RED) {
            node->parent->color = BLACK;
            uncle->color = BLACK;
            node->parent->parent->color = RED;
            node = node->parent->parent;
        } else {
            if (node == node->parent->right) {
                node = node->parent;
                leftRotate(tree, node);
            }
            node->parent->color = BLACK;
            node->parent->parent->color = RED;
            rightRotate(tree, node->parent->parent);
        }
    } else {
        RBTreeNode *uncle = node->parent->parent->left;
        if (uncle->color == RED) {
            node->parent->color = BLACK;
            uncle->color = BLACK;
            node->parent->parent->color = RED;
            node = node->parent->parent;
        } else {
            if (node == node->parent->left) {
                node = node->parent;
                rightRotate(tree, node);
            }
            node->parent->color = BLACK;
            node->parent->parent->color = RED;
            leftRotate(tree, node->parent->parent);
        }
    }
}

カラー修正の手順を理解することで、レッドブラックツリーのプロパティを維持し、バランスを保つことができます。次に、レッドブラックツリーの検索操作について解説します。

レッドブラックツリーの検索操作

レッドブラックツリー内でのデータ検索は、通常の二分探索木と同様に行われます。ツリーのバランスを保つ特性により、検索操作の最悪時間計算量は O(log n) となります。

検索手順

レッドブラックツリーでの検索操作は、以下の手順で行います。

  1. 根ノードから検索を開始します。
  2. 現在のノードのキーと検索するキーを比較します。
  3. 一致するキーが見つかれば、該当ノードを返します。
  4. 検索するキーが現在のノードのキーより小さい場合、左子ノードに移動します。
  5. 検索するキーが現在のノードのキーより大きい場合、右子ノードに移動します。
  6. 一致するキーが見つかるか、葉ノード（NILノード）に到達するまで手順2～5を繰り返します。

検索関数の実装例

以下に、C言語でのレッドブラックツリー検索関数の例を示します。

RBTreeNode* rbSearch(RBTree *tree, int key) {
    RBTreeNode *current = tree->root; // 根ノードから検索を開始

    while (current != tree->nil && key != current->key) {
        if (key < current->key) {
            current = current->left; // キーが現在のノードのキーより小さい場合、左子ノードに移動
        } else {
            current = current->right; // キーが現在のノードのキーより大きい場合、右子ノードに移動
        }
    }

    return current; // 一致するキーが見つかれば該当ノードを返し、見つからなければNILノードを返す
}

検索操作の適用例

例えば、レッドブラックツリー内でキーが45のノードを検索する場合、以下のように関数を呼び出します。

int main() {
    RBTree *tree = createTree();

    // 例としていくつかのノードを挿入
    rbInsert(tree, 30);
    rbInsert(tree, 15);
    rbInsert(tree, 45);
    rbInsert(tree, 60);

    // キーが45のノードを検索
    RBTreeNode *result = rbSearch(tree, 45);

    if (result != tree->nil) {
        printf("キー %d が見つかりました。\n", result->key);
    } else {
        printf("キーが見つかりませんでした。\n");
    }

    return 0;
}

上記の例では、キーが45のノードがツリー内に存在するため、「キー 45 が見つかりました。」と表示されます。

検索操作を理解することで、レッドブラックツリー内のデータに迅速にアクセスできるようになります。次に、実際の応用例や学習を深めるための演習問題を紹介します。

応用例と演習問題

レッドブラックツリーの応用例や学習を深めるための演習問題を紹介します。これにより、実際の開発シナリオでレッドブラックツリーの利用方法を理解し、実装スキルを向上させることができます。

応用例

レッドブラックツリーは、その効率的なデータ操作の特性から、以下のような分野で広く利用されています。

データベースインデックス

レッドブラックツリーは、データベース管理システムでのインデックス構造として使用されます。これにより、データの検索、挿入、削除が高速に行えるようになります。

メモリ管理

動的メモリ管理システムにおいて、メモリブロックの管理にレッドブラックツリーが利用されます。メモリ割り当てや解放を効率的に行うことができます。

ネットワークルーティング

ネットワークルーティングプロトコルでの経路情報の管理に使用されます。これにより、ルート検索が高速化され、ネットワークのパフォーマンスが向上します。

演習問題

レッドブラックツリーの理解を深めるために、以下の演習問題に取り組んでみてください。

演習1: 基本操作の実装

以下の機能を持つレッドブラックツリーを実装してください：

  1. ノードの挿入
  2. ノードの削除
  3. ノードの検索

演習2: トラバース操作の実装

レッドブラックツリーのトラバース操作を実装してください：

  1. 中間順序（In-order）
  2. 前順序（Pre-order）
  3. 後順序（Post-order）

演習3: バランスチェック関数の実装

ツリーが正しくバランスされているかどうかをチェックする関数を実装してください。レッドブラックツリーのプロパティをすべて検証する必要があります。

演習4: 応用シナリオの実装

次のシナリオに基づいてレッドブラックツリーを利用するプログラムを作成してください：

  1. 単語の頻度カウンタ：大量のテキストデータから単語の出現回数をカウントし、頻度順に並べ替えるプログラム。
  2. タスクスケジューラ：タスクの優先順位に基づいてタスクを管理するプログラム。

演習問題に取り組むことで、レッドブラックツリーの実装スキルが向上し、応用力が身につきます。次に、本記事のまとめを提供します。

まとめ

本記事では、C言語でのレッドブラックツリーの実装方法について詳しく解説しました。レッドブラックツリーの基本概念から始まり、必要なデータ構造の定義、ノードの挿入と削除、木の回転操作、カラー修正、検索操作、さらに実際の応用例と演習問題まで幅広くカバーしました。これらの知識を活用することで、高速で効率的なデータ操作が可能なアプリケーションを開発できるようになります。今後の学習では、実際にコードを書いて動作を確認し、理解を深めてください。

C言語
プログラミング データ構造 アルゴリズム C言語 レッドブラックツリー

コメント

コメントする

目次