Tree AVL, RBT,

Tree adalah data struktur abstrak yang dapat menyimpan data dengan cara yang lebih efisien dan mengurangi waktu searching dan mengambil data. Tree memliki kumpulan node yang terhubung secara linear dan tidak memiliki relasi siklik.  Setiap node mengandung data dan ada nilai keynya.

Dalam Tree ada beberapa istilah yang sering dipakai:
-  Root: node inisial dari tree, node berapa di paling atas sebuah tree.
-  Node: bagian dari tree yang diibaratkan bulatan yang terhubung
-  Child: node yang terhubung ke node parent
-  Parent: node yang terhubung ke node child

Tipe - tipe Tree:
1. Binary tree: bentuk tree yang paling umum setiap node memiliki properti 2 pointer untuk terhubung ke node kiri dan kanan nya. Penempatan node pada binary tree tidak memiliki aturan.
2. Binary Search Tree: bentuk tree yang memiliki aturan dimana pada setiap node pointer sebelah kiri terhubung pada node dengan key-value yang lebih kecil dna pointer sebelah kanan terhubung pada node dengan key value yang lebih besar atau sebaliknya. Hal ini  memudahkan proses searching jika kita ingin mencari node dengan key value lebih kecil maka node disebelahkan bisa diabaikan.
3. AVL tree: binary search tree yang memiliki sifat self-balancing. Hal ini disebabkan jika ada kasus pada binary search tree dimana akan ada node yang panjang kekanan kebawah terus apabila key value pada node semakin besar, hal ini tentu tidak efisien, maka dari itu dibuatlah AVL tree ini. Sifat pada setiap node memiliki beda tinggi pada kanan dan kiri penghubungnya adalah 0, atau 1.
4. Red-Black Tree: RBT adalah jenis tree yang juga bersifat auto-balancing. Pada setiap node diberi warna merah atau hitam. Root selalu berwarna hitam. Tidak ada node merah yang berdekatan (terhubung). Setiap langkah dari sebuah node (termasuk root) ke anaknya yang NULL memiliki jumlah black node yang sama.
5. N-ary tree: artinya setiap node atau root bisa memiliki banyak cabang. N bisa kita tentukan nilainya. Jika N adalah 3 maka cabang maksimal yang dimiliki tree adalah 3.

Komentar

Posting Komentar

Postingan populer dari blog ini

Heap

Heap dibagi 2 yaitu max heap(elemen anak dari node lebih kecil) dan min heap (elemen anak dari node lebih besar) . Heap bisa diimplementasi dengan menggunakan array. Penggunaan heap bisa dalam selection algorithm, Djikstra’s algorithm dan Prim algorithm. Untuk sorting juga ada Heap Sort. Elemen dari heap disimpan secara sekuensial dalam array dari atas ke bawah, kiri ke kanan. Root selalu ditempatkan di index ke 1 untuk memudahkan perhitungan. Cara menentukan node relasi dari node x. Parent= x/2, left-child = 2 * x, right-child = 2*x+1. Insert dalam Min-Heap 1.       Taruh node pada index terahir dari array 2.       Upheap node tersebut untuk memperbaiki property heap *Upheap : mencari elemen atas nya, jika elemen parentnya lebih besar maka elemen tersebut akan ditukar. Proses ini terjadi secara rekursif sampai kondisi tidak memenuhi(mencapai root atau elemen parent lebih kecil). Delete dalam Min-Heap 1.   ...
Baca selengkapnya

Hash Table

1. Hash Table •  Hashing adalah teknik yang digunkan untuk menyimpan dan mengambil kunci dalam jangka waktu  yang cepat.  •  Dalam hashing, sebuah data misalnya string dapat diambil bagiannya(karakter) kemudian dijadikan key untuk disimpan pada table •  Hashing menggunakan indek untuk mengambil data pada penyimpanan untuk mempercepat pencaharian menggunakan hashed yang lebih pendek daripada nilai yang sebenarnya(lebih panjang). •  Hashing juga bisa disebut konsep mendistribusikan indeks kedalam sebuah  hash table menggunakan fungsi yang disebut  hash function . 2. Hash Function Ada banyak cara hashing string menjadi key. - Mid-Square - Division - Digit Extraction - Rotating Hash -Mid-Square     Key yang didapat dikudratkan kemudian diambil bagian tengah dari key     contohnya: key 3121 di kuadratkan menjadi 9740641 sehingga diambil bagian tengahnya 406    Penggunaan kuadrat agar address y...
Baca selengkapnya

Binary Search Tree (BST)

Struktur data binary search tree memberikan fitur searching dan sorting yang lebih cepat. insert dan delete yang lebih mudah juga.  Aturan penempatan node :  1. Untuk node yang lebih kecil dari node yang dibandingkan maka node tersebut ditempatkan dikiri 2. Untuk node yang lebih besar dari node yang dibandingkan maka node tersebut ditempatkan dikanan 3. Setiap node nilainya berbeda 4. Perbandingan mulai dari root, terus turun sampai dapat tempat kosong Operasi pada BST 1. search(x) 2. insert(x) 3. remove(x) 1. Search Misalnya nilai yang mau kita cari adalah x  - Mulai dari root  - Jika root mengandung x maka proses selesai  - Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari  secara rekursif pada subtree kanan 2. Insert  Misalnya nilai yang ingin kita masukkan adalah x  - Proses mulai dari root  -  Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari...
Baca selengkapnya