Postingan

Heap dan tries

Gambar
Nama : Raymon Elnardi NIM   : 2301908620       Di Blog kali ini kita akan membahas tentang Heap. berbeda dengan AVL tree dan RB Tree, Heap bukanlah Binary Search Tree. secara umum tree di buat menggunakan array agar lebih mudah menentukan posisi childernnya. untuk mencari parent : node / 2 untuk mencari left-child : 2 * node untuk mencari right-child ; 2 * node + 1 misalnya untuk mencari parent :2 dan 3 merupakan childern dari 1 karena 2/2 = 1 dan 3/2 = 1 (karena integer). inilah mengapa biasanya root pada heap berada di index 1 bukan di index 0 Heap secara umum terbagi menjadi 3 : Min Heap, Max Heap, dan Min-Max Heap. secara umum, heap memiliki 3 buah fungsi 1. Find min atau max ( tergantung jenis heap) 2. Insert (memasukkan node baru ke leaf) 3. pop (menghapus node yang berada di root) - Min Heap adalah Binary Tree yang setiap elemnt dari node-nya bernilai lebih kecil dibandingkan element dari childern-nya - Ini berarti elemenet terkecil berada di root dari tree
Posting Komentar
Baca selengkapnya

AVL Tree

Gambar
Nama : Raymon Elnardi Nim  : 2301908620 AVL Tree ( Georgy Adelson-Velsky and Landis' tree) adalah BST yang diseimbangkan (Balanced). Tujuannya di terapkan AVL Tree kedalam BST adalah untuk mecegah worst case dari BST (Skewed BST) dan memastikan height dari BST menjadi O Log N. Adapula hal hal yang harus diketahui terlebih dahulu sebelum melanjutkan AVL Tree, 1. height dari sebuah subtree yang kosong bernilai 0 2. height dari sebuah leaf bernilai 1 3. height dari sebuah internal node sama dengan maksimum height dari childern ditambah 1 Balance Factor, selisih dari subtree kanan dan subtree kiri syarat untuk membuat AVL Tree adalah, setiap node pada Tree harus memiliki Balance Factor berkisar -1 sampai 1. gambar diatas adalah contoh dari AVL Tree. Gambar diatas menjelaskan bagaimana proses berubahnya BST non-AVL menjadi AVL Tree. Dari gambar diatas dapat dilihat bahwa terdapat pelanggaran pada node 2 karena Balance Factornya bernilai 2, maka dari kita perlu meng
Posting Komentar
Baca selengkapnya

Binary Search Tree

Gambar
Nama : Raymon Elnardi Nim   : 2310908620 Kelas : LL01        Hari ini akan membahas tentang Binary Search Tree atau disingkat BST. BST adalah sebuah data structure yang non-linear. BST memiliki sifat dimana setiap subtree yang berada di sebelah kiri node akan bernilai lebih kecil daripada node itu sendiri, sedangkan subtree yang berada di sebelah kanan node akan bernilai lebih besar daripada node itu. tapi bagaimana jika bernilai sama dengan node ? BST sifatnya adalah mensortir nilai sehingga nilai yang bernilai sama akan diabaikan perintahnya. BST memiliki 3 buah fingsi umum yaitu : Find, Insert, dan Delete. Tetapi pertama-tama kita perlu struct untuk node tersebut. ==================================================================== ||struct node ||{ ||     int key; ||     struct node *left, *right; ||}; =====================================================================        Codingan ini digunakan untuk wadah node tersebut, key untuk menyimpan value
Posting Komentar
Baca selengkapnya