Binary Search Tree in Java

Halo Arek Blodhil! bertemu lagi kita. Pada hari ini kita akan belajar Binary Search Tree dalam Java! Binary Search Tree (selanjutnya disebut BST) adalah jenis pohon biner. Ini juga dapat didefinisikan sebagai pohon biner berbasis node. BST juga disebut sebagai 'Ordered Binary Tree'. Dalam BST, semua node dalam subtree kiri memiliki values yang kurang dari value root node. Demikian pula, semua simpul dari subtree kanan BST memiliki nilai yang lebih besar dari nilai root node. Urutan node ini harus true untuk masing-masing subtree juga. Mari kita terjun lebih dalam lagi Arek Blodhil!

Binary Search Tree In Java

BST tidak mengizinkan node duplikat.

Diagram di bawah ini menunjukkan Representasi BST:

Di samping ditampilkan sampel BST. Kita melihat bahwa 20 adalah root node dari pohon ini. Subtree kiri memiliki semua nilai node yang kurang dari 20. Subtree kanan memiliki semua node yang lebih besar dari 20. Kita dapat mengatakan bahwa pohon di samping memenuhi properti BST.

Struktur data BST dianggap sangat efisien jika dibandingkan dengan Array dan Linked list dalam hal insertion/deletion dan searching item.

BST membutuhkan waktu O(log n) untuk mencari sebuah elemen. Saat elemen diurutkan, setengah dari subtree dibuang di setiap langkah saat mencari elemen. Hal ini menjadi mungkin karena kita dapat dengan mudah menentukan lokasi kasar dari elemen yang akan dicari.

Demikian pula, operasi penyisipan dan penghapusan lebih efisien di BST. Saat kita ingin menyisipkan elemen baru, kira-kira kita tahu di subtree mana (kiri atau kanan) kita akan insert elemen.

Membuat Binary Search Tree (BST)

diberikan array elemen, kita perlu membuat BST. Arek Blodhil bisa membuat dan visualisasi cara kerja Binary Search Tree menggunakan Binary Search Tree Visualization.

Operasi Binary Search Tree

Dari Binary Search Tree yang Arek Blodhil buat, terdapat beberapa operasi yang didukung BST. Tabel berikut menunjukkan metode yang didukung oleh BST di Java.
Metode/operasiDeskripsi
InsertTambahkan elemen ke BST dengan tidak melanggar properti BST.
DeleteHapus node tertentu dari BST. Node dapat berupa root node, non-leaf, atau leaf node.
SearchCari lokasi elemen yang terdapat dalam BST. Operasi ini memeriksa apakah pohon berisi key yang ditentukan.

Insert Elemen Dalam BST 

Sebuah elemen selalu disisipkan sebagai leaf node di BST.
Diberikan di bawah ini adalah langkah-langkah untuk insert elemen.
  1. Mulai dari root. 
  2. Bandingkan elemen yang akan ingin di-insert dengan root node. Jika lebih kecil dari root, maka telusuri subtree kiri atau telusuri subtree kanan. 
  3. Traverse subtree sampai akhir subtree yang diinginkan. Masukkan node di subtree yang sesuai sebagai leaf node.

Operasi Search Dalam BST

Untuk mencari apakah sebuah elemen ada dalam BST, kita kembali memulai dari root dan kemudian traverse subtree kiri atau kanan tergantung pada apakah elemen yang akan dicari lebih kecil atau lebih besar dari akarnya.

di bawah ini adalah langkah-langkah yang harus kita ikuti.
  1. Bandingkan elemen yang akan dicari dengan node root.
  2. If key (elemen yang akan dicari) = root, kembalikan node root.
  3. Else If key < root, telusuri subtree kiri.
  4. Else melintasi subtree kanan.
  5. Bandingkan elemen subtree secara berulang sampai key ditemukan atau akhir tree tercapai.

Remove Elemen Dalam BST

Ketika kita menghapus sebuah node dari BST, maka ada tiga kemungkinan seperti yang dibahas di bawah ini:

Node Adalah Leaf Node
Jika node yang akan dihapus adalah leaf node, maka kita dapat langsung menghapus node ini karena tidak memiliki child node.
Node Hanya Memiliki Satu Child
Ketika kita perlu menghapus node yang memiliki satu child, maka kita salin value child di dalam simpul dan kemudian hapus child itu.
Node Memiliki Dua Child
Ketika sebuah node yang akan dihapus memiliki dua child, maka node tersebut kita ganti dengan inorder (left-root-right) penerus dari node tersebut atau cukup dikatakan node minimum pada subtree kanan jika subtree kanan dari node tersebut tidak kosong. Saya mengganti node dengan node minimum ini dan menghapus node.

Implementasi Binary Search Tree (BST) Dalam Java

Program berikut di Java memberikan demonstrasi dari semua operasi BST di atas.

Output













Traversal Binary Search Tree (BST) Dalam Java

Tree adalah struktur hierarki, sehingga kita tidak dapat traversal secara linier seperti struktur data lain seperti array. Setiap jenis tree perlu dilintasi dengan cara khusus sehingga semua subtree dan node-nya dikunjungi setidaknya sekali.

Bergantung pada urutan di mana root node, subtree kiri dan subtree kanan dilintasi dalam sebuah tree, ada beberapa lintasan seperti yang ditunjukkan di bawah ini:
  • Traversal Inorder
  • Traversal Preorder
  • Traversal PostOrder
