JavaRush /Java Blog /Random-ID /Struktur Data: Pohon Biner di Java

Level 36

28 Februari 2021
43 views
0 comments

Struktur Data: Pohon Biner di Java

Hai Hai! Sulit menjadi programmer yang kuat tanpa pengetahuan dasar. Dan yang kami maksud di sini tidak hanya pengetahuan tentang sintaks bahasa pemrograman asli, tetapi juga dasar-dasar dan konsep pemrograman secara umum. Salah satu fondasinya adalah algoritma dan struktur data. Biasanya, ada yang lebih berpengetahuan tentang masalah ini, ada yang kurang, namun ada beberapa informasi dasar yang harus diketahui semua orang. Di antara database untuk struktur data, sangat penting untuk memahami pohon pencarian biner. Struktur Data: Pohon Biner di Java - 1

Sebenarnya, hari ini kita akan melihat struktur itu sendiri beserta fitur-fiturnya dan mencari tahu bagaimana Anda dapat mengimplementasikan pohon biner di Java . Pertama, mari kita pahami apa itu pohon biner. Pohon biner adalah struktur data yang setiap node (induk) mempunyai paling banyak dua anak (pewaris kanan dan kiri). Struktur Data: Pohon Biner di Java - 2

Dalam praktiknya, dua jenis pohon biner yang umum digunakan - pohon pencarian biner dan piramida (heap). Hari ini kita akan melihat pohon pencarian biner.

Manfaat Pohon Biner

Apa keuntungan menyimpan data sebagai pohon pencarian biner? Bayangkan kita memiliki buku referensi setebal 100 halaman dan kita perlu mencari halaman tertentu yang berisi data yang kita butuhkan. Kami juga mengetahui dari konten halaman spesifik mana yang kami butuhkan. Jika kita mengikuti jalur biasa, kita harus membalik halaman demi halaman sampai kita mendapatkan halaman yang kita butuhkan. Artinya, kita akan menelusuri dari 1 hingga 100 halaman sampai kita menemukan diri kita di tempat yang tepat. Misal kita membutuhkan halaman 77, maka kita akan memiliki 77 pencarian. Jika kita berbicara tentang kompleksitas waktu, maka itu adalah O(N) . Tapi ini bisa dilakukan dengan lebih efisien, bukan? Mari kita coba melakukan hal yang sama, tetapi menggunakan pencarian biner :

Kami membagi direktori menjadi dua bagian, yang pertama - dari 1 hingga 50, yang kedua - 51-100. Kita tahu persis di bagian mana halaman kita berada: jika kita mengambil halaman 77 lagi, itu ada di bagian kedua buku ini.
Selanjutnya, kita perhatikan bagian kedua dan membaginya menjadi dua - dari 51 hingga 75, dari 76 hingga 100. Dalam hal ini, halaman kita akan kembali berada di babak kedua, di kisaran 76-100.
Selanjutnya, kita membagi interval ini dengan 2 dan mendapatkan 76-88 dan 89-100. Halaman tersebut cocok dengan celah pertama, jadi kami membuang celah kedua.
Berikutnya adalah intervalnya: 76-81 dan 82-88, ambil yang pertama.
76-78 dan 79-81, ambil yang pertama.
76 dan 77-78, ambil yang kedua.
77 dan 78, ambil yang pertama dan dapatkan halaman kami - 77.

Daripada 77 langkah, kami hanya membutuhkan 7! Kompleksitas waktu pencarian ini adalah O(log(N)) .

Aturan untuk membangun pohon pencarian biner

Pohon pencarian biner dibangun berdasarkan aturan tertentu:

setiap node mempunyai paling banyak dua anak;
setiap nilai yang kurang dari nilai simpul menjadi anak kiri atau anak dari anak kiri;
setiap nilai yang lebih besar atau sama dengan nilai node menjadi anak kanan atau anak dari anak kanan.

Misalnya, kita mempunyai rangkaian angka dari 1 hingga 10. Mari kita lihat seperti apa pohon pencarian biner untuk rangkaian ini: Struktur Data: Pohon Biner di Java - 3

Mari kita pikirkan apakah semua kondisi pohon biner terpenuhi di sini:

