Struktur Data: Pokok Binari di Jawa

Hi hi! Sukar untuk menjadi pengaturcara yang kuat tanpa pengetahuan asas. Dan di sini yang kami maksudkan bukan sahaja pengetahuan tentang sintaks bahasa pengaturcaraan asli, tetapi juga asas dan konsep pengaturcaraan secara umum. Salah satu asas ini ialah algoritma dan struktur data. Sebagai peraturan, ada yang lebih berpengetahuan tentang isu ini, ada yang kurang, tetapi terdapat beberapa maklumat asas yang semua orang perlu tahu. Di antara pangkalan data untuk struktur data, ia pasti bernilai memahami pokok carian binari. Sebenarnya, hari ini kita akan melihat struktur itu sendiri dengan ciri-cirinya dan mengetahui bagaimana anda boleh melaksanakan pokok binari di Java . Mula-mula, mari kita fikirkan apa itu pokok binari. Pohon binari ialah struktur data di mana setiap nod (ibu bapa) mempunyai paling banyak dua anak (waris kanan dan kiri). Dalam amalan, dua jenis pokok binari biasanya digunakan - pokok carian binari dan piramid (timbunan). Hari ini kita akan melihat pokok carian binari.

Kebaikan Pokok Binari

Apakah kelebihan menyimpan data sebagai pepohon carian binari? Bayangkan kita mempunyai buku rujukan 100 halaman dan kita perlu mencari halaman tertentu yang akan mengandungi data yang kita perlukan. Kami juga tahu dari kandungan halaman tertentu yang kami perlukan. Jika kita mengikut jalan biasa, kita perlu membelek satu demi satu halaman sehingga kita sampai ke halaman yang kita perlukan. Maksudnya, kita akan menelusuri dari 1 hingga 100 muka surat sehingga kita mendapati diri kita berada di tempat yang betul. Sebagai contoh, jika kita memerlukan halaman 77, maka kita akan mempunyai 77 carian. Jika kita bercakap tentang kerumitan masa, maka ia akan menjadi O(N) . Tetapi ini boleh dilakukan dengan lebih cekap, bukan? Mari kita cuba melakukan perkara yang sama, tetapi menggunakan carian binari :

1. Kami membahagikan direktori kepada dua bahagian, yang pertama - dari 1 hingga 50, yang kedua - 51-100. Kami tahu dengan tepat bahagian mana halaman kami berada: jika kami mengambil halaman 77 sekali lagi, ia berada di bahagian kedua buku.
2. Seterusnya, kami mempertimbangkan bahagian kedua dan membahagikannya kepada dua - dari 51 hingga 75, dari 76 hingga 100. Dalam kes ini, halaman kami sekali lagi akan berada di separuh kedua, dalam julat 76-100.
3. Seterusnya, kita bahagikan selang ini dengan 2 dan dapatkan 76-88 dan 89-100. Halaman itu sesuai dengan jurang pertama, jadi kami membuang yang kedua.
4. Seterusnya ialah selang: 76-81 dan 82-88, ambil yang pertama.
5. 76-78 dan 79-81, ambil yang pertama.
6. 76 dan 77-78, ambil yang kedua.
7. 77 dan 78, ambil yang pertama dan dapatkan halaman kami - 77.

Daripada 77 langkah, kami hanya memerlukan 7! Kerumitan masa carian ini ialah O(log(N)) .

Peraturan untuk membina pepohon carian binari

Pokok carian binari dibina mengikut peraturan tertentu:

• setiap nod mempunyai paling banyak dua anak;
• setiap nilai yang kurang daripada nilai nod menjadi anak kiri atau anak kepada anak kiri;
• setiap nilai yang lebih besar daripada atau sama dengan nilai nod menjadi anak kanan atau anak kepada anak kanan.

Sebagai contoh, kita mempunyai satu siri nombor dari 1 hingga 10. Mari lihat rupa pokok carian binari untuk siri ini: Mari kita fikirkan sama ada semua syarat pokok binari dipenuhi di sini:

• semua nod tidak mempunyai lebih daripada dua waris, syarat pertama dipenuhi;
• jika kita menganggap, sebagai contoh, nod dengan nilai 7 (atau mana-mana yang lain), kita akan melihat bahawa semua nilai elemen dalam subpokok kiri akan menjadi kurang, dan di kanan - lebih banyak. Ini bermakna syarat 2 dan 3 dipenuhi.

