Binary Tree
Binary tree adalah pohon dalam suatu struktur data yang berbentuk seperti pohon. Binary tree biasanya terdiri dari 2 anak dan binary tree tidak memiliki anak lebih dari 3 level dari root.
Jika dilihat contoh diatas, angka 7 dan 5 berada pada level 1, angka 2,6, dan 9 berada pada level 2 dst.
Binary Search Tree
Binary Search Tree adalah tree yang terurut. Binary Search Tree sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Implemetasi binary search tree ini biasanya data akan dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari anak satu pertama yang disebut dengan istilah root. Root tersebut memiliki anak(rootbaru) kiri dan anak kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dengan metode in-order. Data yang telah tersusun dalam struktur data BST dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada worstcase dimana BST berbentuk seperti linked list.
Contoh implementasi code C insert,delete dalam bst.
/*
#include <stdio.h>
#include <stdlib.h>
struct Node{
int value;
Node *left,*right;
}*root,*curr;
Node *createNode(int val){
curr = (Node*) malloc(sizeof(Node));
curr->value = val;
curr->left = curr->right = NULL;
return curr;
}
Node *insertNode(Node *parent,int value){
if(!parent)
return createNode(value);
else if(parent->value == value)
return parent;
else if(parent->value > value)
parent->left = insertNode(parent->left,value);
else
parent->right = insertNode(parent->right,value);
}
Node *removeNode(Node *parent,int value){
if(!parent)
return parent;
else if(parent->value > value)
parent->left = removeNode(parent->left,value);
else if(root->value < value)
parent->left = removeNode(parent->left,value);
else if(parent->value == value){
if(parent->left == NULL || parent->right == NULL){
Node *temp = parent->left != NULL ? parent->left : parent->right;
if(temp)
*parent = *temp;
else{
temp = parent;
parent = NULL;
}
free(temp);
}
else{
Node *temp = parent->left;
while(temp->right)
temp = temp->right;
parent->left=removeNode(parent->left,temp->value);
}
return parent;
}
}
void print(Node *parent){
if(parent){
print(parent->left);
printf("%d ",parent->value);
print(parent->right);
}
}
int main(){
root = insertNode(root,20);
root = insertNode(root,5);
root = insertNode(root,14);
root = insertNode(root,3);
root = insertNode(root,16);
root = insertNode(root,22);
root = insertNode(root,19);
root = removeNode(root,3);
//print in order
print(root);
}
*/
Terima Kasih ^ ^
