Binary Search Tree

Binary Search Tree
adalah sebuah data structure binary tree yang memiliki ciri-ciri, yaitu: subtree sebelah kiri nilainya lebih kecil dari parent nodenya dan subtree sebelah kanan nilainya lebih besar dari parent nodenya.



Terdapat 3 cara dalam traverse binary tree (dilakukan secara rekursi):

  • In-order
Yaitu subtree kiri dilalui terlebih dahulu lalu ke root dan ke subtree kanan.
  • Pre-order
Yaitu root yang dilalui terlebih dahulu lalu subtree kiri dan kanan.
  • Post-order
Yaitu subtree kiri dan kanan dilalui terlebih dahulu lalu root.

https://www.tutorialspoint.com/data_structures_algorithms/tree_traversal.htm

Berikut adalah contoh Binary Search Tree :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

struct Node{
int id;
char name[100];
struct Node *left, *right;
};

struct Node *createNode(int id, char name[]){
struct Node *newNode = (Node*)malloc(sizeof(Node));
newNode->id = id;
strcpy(newNode->name, name);
newNode->left = newNode->right = NULL;
return newNode;
}

struct Node *insertNode(struct Node *currNode, int id, char name[]){
if(currNode == NULL){
return createNode(id, name);
}
if(currNode->id > id){
currNode->left = insertNode(currNode->left, id, name);
}
else if(currNode->id < id){
currNode->right = insertNode(currNode->right, id, name);
}
return currNode;
}

void printInfix(struct Node *currNode){
if(currNode == NULL){
return;
}
printInfix(currNode->left);   
printf("%-5d - %-20s\n",currNode->id, currNode->name);    
printInfix(currNode->right);
}

void printPrefix(struct Node *currNode){
if(currNode == NULL){
return;
}
printf("%-5d - %-20s\n",currNode->id, currNode->name);
printPrefix(currNode->left);
printPrefix(currNode->right);
}

void printPostfix(struct Node *currNode){
if(currNode == NULL){
return;
}
printPostfix(currNode->left);
printPostfix(currNode->right);
printf("%-5d - %-20s\n",currNode->id, currNode->name);
}

struct Node *predecessor(struct Node *currNode){
currNode = currNode->left;
while(currNode->right){
currNode = currNode->right;
}
return currNode;
}

struct Node *deleteNode(struct Node *currNode, int id){
if(currNode == NULL){
return NULL;
}
if(currNode->id > id){
currNode->left = deleteNode(currNode->left, id);
}
else if(currNode->id < id){
currNode->right = deleteNode(currNode->right, id);
}
else{
if(currNode->left == NULL || currNode->right == NULL){
struct Node *tempNode = NULL;
if(currNode->left != NULL){
tempNode = currNode->left;
}
else{
tempNode = currNode->right;
}
if(tempNode == NULL){ // kalau tidak ada anak.
tempNode = currNode;
currNode = NULL;
free(tempNode);
}
else{ // kalau anaknya 1.
*currNode = *tempNode;
free(tempNode);
}  
}
else{
struct Node *tempNode = predecessor(currNode);
currNode->id = tempNode->id;  // copy data dari temp ke curr.
strcpy(currNode->name, tempNode->name);
currNode->left = deleteNode(currNode->left, tempNode->id);
}
}
return currNode;
}

int search(struct Node *currNode, int id)
{
if(currNode == NULL)
return 0;
printInfix(currNode->left);
if(currNode->id == id)
return 1;
printInfix(currNode->right);
}

int main(){
struct Node *root = NULL;
root = insertNode(root, 20, "Bambang");
root = insertNode(root, 24, "Michelle");
root = insertNode(root, 22, "Budi");
root = insertNode(root, 18, "Jose");
root = insertNode(root, 18, "Yani"); // kalau sama tidak di print.
printf("Infix :\n");
printInfix(root);printf("\n");
printf("Postfix :\n");
printPostfix(root);printf("\n");
printf("Prefix :\n");
printPrefix(root);printf("\n");
printf("Delete(Pop) :\n");
root = deleteNode(root, 22);
printInfix(root);printf("\n");
printf("Search() :\n");
if(search(root, 18) == 0)
{
printf("Not Found");
}
else 
{
printf("Found");
}

}

Comments

Post a Comment

Popular posts from this blog

Heap & Tries

Image
Heap Heap adalah data structure tree yang terdiri dari 3 properti heap, yaitu: 1. Min Heap: setiap node memiliki value yang lebih kecil dari childnya (value terkecil di root). 2. Max Heap: setiap node memiliki value yang lebih besar dari childnya (value terbesar di root). 3. Min-Max Heap: terdiri dari level dan setiap level memiliki heap yang berbeda. Heap biasa direpresentasikan dalam bentuk array sehingga lebih mudah di digunakan. Index array pada heap dimulai dari 1, dan setiap melakukan insert akan dimasukkan ke index paling akhir. Untuk mengetahui index dari parent, left child, dan right child digunakan: Parent(x) = x/ 2 left-child(x) = 2 * x right-child(x) = 2 * x + 1 Min Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Max Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Min-Max Heap https://www.google.com/url?sa=i&url=https%3A%2F%2Fstackoverflow.com%2Fques
Read more

Linked List II

Image
 Linked List II Circular Singly Linked List Adalah linked list dimana semua node terhubung oleh satu pointer next saja dan membentuk sebuah loop satu arah dan tidak memiliki NULL pada akhir dari node. Node mana saja bisa menjadi starting point karena dia hanya berhenti ketika node yang sama terulang.  https://static.javatpoint.com/ds/images/circular-singly-linked-list.png Doubly Linked List Adalah linked list yang terdiri dari sekumpulan data yang memiliki dua tangan penghubung ke data sebelumnya dan ke data selanjutnya. Setiap ujung atau tail dari data adalah NULL dan dapat dijalankan dua arah karena memiliki dua penunjuk yaitu previous dan next. Jika kita ingin insert data atau delete data kita harus mengubah kedua pointer yang menunjuk ke data sebelum dan selanjutnya. https://www.studytonight.com/data-structures/images/doubly-linked-list-1.png Circular Doubly Linked List Adalah linked list yang mirip dengan Circular Singly Linked L
Read more

AVL Tree

Image
AVL Tree AVL Tree adalah singkatan untuk Adelson-Velskii and Landis, AVL adalah bagian atau subtype dari Binary Search Tree (BST). Konsep AVL Tree adalah selisih dari height kiri dan kanan subtree tidak boleh lebih dari 1. AVL tree harus selalu balance, sehingga setiap melakukan operasi akan di cek selisih height kiri dan kanan subtree jika lebih dari 1 maka disebut violation. Berikut adalah contoh dari violation, jika dilihat height dari subtree kiri 17 adalah 2 dan subtree kananya 0 maka selisihnya 2 ( violation ). https://www.google.com/url?sa=i&url=http%3A%2F%2Fivansrarudiandi.blogspot.com%2F2016%2F05%2Favl-tree.html&psig=AOvVaw0u6xLhAVqqwO6eNKpO-PM4&ust=1588413552562000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMih2u6zkukCFQAAAAAdAAAAABAE AVL Tree Rotation Seperti yang telah saya katakan bahwa setiap operasi kita perlu mengecek balance nya, jika tidak balance maka kita harus membuatnya balance dengan operasi rotation. Terdapat 2 jenis rot
Read more