Binary Search Tree

Hari ini saya akan membagikan tentang Binary Search Tree, apa bedanya dengan Binary Tree biasa?? Nah pada pemrograman Binary Tree biasa, kita hanya perlu menginput value dari node tersebut dimanapun. Pada Binary Search Tree (BST) value yang kita input kan akan dilihat dari lebih kecil atau lebih besar dari node utamanya dan posisinya pun bergantung dari lebih kecil lebih besar tersebut. Nah kita mulai saja contoh code nya ya

Seperti biasa kita membuat struct nya terlebih dahulu,

struct Tree {

char name[21];

int age;

Tree *left, *right;

} *root;

Setelah itu kita membuat fungsi untuk mengalokasikan memori baru,

Tree *createTree(char *name, int age) {

Tree *temp = (Tree*) malloc (sizeof(Tree));

strcpy(temp -> name, name);

temp -> age = age;

temp -> left = temp -> right = NULL;

return temp;

} 

nah setelah kita memiliki objek nya dan fungsi untuk mengalokasikan memorinya, kita harus membuat fungsi dimana dia melihat value dari node baru tersebut lebih kecil atau lebih besar, serta kosong atau tidak node yang akan ditempati,

Tree *insertRoot(Tree *root, Tree *newTree) {

if(!root) return newTree;

else if(newTree -> age < root -> age) root -> left = insertRoot(root -> left, newTree);

else root -> right = insertRoot(root -> right, newTree);

}

lalu kita coba sekarang memasukan nama dan umur pada main kita,

int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

return 0;

}

nah setelah dimasukkan seperti itu kita belum bisa melihat hasil nya betul atau salah, kita harus membuat fungsi untuk mencetak hasilnya tersebut, 

void printInOrder(Tree *root) {

if(root) {

printInOrder(root -> left);

puts("+-------------------+");

printf("| Name : %-10s |\n", root -> name);

printf("| Age  : %-10d |\n", root -> age);

puts("+-------------------+");

printInOrder(root -> right);

}

}

nah kita modif sedikit pada main tadi,

int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

printInOrder(root);

return 0;

}

nah sudah selesai untuk Insert, dan Print kita. Sekarang gimana jika kita ingin delete node tersebut?? Kita harus buat membuat fungsi untuk meng-delete, fungsi dibawah ini saya delete dengan mencari umur yaa,

Tree *removeRoot(Tree *root, int age) {

if(!root) return root;

else if(age < root -> age) root -> left = removeRoot(root -> left, age);

else if(age > root -> age) root -> right = removeRoot(root -> right, age);

else {

//Kalo dia punya 1 anak atau ga punya anak

if(root -> left == NULL || root -> right == NULL) {

Tree *temp = root -> left != NULL ? root -> left : root -> right;

//Kalo punya 1 anak

if(temp) {

*root = *temp;

} 

//Kalo tak punya anak

else {

temp = root;

root = NULL;

}

free(temp);

}

//Kalo dia punya 2 anak

else {

Tree *temp = root -> left;

while(temp -> right)

temp = temp -> right;

root -> age = temp -> age;

strcpy(root -> name, temp -> name);

root -> left = removeRoot(root -> left, temp -> age);

}

return root;

}

}

Nah cukup panjang untuk delete kita yak, sekarang tinggal kita modif lagi main kita,

 int main() {

root = insertRoot(root, createTree("Budi", 18));

root = insertRoot(root, createTree("Setiawan", 21));

printInOrder(root);

root = removeRoot(root, 18);

printInOrder(root);

return 0;

}

nah sudah selesai semua Insert, Delete, dan Print. Sampai sini saja materi yang saya bawakan mengenai Binary Search Tree, selamat mencoba.