Semua traversal di atas menggunakan teknik depth-first yaitu pohon traversal (dilintasi) secara depthwise.

Trees juga menggunakan teknik traversal breadth-first. Pendekatan yang menggunakan teknik ini disebut traversal “Level Order”.
Pada bagian ini, kami akan mendemonstrasikan setiap traversal menggunakan BST berikut sebagai contoh.


Dengan BST seperti terlihat pada diagram di atas, maka level order traversal untuk tree di atas adalah:

Level Order Traversal: 10 6 12 4 8

Traversal Inorder

Pendekatan traversal inorder melintasi BST dalam urutan, Subtree kiri=>RootNode=>Subtree kanan. Traversal inorder memberikan urutan menurun (decreasing) dari node dari BST.

Algoritma InOrder (bstTree) untuk InOrder Traversal diberikan di bawah ini.
  1. Traverse (lintasi) subtree kiri menggunakan InOrder (left_subtree)
  2. Kunjungi root node.
  3. Traverse (lintasi) subtree kanan menggunakan InOrder (right_subtree)
Traversal inorder dari tree di atas adalah:

4       6      8      10      12

Seperti yang terlihat, urutan node sebagai hasil dari inorder traversal dalam urutan menurun.

Traversal Preorder

Dalam traversal preorder, root dikunjungi terlebih dahulu diikuti oleh subtree kiri dan subtree kanan. Traversal preorder membuat copy (salinan) pohon. Ini juga dapat digunakan dalam expression trees untuk mendapatkan prefix expression.

Algoritma untuk traversal PreOrder (bst_tree) diberikan di bawah ini:
  • Kunjungi root node.
  • Traverse (lintasi) subtree kiri dengan PreOrder (left_subtree).
  • Traverse (lintasi) subtree kanan dengan PreOrder (right_subtree).
Traversal preorder untuk BST yang diberikan di atas adalah:

10      6      4       8       12

Traversal PostOrder

PostOrder melintasi BST dalam urutan: Subtree kiri->Subtree kanan->Root node. Traversal PostOrder digunakan untuk menghapus tree atau mendapatkan postfix expression dalam kasus expression trees.

Algoritma untuk traversal postOrder (bst_tree) adalah sebagai berikut:
  • Traverse (lintasi) subtree kiri dengan postOrder (left_subtree).
  • Traverse (lintasi) subtree kanan dengan postOrder (right_subtree).
  • Kunjungi Root node
Traversal postOrder untuk contoh BST di atas adalah:

4       8       6       12      10

Selanjutnya, kita akan mengimplementasikan traversal ini menggunakan teknik depth-first dalam implementasi Java.

Output

Yak itu dia untuk hari ini Arek Blodhil! semoga materi yang dipelajari hari ini dapat bermanfaat untuk Arek Blodhil!

Referensi

Comments

Post a Comment

Popular posts from this blog

Infix, Postfix, and Prefix Expressions in Java

Image
Halo Sobat Blodhil!  Notasi Infix, Postfix, dan Prefix adalah tiga cara yang berbeda tetapi setara dalam penulisan ekspresi. Cara termudah untuk mendemonstrasikan perbedaan dengan melihat contoh operator yang menggunakan dua operan. Notasi infiks: X + Y Operator ditulis di antara operan mereka. Ini adalah cara biasa kami menulis ekspresi. Ekspresi seperti A * (B + C) / D biasanya diartikan seperti: "Pertama tambahkan B dan C bersama-sama, kemudian kalikan hasilnya dengan A, kemudian bagi dengan D untuk memberikan jawaban akhirnya." Notasi infix membutuhkan informasi tambahan untuk memperjelas urutan evaluasi operator: aturan yang dibangun ke dalam bahasa tentang prioritas dan asosiatif operator, dan tanda kurung ( ) untuk memungkinkan pengguna mengganti aturan ini. Sebagai contoh, aturan umum untuk asosiatif mengatakan bahwa kita melakukan operasi dari kiri ke kanan, sehingga perkalian dengan A diasumsikan terjadi sebelum pembagian dengan D. Demikian pula, aturan umum untuk p...
Read more

Sorting Algorithms in Java

Image
Halo Arek Blodhil! hari ini kita akan belajar... yap you guessed it. SORTING!!!  Sorting (Menyortir) data berarti mengaturnya dalam urutan tertentu, seringkali dalam struktur data seperti larik (array). Anda dapat menggunakan berbagai kriteria pengurutan, yang umum adalah pengurutan nomor dari paling kecil ke paling besar (ascending) atau sebaliknya (descending), atau mengurutkan string secara leksikografis. Ada berbagai algoritme pengurutan, dan tidak semuanya sama efisiennya. Aku akan menganalisis kerumitan waktu mereka untuk membandingkannya dan melihat mana yang berkinerja terbaik ya Arek Blodhil! Jadi tiga algoritme sorting yang akan aku bahas di sini adalah pertama Bubble Sort, kedua Insertion Sort, lalu yang terakhir adalah Selection Sort. Bear with me rek! BUBBLE SORT Bubble Sort bekerja dengan menukar elemen yang berdekatan jika tidak dalam urutan yang diinginkan. Proses ini berulang dari awal array hingga semua elemen tersusun rapi. Perhatikan ya Arek Blodhil! Kita tahu ...
Read more