Tugas GSLC Data Structure: Rangkuman Final Data Structure

Rangkuman Final Data Structure
Nama : Arvin Aryaguna
NIM : 2301947685

Kelas : CB01-CL

Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)

Linked List

A. Pengertian

Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence. Selain itu ada beberapa istilah dalam linked list yaitu head dan tail.

- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

- Tail adalah element yang berada pada posisi terakhir dalam suatu linked list

B. Macam - macam Linked List

1. Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Contoh Codingannya:

struct Mahasiswa{

char nama[25];

int usia;

struct Mahasiswa *next;

}*head,*tail;

2. Double Linked List

Double Linked List Merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh Codingannya:

Struct Mahasiswa{

char nama[25];

int usia;

struct Mahasiswa *next,*prev;

}*head,*tail;

3. Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

- Circular Single Linked List

- Circular Double Linked List

4. Multiple Linked List

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

Perbedaan Linked List dan Array

Linked List	Array
Koleksi linear dari elemen data	Koleksi linear dari node
Menyimpan data dalam lokasi memori yang berurutan	Tidak menyimpan node dalam lokasi memori yang berurutan
Dapat diakses secara acak menggunakan indeks	Hanya dapat diakses secara berurutan
Jumlah memory dapat bertambah jika dibutuhkan	Jumlah memory sudah fix sesuai jumlah array yang di inisialisasi di awal

Memory Allocation

Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut.

contoh penggunaan malloc:

int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));
contoh penggunaan free:

free(curr);
Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah node/data baru.

Operasi dalam Linked List :

1. Push

Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert melalui depan (pushDepan) ataupun belakang (pushBelakang). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya, dan sebaliknya pushBelakang berarti data yang paling baru akan berada di belakang data lainnya.

Representasinya adalah sebagai berikut:

- PushDepan: 5, 3, 7, 9 maka hasilnya adalah: 9 ->7 ->3 -> 5 -> NULL

- PushBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 ->3 ->7 ->9 -> NULL

2. Pop

Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki 2 kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data paling depan, dan popBelakang berarti data yang akan dihapus adalah data paling belakang (akhir).

Dalam penerapan code single linked list, umumnya hanya digunakan pointer head sebagai pointer yang menunjuk pada linked list. Namun dalam pembahasan artikel ini akan digunakan 1 pointer tambahan, yakni TAIL untuk menunjuk data terakhir di dalam linked list dalam mempermudah proses pembahasan.

Stack and Queue

1. STACK(Tumpukan)