semua node memiliki tidak lebih dari dua ahli waris, syarat pertama terpenuhi;
jika kita mempertimbangkan, misalnya, sebuah node dengan nilai 7 (atau lainnya), kita akan melihat bahwa semua nilai elemen di subpohon kiri akan lebih kecil, dan di subpohon kanan - lebih banyak. Artinya syarat 2 dan 3 terpenuhi.

Mari kita lihat bagaimana operasi dasar terjadi - penyisipan, penghapusan, pencarian.

Cari sebuah elemen

Saat mencari elemen dengan nilai tertentu, kita mulai dari elemen root:

Jika sama dengan nilai yang dicari maka elemen akarlah yang dicari, jika tidak maka kita bandingkan nilai akar dan nilai yang dicari.
Jika elemen yang kita cari lebih besar, kita pindah ke anak kanan; jika tidak, kita pindah ke anak kiri.
Jika elemen tidak ditemukan, terapkan langkah 1 dan 2, namun pada anak (kanan atau kiri) hingga elemen ditemukan.

Misalnya, pada pohon pencarian biner yang ditunjukkan di atas, kita ingin mencari elemen dengan nilai 5:

kita bandingkan dengan elemen root, kita lihat elemen root lebih besar, jadi kita pindah ke anak kiri yang nilainya 3;
kita bandingkan antara yang kita cari dengan elemen yang bernilai 3, kita lihat yang kita cari lebih besar, sehingga diperlukan turunan yang tepat dari elemen yang dimaksud yaitu elemen yang bernilai 5;
Kami membandingkan keturunan ini dengan yang kami cari dan melihat bahwa nilainya sama - elemen ditemukan.

Memasukkan elemen

Algoritma penyisipannya juga sangat, sangat sederhana:

Kita bandingkan yang baru dengan yang root (jika tidak ada, elemen baru adalah yang root).
Jika elemen baru:
- kurang, maka kita pergi ke ahli waris kiri, jika tidak ada, elemen baru menggantikan ahli waris kiri, dan algoritma selesai;
- lebih besar atau sama dengan akar, maka kita pindah ke ahli waris yang tepat. Demikian pula, jika elemen ini tidak ada, maka elemen baru akan menggantikan elemen yang tepat dan algoritme selesai.
Untuk elemen baru yang dimaksud yang berada di kanan atau kiri dari langkah sebelumnya, ulangi langkah 1 dan 2 hingga elemen yang dimasukkan berada pada tempatnya.

Sebagai contoh, kita ingin memasukkan ke dalam pohon yang dibahas di atas, sebuah elemen dengan nilai 11:
- kita bandingkan dengan elemen akar 7 dan melihat bahwa elemen akar lebih kecil, jadi kita beralih ke pewaris kanan;
- unsur berikutnya yang dipertimbangkan bernilai 9, lebih kecil dari 11 yang baru, maka kita beralih ke ahli waris yang tepat;
- ahli waris yang tepat mempunyai nilai 10, yang lagi-lagi lebih kecil, jadi kita lanjutkan ke elemen pertama, dan karena tidak ada, elemen baru dengan nilai 11 ditempatkan di tempat ini.
↓

Menghapus sebuah elemen

Mungkin, dari semua operasi dengan pohon pencarian biner, penghapusan adalah yang paling sulit. Pertama-tama, ada pencarian elemen yang akan dihapus, setelah ditemukan tahapan berikutnya, yang dapat memiliki tiga variasi:

Node yang akan dihapus adalah node daun (tidak mempunyai anak).

Mungkin yang paling sederhana. Semuanya bermuara pada kenyataan bahwa kita hanya memotongnya dari pohon, tanpa manipulasi yang tidak perlu. Misalnya, dari pohon kita, kita menghapus simpul dengan nilai 8:
↓
Node yang dihapus mempunyai satu anak.

Dalam hal ini, kita menghapus node yang dipilih dan menempatkan turunannya pada tempatnya (intinya, kita cukup memotong node yang dipilih dari rantai). Sebagai contoh, mari kita hapus sebuah node dengan nilai 9 dari pohon:
↓
Node yang dihapus mempunyai dua anak.

Bagian yang paling menarik. Lagi pula, jika node yang dihapus memiliki dua anak sekaligus, Anda tidak bisa begitu saja menggantinya dengan salah satu dari anak tersebut (terutama jika anak tersebut memiliki anak sendiri).

