So implementieren Sie den Rot-Schwarz-Baum-Algorithmus mit Java

So implementieren Sie den Rot-Schwarz-Baum-Algorithmus mit Java

Der Rot-Schwarz-Baum ist ein selbstausgleichender binärer Suchbaum, der in vielen Hochleistungsdatenstrukturen und -algorithmen weit verbreitet ist. In diesem Artikel wird detailliert beschrieben, wie der Rot-Schwarz-Baum-Algorithmus mithilfe der Java-Sprache implementiert wird, und es werden spezifische Codebeispiele gegeben.

1. Definition eines Rot-Schwarz-Baums

Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, der die folgenden Eigenschaften aufweist:

1. Jeder Knoten hat eine Farbe, entweder rot oder schwarz;
2. Wurzelknoten ist schwarz;
3. Jeder Blattknoten (NIL-Knoten, also ein leerer Knoten) ist schwarz.
4. Wenn ein Knoten rot ist, sind seine beiden untergeordneten Knoten schwarz.
5. Für jeden Knoten sind einfache Pfade von diesem Knoten zu allen seinen Nachkommen Blattknoten enthalten die gleiche Anzahl schwarzer Knoten.

Diese Eigenschaften stellen das Gleichgewicht des rot-schwarzen Baums sicher und halten die Höhe des Baums auf dem O(log n)-Niveau.

2. Grundoperationen von rot-schwarzen Bäumen

Rot-schwarze Bäume umfassen hauptsächlich die folgenden Grundoperationen:

1. Einfügen: Fügen Sie einen Knoten in den rot-schwarzen Baum ein, und die Eigenschaften des rot-schwarzen Baums müssen berücksichtigt werden gepflegt werden;
2. Löschen: Um einen Knoten im rot-schwarzen Baum zu löschen, müssen Sie die Eigenschaften des rot-schwarzen Baums beibehalten.
3. Suchen: Suchen Sie einen bestimmten Knoten im rot-schwarzen Baum Reparatur: Die Eigenschaften des rot-schwarzen Baums können durch das Einfügen zerstört werden, und Sie müssen eine Serienreparatur durchführen.
4. Löschungsreparatur: Die Eigenschaften des rot-schwarzen Baums können durch das Löschen beschädigt werden, was erforderlich ist durch eine Reihe von Arbeitsgängen repariert werden.
5. Das Folgende ist ein Codebeispiel für die Verwendung der Java-Sprache zum Implementieren eines Rot-Schwarz-Baums:

// 定义红黑树节点类
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("没有找到节点");
        }
    }
}

Das Ausgabeergebnis der Ausführung des Testcodes lautet: „Knoten gefunden: 50“, was darauf hinweist, dass die Einfügungs- und Suchvorgänge des rot-schwarzer Baum sind normal.

Kompilieren Sie den obigen Code und führen Sie ihn als Java-Klassendatei aus, um die Einfüge- und Suchvorgänge des Rot-Schwarz-Baums zu realisieren. Bei Bedarf können wir auch Löschvorgänge und Löschreparaturcodes hinzufügen.

Zusammenfassung:

Dieser Artikel stellt die Definition und Grundoperationen von Rot-Schwarz-Bäumen vor und gibt Codebeispiele für die Implementierung von Rot-Schwarz-Bäumen mit Java. Als selbstausgleichender binärer Suchbaum spielt der Rot-Schwarz-Baum eine wichtige Rolle bei der Verarbeitung großer Datenmengen und leistungsstarken Algorithmen. Die Beherrschung der Prinzipien und Implementierung von Rot-Schwarz-Bäumen wird uns helfen, den Entwurf und die Anwendung von Datenstrukturen und Algorithmen besser zu verstehen. Ich hoffe, dieser Artikel ist für die Leser hilfreich.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Rot-Schwarz-Baum-Algorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!