Binary Search Tree

Binary Search Tree

Kemarin kita sudah membahas mengenai Hash Table, Hashing dan Binary Tree. Pada hari ini, saya akan menjelaskan tentang Binary Search Tree.

Binary Search Tree adalahadalah Binary Tree dengan :

1. Subtree kiri dari sebuah node hanya berisi node dengan kunci kurang dari kunci node.
2. Subtree kanan dari sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
3. Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner.

Properti di atas dariBST menyediakan pemesanan antar tombol sehingga operasi seperti pencarian, minimum dan maksimum dapat dilakukan dengan cepat. Jika tidak ada pemesanan, maka BST mungkin harus membandingkan setiap kunci untuk mencari kunci yang diberikan.

BST mempunya Basic Operations yang terdiri dari :

1. Search - untuk mencari elemen dalam tree
2. Insert - untuk memasukkan data ke dalam tree
3. Pre-order Traversal - melintasi tree dengan cara pre-order
4. In-order Traversal - melintasi tree dengan cara in-order
5. Post-order Traversal - melintasi tree dengan cara post-order

Search Algorithm : 

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
 
   while(current->data != data){
 
      if(current != NULL) {
         printf("%d ",current->data);
   
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
   
         //not found
         if(current == NULL){
            return NULL;
         }
      }   
   }
   
   return current;
}

Insert Algorithm : 

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
   
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
    
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
} 

Kasus terburuk BST yang dapat terjadi adalah Kompleksitas Waktu. Kompleksitas waktu kasus terburuk dari operasi pencarian dan penyisipan adalah 0 (h) di mana h adalah ketinggian BST. Dalam kasus terburuk, kita mungkin harus melakukan perjalanan dari root ke simpul daun terdalam. Ketinggian pohon miring dapat menjadi n dan kompleksitas waktu pencarian dan operasi memasukkan bisa menjadi 0 (n).

Beberapa fakta mengenai BST :

1. In-order traversal dalam BST selalu menghasilkan output yang berurutan.
2. Kita dapat membuat BST dengan hanya Preorder atau Postorder atau traversal Level Order. Tetapi harus diingat bahwa kita selalu bisa mendapatkan inorder traversal dengan mengurutkan satu-satunya traversal yang diberikan.
3. Jumlah BST unik dengan n kunci yang berbeda adalah nomor Catalan.

Sumber : 

1. https://www.geeksforgeeks.org/binary-search-tree-data-structure/
2. https://en.wikipedia.org/wiki/Binary_search_tree