Struktur Data dan Algoritma - Pohon

Pohon mewakili simpul yang dihubungkan oleh tepi. Kami akan membahas pohon biner atau pohon pencarian biner secara khusus.

Binary Tree adalah struktur data khusus yang digunakan untuk tujuan penyimpanan data. Pohon biner memiliki syarat khusus dimana setiap node dapat memiliki maksimal dua anak. Pohon biner memiliki manfaat dari array terurut dan daftar tertaut karena pencarian secepat dalam array yang diurutkan dan operasi penyisipan atau penghapusan secepat dalam daftar tertaut.

Istilah Penting

Berikut adalah istilah-istilah penting yang berkaitan dengan pohon.

Path - Path mengacu pada urutan node di sepanjang tepi pohon.
Root- Node di puncak pohon disebut root. Hanya ada satu akar per pohon dan satu jalur dari simpul akar ke simpul manapun.
Parent - Setiap simpul kecuali simpul akar memiliki satu sisi ke atas ke simpul yang disebut induk.
Child - Simpul di bawah simpul tertentu yang dihubungkan dengan ujungnya ke bawah disebut simpul anak.
Leaf - Simpul yang tidak memiliki simpul anak disebut simpul daun.
Subtree - Subpohon mewakili keturunan dari sebuah node.
Visiting - Visiting mengacu pada pengecekan nilai sebuah node saat kontrol berada di node.
Traversing - Melintasi berarti melewati node dalam urutan tertentu.
Levels- Level dari sebuah node merupakan generasi dari sebuah node. Jika node root berada di level 0, maka node turunan berikutnya ada di level 1, cucunya di level 2, dan seterusnya.
keys - Key merepresentasikan nilai dari sebuah node yang menjadi dasar operasi pencarian yang akan dilakukan untuk sebuah node.

Representasi Pohon Pencarian Biner

Pohon Pencarian Biner menunjukkan perilaku khusus. Anak kiri node harus memiliki nilai yang kurang dari nilai induknya dan anak kanan node harus memiliki nilai yang lebih besar dari nilai induknya.

Kami akan mengimplementasikan pohon menggunakan objek node dan menghubungkannya melalui referensi.

Node Pohon

Kode untuk menulis simpul pohon akan serupa dengan yang diberikan di bawah ini. Ini memiliki bagian data dan referensi ke node anak kiri dan kanannya.

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

Di pohon, semua node berbagi konstruksi yang sama.

Operasi Dasar BST

Operasi dasar yang dapat dilakukan pada struktur data pohon pencarian biner, adalah sebagai berikut -

Insert - Menyisipkan elemen di pohon / membuat pohon.
Search - Mencari elemen di pohon.
Preorder Traversal - Melintasi pohon dengan cara pre-order.
Inorder Traversal - Melintasi pohon secara berurutan.
Postorder Traversal - Melintasi pohon dengan cara pasca-order.

Kita akan belajar membuat (menyisipkan ke) struktur pohon dan mencari item data di pohon dalam bab ini. Kita akan belajar tentang metode melintasi pohon di bab selanjutnya.

Sisipkan Operasi

Penyisipan pertama membuat pohon. Setelah itu, setiap kali elemen akan dimasukkan, pertama-tama 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

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Penerapan

Implementasi fungsi insert akan terlihat seperti ini -

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, create root node
   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;
            }
         }
      }            
   }
}

Operasi Pencarian

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

Algoritma

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

Penerapan algoritma ini akan terlihat seperti ini.

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

Untuk mengetahui tentang implementasi struktur data pohon pencarian biner, silakan klik di sini .