A. Pengertian Stack (Tumpukan)

Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH) dan penghapusan elemen dari tumpukan(POP). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakan system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan (Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.

Sebelum struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan menggunakan tata susunan linear (larik) dan sebuah variable, yang dikemas dalam tipe data record. Stack (tumpukan) adalah struktur data bertipe record yang terdiri dari field elemen, bertipe larik/array dengan indeks dari 1 sampai dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari 0 (saat kosong) sampai dengan MaksTum (Maksimum Tumpukan).

B. Operasi – operasi pada Stack (Tumpukan)

Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi - operasi yang dapat diterapkan adalah sebagai berikut :

1. Push : digunakan untuk menambah item pada Stack pada Tumpukan paling atas.

2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

3. Clear : digunakan untuk mengosongkan Stack.

4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.

5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.

6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai maksimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang dapat diambil.

C. Macam – macam Stack

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

2. QUEUE (ANTRIAN)

A. Definisi Queue (Antrian)

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

B. Operasi-operasi pada Queue

1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.

2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

3. EnQueue : berfungsi memasukkan data kedalam antrian.

4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.

5. Clear : menghapus seluruh antrian

6. IsEmpty : memeriksa apakah antrian kosong

7. IsFull : memeriksa apakah antrian penuh.

Hashing and Hash Table

Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Kelebihan dari hash table antara lain sebagai berikut:

· Hash table relatif lebih cepat

· Kecepatan dalam insertions, deletions, maupun searching relatif sama

Metode-metode Hash Table yang sering digunakan adalah:

1. Linear probingApabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus
(h+1) mod m.

2. Quadratic probing / squared probing

Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.

3. Double hashing
Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.

Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

Selain metode-metode yang sudah disebutkan di atas, terdapat juga beberapa metode lain diantaranya :

1. Coalesced hashing

Gabungan dari chaining dan openaddressing. Coalesced hashing menghubungkan ke tabel itu sendiri. Seperti open addressing, metode ini memiliki keunggulan pada penggunaan tempat dan cache dibanding metode chaining. Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih menyebar, tetapi pada metode ini record yang disimpan tidak mungkin lebih banyak daripada ruang yang disediakan tabel.

2. Perfect hashing

Jika record yang akan digunakan sudah diketahui sebelumnya, dan jumlahnya tidak melebihi jumlah ruang pada tabel hash, perfect hashing bisa digunakan untuk membuat tabel hash yang sempurna, tanpa ada bentrokan.

3. Probabilistic hashing

Kemungkinan solusi paling sederhana untuk mengatasi bentrokan adalah dengan mengganti record yang sudah disimpan dengan record yang baru, atau membuang record yang baru akan dimasukkan. Hal ini bisa berdampak tidak ditemukannya record pada saat pencarian. Metode ini digunakan untuk keperluan tertentu saja.

4. Robin Hood hashing

Salah satu variasi dari resolusi bentrokan double hashing. Ide dasarnya adalah sebuah record yang sudah dimasukkan bisa digantikan dengan record yang baru jika nilai pencariannya (probe count – bertambah setiap menemukan tempat yang sudah terisi) lebih besar daripada nilai pencarian dari record yang sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk waktu yang diperlukan untuk pencarian.

Binary Tree dan Binary Search Tree

Tree merupakan salah satu bentuk struktur data tidak linear 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 saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

a. Prodecessor : node yang berada diatas node tertentu.

b. Successor : node yang berada di bawah node tertentu.

c. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

d. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

e. Parent : predecssor satu level di atas suatu node.

f. Child : successor satu level di bawah suatu node.

g. Sibling : node-node yang memiliki parent yang sama dengan suatu node.

h. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

i. Size : banyaknya node dalam suatu tree.

j. Height : banyaknya tingkatan/level dalam suatu tree.

k. Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

l. Leaf : node-node dalam tree yang tak memiliki seccessor.

m. Degree : banyaknya child yang dimiliki suatu node.

Binary Tree didefinisikan sebagai struktur data yang memfasilitasi akses data yang lebih cepat yang disimpan dalam memori sekunder dengan membuat dan menggunakan indeks untuk mengakses sejumlah besar data. Ini mirip dengan menggunakan indeks dalam buku untuk mengakses konten terkait secara cepat. Binary Tree cocok untuk membuat kamus dengan menyimpan kunci dan catatan sehingga dengan menyediakan kunci, seseorang dapat mengakses catatan yang sesuai.

Jenis-jenis Binary Tree :

· Perfect Binary Tree

adalah binary tree yang di mana setiap level berada pada kedalaman yang sama.

· Complete Binary Tree

adalah binary tree yang di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node berada sejauh mungkin. Pohon biner sempurna adalah pohon biner lengkap.

· Skewed Binary Tree

adalah binary tree di mana setiap node memiliki paling banyak satu anak.

· Balanced Binary Tree

adalah binary tree di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya (skema penyeimbang yang berbeda memungkinkan definisi yang berbeda tentang "lebih jauh").

Binary Search Tree (BST) adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Aturan main Binary Search Tree :

- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.

- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Operasi-operasi dalam Binary Search Tree :

A. Searching

Pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key dengan node root tersebut. Bila nilai root node sama seperti key yang dicari, maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.

B. Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.

C. Deletion
Terdapat beberapa aturan dasar yang perlu diperhatikan dalam langkah menghapus suatu node, yakni.

1. Bila node tersebut tidak memiliki child, node tersebut dapat langsung dihapus

2. Bila node tersebut memiliki child, maka node (parent) tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent

3. Bila node tersebut memiliki dua children, maka langkah pertama yang dilakukan ialah mengganti nilai node parent dengan salah satu child, hapus nilai node parent awal, secara recursive hapus nilai node child yang telah digunakan untuk mengganti nilai node parent sebelumnya, kemudian lakukan seperti pada kasus pertama atau kedua

Suatu node dengan children, lebih sulit untuk dihapus. Bila node child lebih besar dari node parent yang digantikan maka disebut in-order successor. Sebaliknya bila node child lebih kecil dari node parent yang digantikan, maka disebut in-order predecessor.

AVL TREE

A. Pengertian

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Selain itu terdapat 2 proses penyeimbangan pada AVL Tree yaitu dengan cara Single rotation dan Double rotation.

B. Single Rotation

Single rotation adalah rotasi yang di lakukan hanya sekali agar sebuah tree AVL cara ini dapat menyelesaikan kasus luar.

Double rotation

Double rotation adalah rotasi yang dilakukan lebih dari sekali dan sedangkan cara ini untuk menyelesaikan kasus dalam.

Cara menentukan Height dan Balance Factor :Note :

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.

AVL Tree Operations : Insertion

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi

– Kasus 1 dan 2 dengan single rotation

– Kasus 3 dan 4 dengan double rotation

AVL Tree Operations : Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

Heap

Heap adalah Complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap. Heap biasanya diimplementasikan pada array dan indexnya dimulai dari 1 bukan 0.

Heap dibagi menjadi 3 jenis yaitu:

1. Min Heap: node paling kecil adalah root dan semakin kebawah levelnya semakin besar

Cara insert:

Jika mi(elemen terkecil terletak di root): Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah. Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh kecil maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lebih besar dr parentnya.

Cara delete:

Jika min heap(elemen terkecil terletak di root): Maka yang dihapus merupakan rootnya(elemen terkecil). Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).

