Binary Search Tree
Binary Search tree adalah setiap node node memiliki 1 kunci unik sehingga tidak ada kunci yang sama di node yang lain.
kunci yang ada di kiri node lebih kecil dari pada akar node di atasnya, sedangkan yang dikanan lebih besar dari pada node akarnya. seterusnya node node tersebut akan membentuk BST yang lain.
BST : Searching
Konsep dari pencarian element (X) di BST adalah mencari dari akar node. jika element (X) lebih kecil dari node, maka akan otomatis menuju ke kiri, sedangkan jika lebih besar dari node akan terus menuju ke kekanan.
BST : Inserting
Penambahan node pada BST adalah element (X) di komparasi dengan node, jika lebih besar akan menuju ke kanan sedangkan jika lebih kecil akan menuju ke kiri. Hal ini akan dilakukan sampai mendapat node yang kosong.(akan selalu menjadi daun baru).
BST : Deleting
Penghapusan node memiliki beberapa sifat :
- Jika node yang akan dihapus itu daun(leaf) maka akan langsung dihilangkan.
- jika node yang akan dihapus itu memiliki 1 cabang(anak) maka leaf harus di sambugkan ke parent nodenya.
- Jika node yang di hapus memiliki 2 cabang(anak) maka node yang di kanan harus menggantikan node yang ada di atasnya sampai ke tempat dimana node itu dihapus.
Threaded Binary Tree Concept
Suatu Binary Tree yang punya perbedaan dalam menyimpan pointer NULL.
NULL pointer ini bisa di gunakan untuk menunjuk elemen lain, seperti keturunan dari node sebelumnya.