Comment implémenter l'algorithme d'arbre rouge-noir en utilisant Java

Comment utiliser Java pour implémenter l'algorithme de l'arbre rouge-noir

L'arbre rouge-noir est un arbre de recherche binaire auto-équilibré qui est largement utilisé dans de nombreuses structures de données et algorithmes hautes performances. Cet article présentera en détail comment implémenter l'algorithme d'arbre rouge-noir à l'aide du langage Java et donnera des exemples de code spécifiques.

1. Définition de l'arbre rouge-noir

Un arbre rouge-noir est un arbre de recherche binaire, qui présente les caractéristiques suivantes :

1. Chaque nœud a une couleur, soit rouge, soit noire ;
2. Chaque nœud feuille (nœud NIL, c'est-à-dire un nœud vide) est noir ;
3. Si un nœud est rouge, alors ses deux nœuds enfants sont noirs
4. Pour chaque nœud, chemins simples de ce nœud à tous ses descendants ; les nœuds feuilles contiennent le même nombre de nœuds noirs.
5. Ces caractéristiques assurent l'équilibre de l'arbre rouge-noir, en gardant la hauteur de l'arbre au niveau O(log n).

2. Opérations de base des arbres rouge-noir

Les arbres rouge-noir comprennent principalement les opérations de base suivantes :

Insérer : insérez un nœud dans l'arbre rouge-noir, et les caractéristiques de l'arbre rouge-noir doivent être maintenu ;

1. Supprimer : de Pour supprimer un nœud dans l'arbre rouge-noir, vous devez conserver les caractéristiques de l'arbre rouge-noir
2. Rechercher : rechercher un nœud spécifié dans l'arbre rouge-noir
3. Insertion ; réparation : les caractéristiques de l'arbre rouge-noir peuvent être détruites en raison de l'insertion, et vous devez passer une réparation par opération en série 
4. Réparation par suppression : les caractéristiques de l'arbre rouge-noir peuvent être endommagées en raison d'une suppression, qui doit être effectuée ; être réparé par une série d’opérations.
5. Ce qui suit est un exemple de code d'utilisation du langage Java pour implémenter un arbre rouge-noir :

// 定义红黑树节点类
class Node {
    int key;
    Node parent;
    Node left;
    Node right;
    boolean isRed; // 红色节点为true，黑色节点为false

    public Node(int key) {
        this.key = key;
        this.parent = null;
        this.left = null;
        this.right = null;
        this.isRed = true; // 默认插入的节点为红色节点
    }
}

// 定义红黑树类
class RedBlackTree {
    private Node root;
    private final Node NIL;

    public RedBlackTree() {
        NIL = new Node(-1); // 定义一个表示NIL节点的对象
        NIL.isRed = false; // NIL节点为黑色节点
        root = NIL;
    }

    // 插入节点
    public void insert(int key) {
        Node node = new Node(key);
        Node current = root;
        Node parent = null;
        while (current != NIL) {
            parent = current;
            if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        node.parent = parent;
        if (parent == null) {
            root = node;
        } else if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.left = NIL;
        node.right = NIL;
        node.isRed = true;
        insertFixup(node);
    }

    // 插入修复
    private void insertFixup(Node node) {
        while (node.parent.isRed) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (uncle.isRed) { // Case 1: 叔节点为红色
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        leftRotate(node);
                    }
                    node.parent.isRed = false;
                    node.parent.parent.isRed = true;
                    rightRotate(node.parent.parent);
                }
            } else {
                Node uncle = node.parent.parent.left;
                if (uncle.isRed) { // Case 1: 叔节点为红色
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rightRotate(node);
                    }
                    node.parent.isRed = false;
                    node.parent.parent.isRed = true;
                    leftRotate(node.parent.parent);
                }
            }
        }
        root.isRed = false;
    }

    // 左旋转
    private void leftRotate(Node node) {
        Node child = node.right;
        node.right = child.left;
        if (child.left != NIL) {
            child.left.parent = node;
        }
        child.parent = node.parent;
        if (node.parent == NIL) {
            root = child;
        } else if (node == node.parent.left) {
            node.parent.left = child;
        } else {
            node.parent.right = child;
        }
        child.left = node;
        node.parent = child;
    }

    // 右旋转
    private void rightRotate(Node node) {
        Node child = node.left;
        node.left = child.right;
        if (child.right != NIL) {
            child.right.parent = node;
        }
        child.parent = node.parent;
        if (node.parent == NIL) {
            root = child;
        } else if (node == node.parent.right) {
            node.parent.right = child;
        } else {
            node.parent.left = child;
        }
        child.right = node;
        node.parent = child;
    }

    // 查找节点
    public Node search(int key) {
        Node current = root;
        while (current != NIL && key != current.key) {
            if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }
}

// 测试红黑树的代码
public class Main {
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        tree.insert(60);
        tree.insert(70);
        Node node = tree.search(50);
        if (node != tree.NIL) {
            System.out.println("找到了节点：" + node.key);
        } else {
            System.out.println("没有找到节点");
        }
    }
}

Le résultat de l'exécution du code de test est : "Nœud trouvé : 50", indiquant que les opérations d'insertion et de recherche du les arbres rouge-noir sont normaux.

Compilez et exécutez le code ci-dessus en tant que fichier de classe Java pour réaliser les opérations d'insertion et de recherche de l'arborescence rouge-noir. Nous pouvons également ajouter des opérations de suppression et du code de réparation de suppression selon les besoins.

Résumé :

Cet article présente la définition et les opérations de base des arbres rouge-noir, et donne des exemples de code pour implémenter des arbres rouge-noir à l'aide de Java. En tant qu'arbre de recherche binaire auto-équilibré, l'arbre rouge-noir joue un rôle important dans le traitement de grandes quantités de données et dans les algorithmes hautes performances. La maîtrise des principes et de la mise en œuvre des arbres rouge-noir nous aidera à mieux comprendre la conception et l'application des structures de données et des algorithmes. J'espère que cet article sera utile aux lecteurs.

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!