Rangkuman dari pertemuan pertama Data Structure pada tanggal 30 Maret 2016
Binary Search Tree
Binary Search Tree adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.
Contoh Binary Tree(angka lebih kecil selalu panah bawah kekiri)
Binary Search Tree memiliki 3 operasi :
Search,Insertion dan Deletion
Search
Pencarian (Searching) dimulai dari rootnya (di gambar adalah angka 50).
Jika angka yang dicari belum ditemukan, maka pencarian akan dilanjutkan, jika angka yang dicari lebih kecil dari root, maka pencarian akan ke sebelah kiri root, jika sebaliknya maka akan dicari ke sebelah kanan root. Begitu seterusnya sampai ditemukan angka yang dicari.
Search 23
- 23 != root, maka 23 dibandingkan dengan root
- 23 < 50, maka pencarian dilanjutkan ke sebelah kiri
- 23 != 17, maka 23 dibandingkan dengan 17
- 23 > 17, maka pencarian dilanjutkan ke sebelah kanan
- 23 == 23, maka pencarian telah berhasil dan selesai
Insertion
Misal angka yang ingin kita insert adalah 35, maka:
- Insertion dimulai dari root, 35 > 50 maka akan dilanjutkan ke sebelah kiri
- Setelah itu, 35 dibandingkan dengan 17 (35 >17)
- Lalu karena lebih besar maka ke kanan ke 23, karena lebih besar (35>23) maka ke kanan membentuk node baru
Deletion
Misal akan mendelete akan 76
- Root =50 , dibandingkan dengan 76
- Karena lebih besar 76 maka ke kanan, lalu 76=76
- Lalu cari dari turunan 76 ,cari angka yang paling besar dan terbawah(tidak memiliki turunan lagi), disini angka merupakan 67
- tukar 67 ke tempat angka 76
- free 76