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:

1. Setiap nod mempunyai warna, sama ada merah atau hitam
2. nod akar berwarna hitam;
3. Every Leaf Node (nod nod, iaitu, nod kosong) adalah hitam; nod daun mengandungi bilangan nod hitam yang sama.
4. Ciri-ciri ini memastikan keseimbangan pokok merah-hitam, mengekalkan ketinggian pokok pada tahap O(log n).
5. 2. Operasi asas pokok merah-hitam

Pokok merah-hitam terutamanya termasuk operasi asas berikut:

1. Cari: Cari nod yang ditentukan dalam pokok merah-hitam; pembaikan: Ciri-ciri pokok merah-hitam mungkin musnah akibat pemadaman, dan anda perlu lulus pembaikan operasi Siri
2. Pembaikan pemadaman: Ciri-ciri pokok merah-hitam mungkin rosak akibat pemadaman, dan ia memerlukan; untuk dibaiki melalui beberapa siri operasi.
3. Berikut ialah contoh kod menggunakan bahasa Java untuk melaksanakan pokok merah-hitam:

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

   Salin selepas log masuk
Hasil keluaran menjalankan kod ujian ialah: "Nod found: 50", menunjukkan bahawa operasi sisipan dan carian bagi pokok merah-hitam adalah perkara biasa.
5. Kompil dan jalankan kod di atas sebagai fail kelas Java untuk merealisasikan operasi sisipan dan carian bagi pokok merah-hitam. Kami juga boleh menambah operasi pemadaman dan kod pembaikan pemadaman mengikut keperluan.

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!