5-Binary Search Tree
1. Binary Tree dan Binary Search Tree
Binary tree adalah tree yang memiliki maksimal child, sebanyak dua untuk setiap nodenya, sedangkan binary search tree adalah binary tree yang child kirinya selalu lebih kecil daripada node tersebut, dan child kanan selalu lebih besar daripada node tersebut.
Note: Binary search tree memiliki bentuk yang sama seperti binary tree biasa
2. Kegunaan Binary Search Tree
Kegunaan binary search tree adalah untuk mempermudah proses pencarian data
3. Operasi dalam Binary Search Tree
Proses pencarian data dalam binary search tree adalah sebagai berikut:
misalnya kita ingin mencari nilai X,
1. pencarian dimulai dari root
2. jika root berisi X, berarti pencarian selesai
3. jika X lebih kecil dari pada nilai root, cari ke subtree kiri secara rekursif, sebaliknya jika X lebih besar dari pada nilai root, cari ke subtree kanan secara rekursif
4. Code Pencarian pada Binary Search Tree
5. Penambahan Data Pada Binary Search Tree
Penambahan data pada binary search tree dilakukan secara rekursif, misalnya node yang akan ditambah adalah X, maka:
1. mulai pada root
2. jika X lebih kecil dari pada node root, maka masukkan X ke subtree kiri, sebaliknya masukkan X ke subtree kanan.
3. lakukan hingga menemukan node kosong untuk meletakkan X ( X akan selalu menjadi leaf baru).
6. Code Penambahan Data pada Binary Search Tree
7. Penghapusan Data pada Binary Search Tree
Ada 3 kasus yang harus dipertimbangkan dalam penghapusan data di binary search tree, yaitu:
1. jika data ada pada leaf, maka hanya perlu menghapus node tersebut
2. jika data ada pada node yang memiliki 1 child, hapus node tersebut dan hubungkan child nya kepada parentnya
3. jika data ada pada node yang memiliki 2 child, temukan data paling kanan dari child kirinya (node P), timpa data tersebut dengan data P, dan hapus node P secara rekursif (atau bisa juga pilih node paling kiri dari child kanannya).
8. Code Penghapusan Data pada Binary Search Tree
Binary tree adalah tree yang memiliki maksimal child, sebanyak dua untuk setiap nodenya, sedangkan binary search tree adalah binary tree yang child kirinya selalu lebih kecil daripada node tersebut, dan child kanan selalu lebih besar daripada node tersebut.
Note: Binary search tree memiliki bentuk yang sama seperti binary tree biasa
2. Kegunaan Binary Search Tree
Kegunaan binary search tree adalah untuk mempermudah proses pencarian data
3. Operasi dalam Binary Search Tree
Proses pencarian data dalam binary search tree adalah sebagai berikut:
misalnya kita ingin mencari nilai X,
1. pencarian dimulai dari root
2. jika root berisi X, berarti pencarian selesai
3. jika X lebih kecil dari pada nilai root, cari ke subtree kiri secara rekursif, sebaliknya jika X lebih besar dari pada nilai root, cari ke subtree kanan secara rekursif
4. Code Pencarian pada Binary Search Tree
Penambahan data pada binary search tree dilakukan secara rekursif, misalnya node yang akan ditambah adalah X, maka:
1. mulai pada root
2. jika X lebih kecil dari pada node root, maka masukkan X ke subtree kiri, sebaliknya masukkan X ke subtree kanan.
3. lakukan hingga menemukan node kosong untuk meletakkan X ( X akan selalu menjadi leaf baru).
6. Code Penambahan Data pada Binary Search Tree
Ada 3 kasus yang harus dipertimbangkan dalam penghapusan data di binary search tree, yaitu:
1. jika data ada pada leaf, maka hanya perlu menghapus node tersebut
2. jika data ada pada node yang memiliki 1 child, hapus node tersebut dan hubungkan child nya kepada parentnya
3. jika data ada pada node yang memiliki 2 child, temukan data paling kanan dari child kirinya (node P), timpa data tersebut dengan data P, dan hapus node P secara rekursif (atau bisa juga pilih node paling kiri dari child kanannya).
8. Code Penghapusan Data pada Binary Search Tree
Comments
Post a Comment