C# で赤黒ツリー アルゴリズムを実装する方法

C# で赤黒ツリー アルゴリズムを実装するには、特定のコード サンプルが必要です

はじめに:
赤黒ツリーは、自己平衡型二分探索です。木 。これは、有効な赤黒ツリーの場合、最長パスが最短パスの 2 倍を超えないという特定のプロパティを維持します。この特性により、赤黒ツリーの挿入、削除、検索操作のパフォーマンスが向上します。この記事では、C# で赤黒ツリー アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。

赤黒ツリーのプロパティ:
赤黒ツリーには次の 5 つのプロパティがあります:

1. 各ノードは赤または黒です。
2. ルート ノードは黒です。
3. 各リーフ ノード (NIL ノード、空のノード) は黒です。
4. ノードが赤の場合、その子ノードは両方とも黒になります。
5. 各ノードについて、そのノードからすべての子孫リーフ ノードへの単純なパスには、同じ数の黒いノードが含まれます。

赤黒ツリーの実装:
以下は、C# で赤黒ツリーを実装するサンプル コードです:

enum Color
{
    Red,
    Black
}

class Node
{
    public int key;
    public Node parent;
    public Node left;
    public Node right;
    public Color color;

    public Node(int key)
    {
        this.key = key;
        color = Color.Black;
    }
}

class RedBlackTree
{
    private Node root;

    private void Insert(Node newNode)
    {
        Node current = root;
        Node parent = null;

        while (current != null)
        {
            parent = current;

            if (newNode.key < current.key)
                current = current.left;
            else
                current = current.right;
        }

        newNode.parent = parent;

        if (parent == null)
            root = newNode;
        else if (newNode.key < parent.key)
            parent.left = newNode;
        else
            parent.right = newNode;

        newNode.color = Color.Red;

        FixAfterInsertion(newNode);
    }

    private void FixAfterInsertion(Node newNode)
    {
        while (newNode != root && newNode.parent.color == Color.Red)
        {
            if (newNode.parent == newNode.parent.parent.left)
            {
                Node uncle = newNode.parent.parent.right;

                if (uncle != null && uncle.color == Color.Red)
                {
                    newNode.parent.color = Color.Black;
                    uncle.color = Color.Black;
                    newNode.parent.parent.color = Color.Red;
                    newNode = newNode.parent.parent;
                }
                else
                {
                    if (newNode == newNode.parent.right)
                    {
                        newNode = newNode.parent;
                        RotateLeft(newNode);
                    }

                    newNode.parent.color = Color.Black;
                    newNode.parent.parent.color = Color.Red;
                    RotateRight(newNode.parent.parent);
                }
            }
            else
            {
                Node uncle = newNode.parent.parent.left;

                if (uncle != null && uncle.color == Color.Red)
                {
                    newNode.parent.color = Color.Black;
                    uncle.color = Color.Black;
                    newNode.parent.parent.color = Color.Red;
                    newNode = newNode.parent.parent;
                }
                else
                {
                    if (newNode == newNode.parent.left)
                    {
                        newNode = newNode.parent;
                        RotateRight(newNode);
                    }

                    newNode.parent.color = Color.Black;
                    newNode.parent.parent.color = Color.Red;
                    RotateLeft(newNode.parent.parent);
                }
            }
        }

        root.color = Color.Black;
    }

    private void RotateLeft(Node node)
    {
        Node right = node.right;
        node.right = right.left;

        if (right.left != null)
            right.left.parent = node;

        right.parent = node.parent;

        if (node.parent == null)
            root = right;
        else if (node == node.parent.left)
            node.parent.left = right;
        else
            node.parent.right = right;

        right.left = node;
        node.parent = right;
    }

    private void RotateRight(Node node)
    {
        Node left = node.left;
        node.left = left.right;

        if (left.right != null)
            left.right.parent = node;

        left.parent = node.parent;

        if (node.parent == null)
            root = left;
        else if (node == node.parent.right)
            node.parent.right = left;
        else
            node.parent.left = left;

        left.right = node;
        node.parent = left;
    }

    // 其他方法：查找、删除等
    // ...

}

概要:
この記事では、その方法を紹介します。 C# で赤黒ツリーを実装するには 赤黒ツリー アルゴリズムを実装し、詳細なコード例を提供します。赤黒ツリーは、挿入、削除、検索操作のパフォーマンスが向上した自己平衡型二分探索ツリーです。赤黒ツリーを使用すると、いくつかの一般的な問題をより効率的に解決できます。実際のアプリケーションでは、必要に応じて赤黒ツリーの機能を適切に調整および拡張できます。この記事があなたのお役に立ち、赤黒木についての興味と深い研究のきっかけになれば幸いです。

以上がC# で赤黒ツリー アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。