Hashing table and Binary Tree

Hashing adalah Struktur Data penting yang dirancang untuk menggunakan fungsi khusus yang disebut fungsi Hash yang digunakan untuk memetakan nilai yang diberikan dengan kunci tertentu untuk akses elemen yang lebih cepat. Efisiensi pemetaan tergantung pada efisiensi fungsi hash yang digunakan.

Pemetaan Indeks (atau Trivial Hashing) dengan negatif diperbolehkan

Mengingat array rentang terbatas berisi angka positif dan non-positif, mis., Elemen berada dalam kisaran dari -MAX hingga + MAX. Tugas kita adalah mencari apakah ada angka dalam array atau tidak dalam waktu O (1).

Karena rentang terbatas, kita dapat menggunakan pemetaan indeks (atau hashing trivial). Kami menggunakan nilai sebagai indeks dalam array besar. Karenanya kita dapat mencari dan memasukkan elemen dalam waktu O (1).

cara menangani angka negatif
Idenya adalah menggunakan array 2D ukuran hash [MAX + 1] [2]
Algoritma:

Assign all the values of the hash matrix as 0.
Traverse the given array:
    If the element eles is non negative assign 
        hash[eles][0] as 1.
    Else take the absolute value of eles and 
         assign hash[eles][1] as 1.

 CODE

// C# program to implement direct index 
// mapping with negative values allowed. 
using System; 

class GFG 
{ 

static int MAX = 1000; 

// Since array is global, it 
// is initialized as 0. 
static bool[,] has = new bool[MAX + 1, 2]; 

// searching if X is Present in 
// the given array or not. 
static bool search(int X) 
{ 
 if (X >= 0) 
 { 
  if (has[X, 0] == true) 
  { 
   return true; 
  } 
  else
  { 
   return false; 
  } 
 } 

 // if X is negative take the 
 // absolute value of X. 
 X = Math.Abs(X); 
 if (has[X, 1] == true) 
 { 
  return true; 
 } 

 return false; 
} 

static void insert(int[] a, int n) 
{ 
 for (int i = 0; i < n; i++) 
 { 
  if (a[i] >= 0) 
  { 
   has[a[i], 0] = true; 
  } 
  else
  { 
   has[Math.Abs(a[i]), 1] = true; 
  } 
 } 
} 

// Driver code 
public static void Main() 
{ 
 int[] a = {-1, 9, -5, -8, -5, -2}; 
 int n = a.Length; 
 insert(a, n); 
 int X = -5; 
 if (search(X) == true) 
 { 
  Console.WriteLine("BUDI"); 
 } 
 else
 { 
  Console.WriteLine("SINTA"); 
 } 
} 
}

Collision

Karena fungsi hash memberi kita sejumlah kecil untuk kunci yang 

merupakan integer atau string, ada kemungkinan 

bahwa dua kunci menghasilkan nilai yang sama. Situasi di mana 

peta kunci yang baru dimasukkan ke slot yang sudah ditempati di 

tabel hash disebut collision dan harus ditangani menggunakan beberapa 

teknik penanganan collision.

Ada dua metode utama untuk menangani tabrakan:
1) Separate Chaining
2) Open Addressing

Separate Chaining 

idenya adalah untuk membuat setiap sel tabel hash menunjuk ke 

daftar catatan terkait yang memiliki nilai fungsi hash yang sama.

Mari kita anggap fungsi hash sederhana sebagai "key mod 7" 

dan urutan tombol sebagai 50, 700, 76, 85, 92, 73, 101. 

Buka Mengatasi
Seperti Separate Chaining, Open Addressing adalah metode untuk 

menangani collision. Di Open Addressing, semua elemen disimpan 

di tabel hash itu sendiri. Jadi pada titik mana pun, ukuran tabel harus

lebih besar dari atau sama dengan jumlah total kunci (Perhatikan bahwa 

kami dapat menambah ukuran tabel dengan menyalin data lama jika diperlukan).

insert (k): Terus selidiki sampai slot kosong ditemukan. Setelah 

slot kosong ditemukan, masukkan k.

search (k): Terus selidiki sampai kunci slot tidak menjadi sama dengan k 