2. Max Heap: node paling besar adalah root dan semakin kebawah levelnya semakin kecil

Cara insert:

Jika max heap(elemen terbesar terletak di root): Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah. Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh besar maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lebih kecil dr parentnya.

Cara delete:

Jika max heap(elemen terkecil terletak di root): Maka yang dihapus merupakan rootnya(elemen terbesar). Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).

Heaps · codepath/compsci_guides Wiki · GitHub

3. Max-Min Heap: min-heap dan max-heap levelnya saling bergantian pada tree

Cara insert:

· Insert node baru (key) pada index selanjutnya (setelah index terakhir)

1. jika key terletak pada level min : bandingkan dengan parentnya

Jika parent < key maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key setelah swap)

Jika parent > key, upheapmin dari posisi key (dibandingkan dengan grandparentnya dari posisi key).

2. jika key terletak pada level max :

Jika parent > key maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi keysetelah swap)

Jika parent < key, upheapmax dari posisi key(dibandingkan dengan grandparentnya dari posisi key).

Cara delete:

terdapat 2 jenis delete, yaitu delete min, dan delete max

- Delete Min, menghapus node terkecil, yaitu root

- Delete Max, menghapus node terbesar, yaitu salah satu dari anak root

konsep deletenya sama :

- node yang dihapus digantikan oleh node index terakhir

- lakukan downheapmin jika delete min, atau downheapmax jika delete max

Heap Sort merupakan salah satu dari 6 jenis metode sort atau sorting (melakukkan pengurutan). Heap sort ini menggunakan teknik sorting dengan menggunakan teknik heap. Teknik tersebut tersebut merupakan teknik pengelolaan data yang menggunakan binary tree. Data yang dikelola maksudnya adalah bagaimana data yang sudah terstruktur akan di organisir kembali jika kita memasukkan data baru atau meng-insert data baru, atau pula menghapus data. Teknik itulah yang diterapkan di metode heap sort. Inti dari pengurutan secara heap adalah pengerjaannya yang dilakukkan dengan pengurutan ascending dan descending, jadi ada dua kali pengurutan.

Tries
Tries adalah Binary Tree dimana isi dari tersebut adalah kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).

danvk.org » Tries, the Perfect Data Structure