Mari lihat bagaimana operasi asas berlaku - penyisipan, pemadaman, carian.

Cari elemen

Apabila mencari elemen dengan nilai tertentu, kita bermula pada elemen akar:

1. Jika ia sama dengan nilai yang diingini, elemen akar adalah yang dikehendaki; jika tidak, kita bandingkan nilai akar dan yang dikehendaki.
2. Jika elemen yang kita cari lebih besar, kita beralih ke anak kanan, jika tidak, kita beralih ke anak kiri.
3. Jika elemen tidak ditemui, kami menggunakan langkah 1 dan 2, tetapi kali ini kepada kanak-kanak (kanan atau kiri) sehingga elemen ditemui.

Sebagai contoh, dalam pepohon carian binari yang ditunjukkan di atas, kami ingin mencari elemen dengan nilai 5:

• kita membandingkannya dengan elemen akar, kita melihat bahawa unsur akar lebih besar, jadi kita bergerak ke anak kiri, yang mempunyai nilai 3;
• kita bandingkan yang kita cari dan elemen dengan nilai 3, kita nampak yang kita cari lebih besar, jadi kita perlukan keturunan yang betul dari elemen yang dimaksudkan, iaitu elemen dengan nilai 5;
• Kami membandingkan keturunan ini dengan yang kami cari dan melihat bahawa nilainya adalah sama - unsur itu dijumpai.

Memasukkan elemen

Algoritma penyisipan juga sangat, sangat mudah:

1. Kami membandingkan yang baru dengan yang akar (jika ia tidak wujud, unsur yang baru ialah yang akar).

2. Jika elemen baharu:

   • adalah kurang, maka kita pergi ke waris kiri, jika tidak ada, elemen baru mengambil tempat waris kiri, dan algoritma selesai;
   • adalah lebih besar daripada atau sama dengan akar, maka kita beralih kepada waris yang betul. Dan begitu juga, jika elemen ini tidak wujud, maka elemen baru akan menggantikan elemen yang betul dan algoritma selesai.

3. Untuk elemen baharu yang dimaksudkan, yang berada di kanan atau kiri daripada langkah sebelumnya, ulangi langkah 1 dan 2 sehingga elemen yang disisipkan berada di tempatnya.

   Sebagai contoh, kami ingin memasukkan ke dalam pokok yang dipertimbangkan di atas, elemen dengan nilai 11:

   • kita bandingkan dengan unsur akar 7 dan lihat bahawa unsur akar lebih kecil, jadi kita beralih kepada waris yang betul;
   • elemen seterusnya yang sedang dipertimbangkan mempunyai nilai 9, iaitu kurang daripada 11 baharu, jadi kita beralih kepada waris yang betul;
   • waris yang betul mempunyai nilai 10, yang sekali lagi kurang, jadi kita pergi ke elemen pertama, dan kerana ia tidak ada, elemen baru dengan nilai 11 diletakkan di tempat ini.
   ↓

Mengalih keluar elemen

Mungkin, daripada semua operasi dengan pepohon carian binari, pemadaman adalah yang paling sukar. Pertama sekali, terdapat carian untuk elemen yang akan dipadamkan, selepas mendapati peringkat mana yang diikuti, yang boleh mempunyai tiga variasi:

1. Nod yang akan dipadamkan ialah nod daun (tidak mempunyai anak).

   Mungkin yang paling mudah. Semuanya datang kepada fakta bahawa kita hanya memotongnya dari pokok, tanpa manipulasi yang tidak perlu. Sebagai contoh, dari pokok kami, kami mengeluarkan nod dengan nilai 8:

   ↓

2. Nod yang dipadamkan mempunyai seorang anak.

   Dalam kes ini, kami memadamkan nod yang dipilih dan meletakkan keturunannya di tempatnya (pada dasarnya, kami hanya memotong nod yang dipilih dari rantai). Sebagai contoh, mari kita keluarkan nod dengan nilai 9 daripada pokok:

   ↓

