Struktur Data - Pohon Pencarian Biner

A Binary Search Tree (BST) adalah pohon di mana semua node mengikuti properti yang disebutkan di bawah ini -

  • Nilai kunci sub-pohon kiri kurang dari nilai kunci simpul induknya (root).

  • Nilai kunci sub-pohon kanan lebih besar dari atau sama dengan nilai kunci simpul induknya (root).

Jadi, BST membagi semua sub-pohonnya menjadi dua segmen; sub-pohon kiri dan sub-pohon kanan dan dapat didefinisikan sebagai -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Perwakilan

BST adalah kumpulan node yang diatur sedemikian rupa sehingga mereka mempertahankan properti BST. Setiap node memiliki kunci dan nilai terkait. Saat mencari, kunci yang diinginkan dibandingkan dengan kunci di BST dan jika ditemukan, nilai terkait diambil.

Berikut adalah representasi bergambar BST -

Kami mengamati bahwa kunci simpul akar (27) memiliki semua kunci yang nilainya lebih rendah di sub-pohon kiri dan kunci bernilai lebih tinggi di sub-pohon kanan.

Operasi Dasar

Berikut adalah operasi dasar dari sebuah pohon -

  • Search - Mencari elemen di pohon.

  • Insert - Menyisipkan elemen di pohon.

  • Pre-order Traversal - Melintasi pohon dengan cara pre-order.

  • In-order Traversal - Melintasi pohon secara berurutan.

  • Post-order Traversal - Melintasi pohon dengan cara pasca-order.

Node

Tentukan node yang memiliki beberapa data, referensi ke node anak kiri dan kanannya.

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

Operasi Pencarian

Kapanpun sebuah elemen akan dicari, mulailah mencari dari root node. Kemudian jika datanya kurang dari nilai kunci, cari elemen di subtree kiri. Jika tidak, cari elemen di subtree kanan. Ikuti algoritma yang sama untuk setiap node.

Algoritma

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;
}

Sisipkan Operasi

Kapanpun sebuah elemen akan dimasukkan, pertama cari lokasi yang tepat. Mulailah mencari dari root node, kemudian jika datanya kurang dari nilai kunci, cari lokasi kosong di subtree kiri dan masukkan datanya. Jika tidak, cari lokasi kosong di subtree kanan dan masukkan datanya.

Algoritma

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;
            }
         }
      }            
   }
}