Binary Search Tree

Nama : Dikky Larson
NIM : 2301853930

Pengertian

Binary Search Tree (BST) adalah jenis tree yang dapat mempercepat proses pencarian (searching), pengurutan (sorting), dan penginputan/penghapusan data (insertion/deletion).

Dapat disebut sebagai Sorted Binary Tree.

Konsep

Jika data yang akan masuk bernilai lebih kecil dari suatu node X, maka data akan masuk ke subtree bagian kiri dari X.

Sebaliknya, jika data yang akan masuk bernilai lebih kecil dari suatu node X, maka data akan masuk ke subtree bagian kiri dari X.

Untuk konsep dasar dari tree, dapat dilihat di link berikut: 

https://linked-list-dikky.blogspot.com/2020/03/hashmap-and-binary-tree.html

Metode / Operations 

1. find(value)
   
2. insert(value)
   
3. remove(value)
   ada beberapa cara dalam menghapus / remove suatu node di dalam BST, yaitu:

• Jika node berada di leaf, maka tinggal remove saja.
• Jika node memiliki 1 child node, maka hapus node dan sambung child-nya dengan parent dari node yang dihapus sebelumnya.
• Jika node memiliki 2 child node, maka ganti node yang akan dihapus dengan child paling kanan di subtree kiri (bisa juga menggunakan child paling kiri di subtree kanan).