atau slot kosong tercapai.
delete (k): Hapus operasi itu menarik. Jika kami hanya menghapus kunci,

maka pencarian mungkin gagal. Jadi slot kunci yang dihapus ditandai

secara khusus sebagai "dihapus".
Sisipan dapat menyisipkan item di slot yang dihapus,

tetapi pencarian tidak berhenti di slot yang dihapus.

Struktur Data Binary Tree

Pohon yang unsurnya paling banyak memiliki 2 anak disebut binary tree.

Karena setiap elemen dalam binary tree hanya dapat memiliki 2 anak.

 CODE BINARYT TREE

//  C# program to introduce Binary Tree 
using System; 

/* Class containing left and right child 
of current node and key value*/
public class Node 
{ 
 public int key; 
 public Node left, right; 

 public Node(int item) 
 { 
  key = item; 
  left = right = null; 
 } 
} 

public class BinaryTree 
{ 
 // Root of Binary Tree 
 Node root; 

 // Constructors 
 BinaryTree(int key) 
 { 
  root = new Node(key); 
 } 

 BinaryTree() 
 { 
  root = null; 
 } 

 // Driver Code 
 public static void Main(String[] args) 
 { 
  BinaryTree tree = new BinaryTree(); 

  /*create root*/
  tree.root = new Node(1); 

  /* following is the tree after above statement 

   1 
   / \ 
  null null  */
  tree.root.left = new Node(2); 
  tree.root.right = new Node(3); 

  /* 2 and 3 become left and right children of 1 
   1 
   / \ 
   2  3 
  / \ / \ 
  null null null null */
  tree.root.left.left = new Node(4); 
  
  /* 4 becomes left child of 2 
     1 
    /  \ 
   2   3 
   / \  / \ 
   4 null null null 
  / \ 
  null null 
  */
 } 
} 

TIPE BINARY TREE

Full Binary Tree 

Binary Tree penuh jika setiap node memiliki 0 

atau 2 anak. Berikut ini adalah contoh pohon biner penuh. 

Kita juga dapat mengatakan pohon biner penuh adalah pohon 

biner di mana semua simpul kecuali daun memiliki dua anak.
 

complete Binary Tree:

Binary tree adalah complete Binary Tree

jika semua level terisi penuh kecuali mungkin level terakhir dan 

level terakhir memiliki semua kunci yang tersisa sebanyak mungkin.

Perfect Binary Tree 

Sebuah Binary tree adalah Perfect Binary Tree 

di mana semua node internal memiliki dua anak dan semua daun 

berada pada level yang sama. 

Balanced Binary Tree

binary tree seimbang jika ketinggian pohon adalah O (Log n) di 

mana n adalah jumlah node. Sebagai contoh, pohon AVL mempertahankan 

tinggi O (Log n) dengan memastikan bahwa perbedaan antara ketinggian 

sub pohon kiri dan kanan paling tinggi 1. Pohon Merah-Hitam 

mempertahankan tinggi O (Log n) dengan memastikan bahwa jumlah 

simpul Hitam pada setiap jalur akar ke daun sama dan tidak ada simpul 

merah yang berdekatan. Pohon-pohon Pencarian Biner Seimbang adalah 

kinerja yang baik karena mereka menyediakan O (log n) waktu untuk 

pencarian, masukkan dan hapus.

Singly Linked List

Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL

Linked List : artinya node-node tersebut saling terhubung satu sama lain.

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.

Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Pointer pokok yang digunakan yaitu head (menunjuk pada node awal) dan tail (menunjuk pada node terakhir)

typedef struct node {

int data;

struct node *next;

}node;//ganti

void ins_head(node **head, node **tail, int data){

node *temp=(node*)malloc(sizeof(node));

temp->next=NULL;

temp->data=data;

if(*head==NULL){*head=*tail=temp;

}else{

temp->next=*head;

 *head=temp;

}

}

void del_head(node **head, node**tail){

node *temp=*head;

if(*head==*tail){*head=*tail=NULL;

free(temp);

}else{*head=temp->next;

free(temp);

}

}

int main(){ node *head=NULL; node *tail=NULL; ins_head(&head,&tail,data); del_head(&head,&tail,data); return 0;