BINARY SEARCH TREE

Emilio Joshua Adiputra
1901460171

Binary Search Tree adalah Tree yang memiliki urutan dan semua node harus memiliki Value
subtree bagian kiri dari Root itu value lebih kecil dari value Root sedangkan subtree bagian kanan dari Root value lebih besar dari value Root

Dalam BST value setiap node tidak boleh sama
sehingga data dengan nilai yang sama tidak boleh

Operasi

Find (x) : Fungsi untuk mencari nilai x

Insert(x) : Fungsi untuk memasukkan nilai x ke dalam binary tree

Delete(x) : Fungsi untuk membuang atau menghilangkan nilai x dari dalam tree





Find (5)


1.Root value adalah 9
2.jika 5 lebih besar dari 9 maka kita ke node kanan Root
   jika 5 lebih kecil dari 9 maka kita ke node kiri dari Root
3.maka kita menemukan 5 < 9 kita pindah ke kiri dimana value nya adalah 4
4.check nomor 2 berdasarkan subnode yg sedang kita cek yaitu 4
5. 5> 4 jika lebih besar pindah ke kanan dan node berikut nya adalah 6
6.ulangi nomor 2 dengan node 6
7. 5 < 6 maka kita berpindah ke kiri dari value 6
8. sesudah itu lokasi 5 di temukan

Insert (8)

1.jika Root kosong maka root sama dengan value yang dicari
2. root adalah 9 dan yg ingin di masukan 8 sehingga 8 < 9 maka ke kiri dari Root
3.8 > 4 maka kita ke kanan dari value 4
4.8 > 6 maka kita ke kanan dari value 6
5.setelah 6 ada value 7 maka kita perlu check 8>7 sehingga
6.  8 lebih besar dari 7 maka kita ke kanan dari value 7
7. setelah 7 tidak ada child lagi maka kita bisa masukan angka 8 di kanan bawah nya

Delete(6)

pertama kita perlu memakai fungsi yang sama seperti Find(x)

dengan tambahan syarat
jika yang di delete adalah Leaf (Tidak punya child)
maka kita dapat mendelete secara langsung

jika yang di delete punya 1 child maka child ini kita hubungkan langsung dengan parent dari data yang mau kita delete lalu delete

jika yang di delete punya 2 child maka node child paling kanan dari kiri subnode atau kiri dari kanan subnode sebagai pengganti posisi data yang ingin di delete lalu hubungkan secara langsung child tersebut dengan parent yang ingin di delete lalu kita delete yang kita ingin hapus

di dalam Delete (6) kita dapat melihat jika kita mendelete value 6 maka kita perlu pindahkan 5 dan 7

dalam skenario ini kita perlu menghubungkan langsung  5 ke parent dari 6 yaitu 4 lalu 6 dapat kita delete sehingga 5 menjadi parent dari 7