Tree

Heap and Tries Heap Heap adalah struktur data khusus berbasis pohon di mana pohon adalah complete binary tree. Umumnya, Heaps dapat dua jenis: Max-Heap: dalam Max-Heap, key yang ada di node root harus terbesar di antara key yang ada di semua child. Properti yang sama harus dapat direkursif untuk semua sub-tree di binary tree. Min-Heap: dalam Min-Heap, key yang ada di node root harus minimum di antara key yang ada di semua child. Properti yang sama harus dapat direkursif  untuk semua sub-tree di binary tree. Min Heap Setiap node lebih kecil dari masing-masing childnya Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node Max Heap Setiap node lebih besar dari masing-masing childnya Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node Min-Max Heap Heap dengan Min heap pada level ganjil dan Max heap pada level genap Heap dapat diimplementasi dengan array maupu...

AVL Tree AVL Tree adalah binary search tree yang telah disortir menjadi seimbang. AVL Tree merupakan nama dari kedua penemu AVL Tree yaitu G.M.Adelson Veleskii dan E.M.Landis. Contoh AVL Tree: Contoh Binary Search Tree yang belum di sortir: Cara menentukan Height dan Balance Factor : Height : - Jika node (root) tidak memiliki subtree heightnya = 0 - Jika node adalah leaf, height =  1 - Jika internal node, maka height =  height tertinggi dari anak + 1 Balance Factor : -selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0. Ada 2 jenis rotation dalam AVL Tree: 1. Single Rotation 2. Double Rotation Rotasi pertama: Rotasi kedua: B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu ...

Source file tugas GSLC: https://drive.google.com/file/d/1yXr5sOSjbaUJSOnyvdoeDRfvkQukFGCc/view?usp=sharing

1. Circular Single Linked List Circular single linked list adalah single linked list yang tidak menerima value NULL yang dikarenakan node terakhir akan menunjuk ke head pointer sehingga circular single linked list tidak menerima value NULL. 2. Doubly Linked List Doubly linked list adalah single linked list yang memiliki 2 arah pointer dimana sebuah node memiliki 2 pointer yaitu next dan prev. Ada 2 cara untuk menyunting doubly linked list: a. Insert Insert digunakan untuk memasukan node baru ke dalam doubly linked list dan mengkoneksikan node tersebut dengan node yang sudah ada. struct tnode *node = (struct tnode*) malloc (sizeof (struct tnode); node->value = x; node->next  = NULL; node->prev  = tail; tail->next = node; tail = node; b. Delete Delete digunakan untuk menghapus node tertentu dari doubly linked list. Jika menghapus node saja: free  (head); head = NULL; tail = NULL; Jika menghapus head: head = head.next; free (head.prev); h...

Binary Search Tree Binary Search Tree mempunyai 2 aturan yaitu: 1. Jika value node lebih besar dari node, maka node tersebut akan menjadi leaf kanan node tersebut. 2. Jika value node lebih kecil dari node, maka node tersebut akan menjadi leaf kiri node tersebut. Ini adalah contoh kode create dan insert untuk binary search tree: #include<stdio.h> #include<stdlib.h> struct node{ int key; struct node *left, *right; }; // Function untuk membuat node baru struct node *newNode(int item){ struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inorder(struct node *root) { if (root != NULL) { inorder(root->left); printf("%d \n", root->key); inorder(root->right); } } /* Function untuk insert */ struct node* insert(struct node* node, int key){ if (node == NULL) { return newNode(key); } if (key < node->key){ node->left = i...

Hashing, Hash Table dan Binary Tree Hashing Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa. Hashing dilakukan dengan membuat fungsi hash. Hasil dari fungsi hash dimasukkan ke dalam hash table. Hash Table adalah salah satu contoh implementasi linked list dalam data struktur. Hash table digunakan dalam penyimpanan data sementara. Ada banyak cara untuk hashing string ke sebuah key: 1. Mid-square 2. Division (most common) 3. Folding 4. Digit Extraction 5. Rotating Hash Contoh hash table yang kurang efisien dan yang efisien: Contoh yang kurang efisien Contoh fungsi hash yang efisien: Sebaik apapun fungsi hash yang kita buat, collision tidak dapat dihindari, oleh karena itu ada banyak teknik untuk menghindari collision: 1. Separate Chaining (Open Hashing) Separate Chahining adalah teknik yang paling banyak digunakan untuk resolusi tabrakan. Separate Chaining biasanya diimplementasikan menggunak...