Binary Search Tree

Binary Search Tree

BST adalah binary tree dimana node kirinya selalu lebih kecil dari node kanannya. Operasi-operasi dalam BST, yaitu search, insert, delete, pre-order traversal, post-order traversal, in-order traversal.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

1. Search, search dimulai dari root, jika key yang dicari lebih kecil dari data, maka akan turun ke subtree kiri, jika key yang dicari lebih besar dari tada, maka akan turun ke subtree kanan.

2. Insert, untuk menginsert data, maka harus dimulai dari root, jika key yang akan diinsert lebih kecil dari data, maka akan dicari tempat kosong di subtree kiri, sedangkan jika key yang akan diinsert lebih besar dari data, maka akan dicari tempat kosong di subtree kanan.

3. Delete, node pada bst saling berhubungan, sehingga ada beberapa kondisi yang perlu diperhatikan ketika akan mendelete node, yaitu:

-Jika yang didelete adalah leaf node, maka hanya perlu delete leaf node tersebut.
-Jika yang didelete memiliki 1 child, jika simpul yang akan dihapus adalah anak kiri dari induk, maka dihubungkan pointer kiri induk (dari simpul yang dihapus) ke satu anak. Jika simpul yang akan dihapus adalah anak kanan dari induk, maka dihubungkan pointer kanan induk (dari simpul yang dihapus) ke satu anak.
-Jika yang didelete memiliki 2 child, maka data yang akan diinsert harus dibandingkan dengan data-data pada BST dan mencari pengganti untuk node yang dihapus dari node lain.

Kompleksitas Waktu: Kompleksitas waktu kasus terburuk dari operasi pencarian dan penyisipan adalah O (h) di mana h adalah ketinggian Pohon Pencarian Biner. Dalam kasus terburuk, kita mungkin harus melakukan perjalanan dari root ke simpul daun terdalam.