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:
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:
// 定义红黑树节点类
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!