3. Nod yang dipadamkan mempunyai dua anak.

   Bahagian yang paling menarik. Lagipun, jika nod yang dipadamkan mempunyai dua anak serentak, anda tidak boleh menggantikannya dengan salah satu daripada kanak-kanak ini (terutamanya jika kanak-kanak itu mempunyai anak sendiri).

   Contoh: Dalam pokok di atas, nod yang manakah harus menjadi anak kiri nod 3?

   Jika anda memikirkannya sedikit, ia menjadi jelas bahawa ini sepatutnya menjadi nod dengan nilai 4. Tetapi bagaimana jika pokok itu tidak begitu mudah? Jika ia memegang ratusan nilai, adakah semudah itu untuk mengetahui siapa penggantinya?

   Ia jelas bahawa tidak. Oleh itu, kami memerlukan algoritma carian penerima kecil kami sendiri:

   1. Mula-mula kita mesti pergi ke anak kanan nod yang dipilih, yang nilainya mestilah lebih besar daripada nilai nod.
   2. Kemudian kita bergerak ke anak kiri anak kanan (jika ada), kemudian ke anak kiri anak kiri, dsb., mengikuti rantai anak kiri.
   3. Sehubungan itu, anak kiri terakhir di laluan ini akan menjadi pengganti nod asal.

   Mari kita umumkan sedikit algoritma ini: dalam subpokok anak kanan nod sumber, semua nod lebih besar daripada yang dipadamkan, yang boleh difahami daripada peraturan asas pepohon carian binari. Dalam subtree ini kita sedang mencari nilai terkecil.

   Dalam erti kata lain, kita sedang mencari nod terkecil dalam set nod yang lebih besar daripada nod asal. Nod terkecil ini antara yang lebih besar akan menjadi pengganti yang paling sesuai.

   Apakah rupa pokok selepas mengalih keluar nod dengan nilai 3:

   ↓

Kini tiba masanya untuk beralih dari amalan kepada teori. Mari kita lihat bagaimana kita boleh memetakan struktur data ini dalam Java. Kelas nod tunggal:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет meaning :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Tiada yang terlalu rumit: setiap elemen mempunyai pautan ke anak kiri dan kanannya. Dan sekarang, mungkin, kelas yang paling penting ialah kelas pokok:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент or не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // or движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим meaningм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём How текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное meaning расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его meaning в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Sekali lagi, tiada yang terlalu rumit. Operasi pepohon carian binari yang diterangkan sebelum ini hadir, ditambah kaedah untuk memaparkan pepohon dalam konsol. Nah, sekarang mari kita lihat pokok yang sedang beraksi:

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Operasi carian/sisipkan/padam dalam pepohon carian binari mempunyai kerumitan masa O(log(N)) . Tetapi itulah senario kes terbaik. Secara umum, kerumitan masa operasi berjulat dari O(log(N)) hingga O(N) . Ia bergantung kepada tahap degenerasi pokok.

Apakah pokok yang merosot?

Ini ialah pokok di mana unsur-unsur jatuh apabila ditambah pada kedudukan nod paling kiri (bilangan terkecil) atau nod paling besar (terbesar). Ini boleh berlaku jika, sebagai contoh, keseluruhan pokok kiri kosong pada setiap peringkat, terdapat hanya pokok kanan, yang mana pokok itu merosot menjadi senarai (menuju ke kanan). Ya, ini adalah cara pokok yang rosak menjadi senarai yang dipautkan secara berkesan, di mana setiap elemen hanya mengetahui tentang yang seterusnya. Dalam kes ini, semua operasi pada struktur ini menghampiri kerumitan masa O(N) .

Dalam kes apakah pokok boleh merosot?

Contohnya, jika anda menambah senarai elemen yang diisih. Jika senarai diisih dalam tertib menaik, maka akar akan menjadi yang pertama, masing-masing terkecil. Yang seterusnya selepasnya akan mengambil kedudukan anak yang betul. Dan yang berikutnya akan lebih besar daripada yang kedua dan akan mengambil kedudukan pengganti kanannya, dan seterusnya... Jika senarai itu dalam susunan menurun, maka perkara yang sama akan berlaku, tetapi dengan elemen paling kiri. Untuk mengelakkan ini, selepas menerima beberapa elemen, anda boleh mencampurkannya. Kemudian pengisihan akan hilang, dan nombor akan lebih kurang sama rata di seluruh pokok. Itu sahaja untuk hari ini, terima kasih atas perhatian anda!