Hal yang akan dibahas pada pertemuan kali ini yaitu :
1. Binary Search Tree
2. Binary Search Tree Operations
1. Binary Search Tree
Binary Search Tree adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah.
Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.
Aturan main Binary Search Tree adalah :
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
berikut gambaran contoh dari Binary Search Tree
Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.
2. Binary Search Tree Operations
Terdapat 3 operasi dalam Binary Search Tree yaitu :
1. Search
Dengan properti bahwa semua nilai lebih kecil dari root node terletak disebelah kiri dan semua nilai yang lebih besar dari root node terletak disebelah kanan membantu untuk pencarian dalam waktu yang cepat (dengan anggapan h adalah ketinggian tree)
Misalkan kita berada pada satu simpul dan nilai yang ingin dicari lebih kecil dari nilai simpul itu. Dalam hal ini, kita akan mencari di subtree kiri.
contoh:
Jadi fungsi kita akan mengambil elemen yang akan dicari (x) dan pohon (T)yaitu : SEARCH(x,T)
dan kita akan melakukan pencarian jika root of the tree tidak NULL, if (T.root!=NULL)
langkah-langkahnya yaitu :
1. pertama kita cek terlebih dahulu apakah data yang akan dicari berada di root atau tidak. jika sudah di root, maka kita akan mengembalikannya
2. jika bukan, maka kita akan mencari di subtree kiri jika nilai yang akan dicari lebih kecil dari pada root. atau kita akan mecrai di subtree sebelah kanan jika nilai yang akan dicari lebih besar dari pada root.
gambaran codingannya :
SEARCH(x, T)
if(T.root != null)
if(T.root.data == x)
return r
else if(T.root.data > x)
return SEARCH(x, T.root.left)
else
return SEARCH(x, T.root.right)
2. Insertion
contoh insertion
Langkah-langkah untuk insertion sbb :
Pertama-tama kita akan mencari elemen itu dan jika elemen itu tidak ditemukan, maka kita akan memasukkannya.
Lalu kita akan menggunakan pointer sementara dan pergi ke tempat node akan dimasukkan.
Kita perlu membuat simpul terakhir dalam iterasi diatas sebagai induk dari simpul baru. jadi kita perlu menggunakan variabel baru
kita telah menggunakan variabel y. ketika tree tidak memiliki simpul, simpul baru akan manjadi root dari tree dan parentnya akan NULL. jadi awalnya nilai y adalah NULL. Jika tidak y akan menunjuk pada simpul terakhir.
setelah ini kita akan menjadikan y sebagai induk dari simpul baru
Terakhir, kita perlu membuat simpul baru anak y. jika y adalah NULL, simpul baru akan menjadi akar dari pohon, jika tidak kita akan memeriksa apakah lebih besar atau lebih kecil dari data y, dan karenanya kita akan membuatnya menjadi kiri atau the right child
gambaran codingannya :
INSERT(T, n)
temp = T.root
y = NULL
while temp != NULL
y = temp
if n.data < temp.data
temp = temp.left
else
temp = temp.right
n.parent = y
if y==NULL
T.root = n
else if n.data < y.data
y.left = n
else
y.right = n
3. Deletion
dalam tahap deletion kita perlu memerhatikan 3 hal yaitu :
1. jika key berada di leaf, maka kita hanya perlu menghapus node tersebut
2. jika key ada di simpul yang memiliki 1 child, hapus simpul tersebut dan sambungkan childnya ke parentnya.
3. jika key ada di simpul yang memiliki 2 child, mkaa temukan child paling kanan dari sub tree kirinya(simpul P), ganti keynya dengan key p dan hapus p secara rekursif
NAMA : Timothy Gilbert
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01
sumber :
