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/operasi | Deskripsi |
|---|---|
| Insert | Tambahkan elemen ke BST dengan tidak melanggar properti BST. |
| Delete | Hapus node tertentu dari BST. Node dapat berupa root node, non-leaf, atau leaf node. |
| Search | Cari 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.
- Mulai dari root.
- Bandingkan elemen yang akan ingin di-insert dengan root node. Jika lebih kecil dari root, maka telusuri subtree kiri atau telusuri subtree kanan.
- 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.
- Bandingkan elemen yang akan dicari dengan node root.
- If key (elemen yang akan dicari) = root, kembalikan node root.
- Else If key < root, telusuri subtree kiri.
- Else melintasi subtree kanan.
- 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.
- Traverse (lintasi) subtree kiri menggunakan InOrder (left_subtree)
- Kunjungi root node.
- 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