Contoh: Pada pohon di atas, node mana yang merupakan anak kiri dari node 3?

Jika Anda memikirkannya sedikit, menjadi jelas bahwa ini seharusnya adalah sebuah node dengan nilai 4. Tetapi bagaimana jika pohonnya tidak sesederhana itu? Jika ia memiliki ratusan nilai, apakah semudah itu mengetahui siapa penerusnya?

Jelas tidak. Oleh karena itu, kita memerlukan algoritma pencarian receiver kecil kita sendiri:
1. Pertama kita harus pergi ke anak kanan dari node yang dipilih, yang nilainya harus lebih besar dari nilai node tersebut.
2. Lalu kita pergi ke anak kiri dari anak kanan (jika ada), lalu ke anak kiri dari anak kiri, dan seterusnya, mengikuti rantai anak kiri.
3. Oleh karena itu, anak terakhir yang tersisa pada jalur ini akan menjadi penerus node asli.
Mari kita menggeneralisasi algoritma kecil ini sedikit: di subpohon dari anak kanan dari node sumber, semua node lebih besar dari yang dihapus, yang dapat dipahami dari aturan dasar pohon pencarian biner. Pada subpohon ini kita mencari nilai terkecil.

Dengan kata lain, kita mencari node terkecil dalam kumpulan node yang lebih besar dari node aslinya. Node terkecil di antara node terbesar ini akan menjadi penerus yang paling cocok.

Seperti apa tampilan pohon setelah menghapus node dengan nilai 3:
↓

Sekarang saatnya beralih dari praktik ke teori. Mari kita lihat bagaimana kita memetakan struktur data ini di Java. Kelas simpul 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 +
               '}';
   }
}

Tidak ada yang terlalu rumit: setiap elemen memiliki link ke anak kiri dan kanannya. Dan sekarang, mungkin, kelas yang paling penting adalah kelas pohon:

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, tidak ada yang terlalu rumit. Operasi pohon pencarian biner yang dijelaskan sebelumnya ada, ditambah metode untuk menampilkan pohon di konsol. Nah, sekarang mari kita lihat aksi pohon tersebut:

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 pencarian/masukkan/hapus dalam pohon pencarian biner memiliki kompleksitas waktu O(log(N)) . Tapi itulah skenario terbaik. Secara umum, kompleksitas waktu operasi berkisar dari O(log(N)) hingga O(N) . Hal ini tergantung pada tingkat degenerasi pohon.

Apa itu pohon yang merosot?

Ini adalah pohon yang unsur-unsurnya jatuh jika dijumlahkan dengan posisi simpul paling kiri (angka terkecil) atau simpul paling besar (terbesar). Hal ini dapat terjadi jika, misalnya, seluruh pohon kiri kosong di setiap tingkat, hanya ada pohon kanan, dalam hal ini pohon tersebut merosot menjadi daftar (menuju ke kanan). Ya, beginilah cara pohon yang mengalami degenerasi secara efektif menjadi daftar tertaut tunggal, di mana setiap elemen hanya mengetahui elemen di sebelahnya. Dalam hal ini, semua operasi pada struktur ini mendekati kompleksitas waktu O(N) .

Dalam kasus apa pohon bisa mengalami degenerasi?

Misalnya, jika Anda menambahkan daftar elemen yang diurutkan. Jika daftar diurutkan dalam urutan menaik, maka akarnya akan menjadi yang pertama, dan masing-masing menjadi yang terkecil. Yang berikutnya setelah dia akan mengambil posisi sebagai anak yang tepat. Dan yang berikutnya akan lebih besar dari yang kedua dan akan mengambil posisi penerus kanannya, dan seterusnya... Jika daftarnya dalam urutan menurun, maka hal yang sama akan terjadi, tetapi dengan elemen paling kiri. Untuk menghindari hal ini, setelah menerima sejumlah elemen, Anda cukup mencampurkannya. Kemudian penyortiran akan hilang, dan jumlahnya akan tersebar merata di seluruh pohon. Struktur Data: Pohon Biner di Java - 13

Sekian untuk hari ini, terima kasih atas perhatiannya!

Komentar

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION