Comment implémenter l'algorithme d'arbre rouge-noir en C#-Tutoriel C#.Net-php.cn

Comment implémenter l'algorithme d'arbre rouge-noir en C#

WBOY

Libérer： 2023-09-19 12:57:46

original

1401 Les gens l'ont consulté

Comment implémenter lalgorithme darbre rouge-noir en C#

Comment implémenter l'algorithme de l'arbre rouge-noir en C# nécessite des exemples de code spécifiques

Introduction :
L'arbre rouge-noir est un arbre de recherche binaire auto-équilibré. Il maintient la propriété spécifique telle que pour tout arbre rouge-noir valide, le chemin le plus long n'est jamais plus de deux fois le chemin le plus court. Cette caractéristique permet aux arbres rouge-noir d'avoir de meilleures performances dans les opérations d'insertion, de suppression et de recherche. Cet article explique comment implémenter l'algorithme d'arbre rouge-noir en C# et fournit des exemples de code spécifiques.

Propriétés des arbres rouge-noir :
Les arbres rouge-noir ont les 5 propriétés suivantes :

Chaque nœud est soit rouge, soit noir.
Le nœud racine est noir.
Chaque nœud feuille (nœud NIL, nœud vide) est noir.
Si un nœud est rouge, ses deux nœuds enfants sont noirs.
Pour chaque nœud, le chemin simple de ce nœud à tous ses nœuds feuilles descendants contient le même nombre de nœuds noirs.

Implémentation de l'arbre rouge-noir :
Ce qui suit est un exemple de code pour implémenter l'arbre rouge-noir en 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;
    }

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

}

Copier après la connexion

Résumé :
Cet article présente comment implémenter l'algorithme d'arbre rouge-noir en C# et fournit un code détaillé exemples. L'arbre rouge-noir est un arbre de recherche binaire auto-équilibré avec de meilleures performances dans les opérations d'insertion, de suppression et de recherche. En utilisant des arbres rouge-noir, nous pouvons résoudre plus efficacement certains problèmes courants. Dans les applications pratiques, nous pouvons ajuster et étendre de manière appropriée les fonctions de l’arbre rouge-noir selon les besoins. J'espère que cet article vous sera utile et suscitera votre intérêt et vos recherches approfondies sur les arbres rouge-noir.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!