Rumah >Java >javaTutorial >Bagaimana untuk melaksanakan algoritma pokok merah-hitam menggunakan java
Cara menggunakan Java untuk melaksanakan algoritma pepohon merah-hitam
Pokok merah-hitam ialah pepohon carian binari pengimbangan diri yang digunakan secara meluas dalam banyak struktur dan algoritma data berprestasi tinggi. Artikel ini akan memperkenalkan secara terperinci cara menggunakan bahasa Java untuk melaksanakan algoritma pokok merah-hitam dan memberikan contoh kod khusus.
1. Definisi pokok merah-hitam
Pokok merah-hitam ialah pokok carian binari, yang mempunyai ciri-ciri berikut:
Pokok merah-hitam terutamanya termasuk operasi asas berikut:
Sisipkan: masukkan nod ke dalam pokok merah-hitam, dan ciri-ciri pokok merah-hitam perlu dikekalkan; Padam: dari Untuk memadamkan nod dalam pokok merah-hitam, anda perlu mengekalkan ciri-ciri pokok merah-hitam// 定义红黑树节点类 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("没有找到节点"); } } }
Ringkasan:
Artikel ini memperkenalkan definisi dan operasi asas pokok merah-hitam, dan memberikan contoh kod untuk melaksanakan pokok merah-hitam menggunakan Java. Sebagai pepohon carian perduaan pengimbangan diri, pokok merah-hitam memainkan peranan penting dalam memproses sejumlah besar data dan algoritma berprestasi tinggi. Menguasai prinsip dan pelaksanaan pokok merah-hitam akan membantu kami lebih memahami reka bentuk dan aplikasi struktur dan algoritma data. Semoga artikel ini bermanfaat kepada pembaca.
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pokok merah-hitam menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!