Rangkuman Data structure

Hashing

Hashing adalah teeknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.

Hash Table

Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentyj array dengan tambahan algoritma untuk mempercepat pemrosesan data.

Hashing

Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

(1,20)
(2,70)
(42,80)
(4,25)
(12,44)
(14,32)
(17,11)
(13,78)
(37,98)

Sr.No.	Key	Hash	Array Index
1	1	1 % 20 = 1	1
2	2	2 % 20 = 2	2
3	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

Linear Probing

As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.

Sr.No.	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

Basic Operations

Following are the basic primary operations of a hash table.

Search − Searches an element in a hash table.
Insert − inserts an element in a hash table.
delete − Deletes an element from a hash table.

DataItem

Define a data item having some data and key, based on which the search is to be conducted in a hash table.

struct DataItem {
   int data;
   int key;
};

Hash Method

Define a hashing method to compute the hash code of the key of the data item.

int hashCode(int key){
   return key % SIZE;
}

Search Operation

Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.

Example

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
 
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
   
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

Insert Operation

Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

Example

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   hashArray[hashIndex] = item;        
}

Delete Operation

Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing to get the element ahead if an element is not found at the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact.

Example

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
 
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
   
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
  
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }  
 
   return NULL;        
}

        *Pengertian Tree dalam Struktur Data* Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.


Parent : predecssor satu level di atas suatu node.
Child : successor satu level di bawah suatu node.
Sibling : node-node yang memiliki parent yang sama dengan suatu node.
Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
Size : banyaknya node dalam suatu tree.
Height : banyaknya tingkatan/level dalam suatu tree.
Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
Leaf : node-node dalam tree yang tak memiliki seccessor.
Degree : banyaknya child yang dimiliki suatu node.

Pengertian Binaary Tree dalam Struktur Data
Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.




Node pada Binary Tree 
Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

Jumat, 13 Maret 2020