Heaps and Tries

HEAP

Heap adalah pohon complete binary tree biner yang berdasarkan memenuhi properti heap.

Apa jenis properti heap?

Min Heap:

Unsur setiap node adalah lebih kecil dibandingkan anak-anak.

Max Heap:

Unsur setiap node adalah lebih besar dibandingkan anak-anak.

Min-Heap 

Unsur setiap node lebih kecil dari elemen anak nya.

Ini menyiratkan bahwa elemen terkecil terletak pada akar pohon.

Unsur terbesar terletak di suatu tempat di salah satu node daun.


Heap dapat diimplementasikan dengan menggunakan linked-list, tapi jauh lebih mudah untuk menerapkan tumpukan menggunakan berbagai.

Contoh Min-Heap :

Aplikasi Heap :

Priority Queue

Temukan Algoritma (menemukan min / max elemen, median, k-terbesar elemen, dll).

Algoritma Dijkstra (menemukan jalan terpendek dalam grafik)

Prim Algoritma (menemukan pohon spanning minimum)

Heap Sort

O (n.lg (n)) algoritma.

Implementasi Array :

Tumpukan biasanya diimplementasikan dalam sebuah array.

Unsur-unsur yang disimpan secara berurutan dari indeks 1 sampai N dari atas ke bawah dan dari kiri ke simpul kanan pohon.

Akar disimpan dalam indeks 1

(Kita membiarkan indeks 0 kosong / tidak terpakai, untuk tujuan kenyamanan).

Insertion Min-Heap

 insert new node(20)

 insert new node(5)

 (continue)

Deletion Min-Heap

Di sini kita hanya perhatian dengan penghapusan elemen terkecil yang terletak pada akar.

Ganti root dengan elemen terakhir dari tumpukan.

Menurunkan jumlah elemen dalam tumpukan.

akar Downheap (memperbaiki properti tumpukan nya).

 delete node(7)

 (continue)

Heap Complexity

•find-min  : O(1)

•insert  : O(log(n))

•delete-min  : O(log(n))

Menyisipkan dan menghapus-min tergantung pada tinggi pohon, yang

adalah log (n), ketinggian pohon biner lengkap.

Max-Heap

Unsur setiap node lebih besar dari elemen anak nya.

Ini menyiratkan bahwa elemen terbesar terletak pada akar pohon.

Max-tumpukan memegang prinsip yang sama seperti min-heap dan dapat digunakan untuk membuat antrian prioritas yang perlu menemukan elemen terbesar bukan yang terkecil.

Min-Max Heap

Kondisi tumpukan bergantian antara minimum dan tingkat maksimum untuk tingkat

Setiap elemen di bahkan tingkat / aneh lebih kecil dari semua anak-anaknya (min-level).

Setiap elemen pada aneh / bahkan tingkat lebih besar dari semua anak-anaknya (max-level).

Tujuan dari min-max heap adalah untuk memungkinkan kita untuk menemukan kedua elemen terkecil dan terbesar dari tumpukan pada saat yang sama.

TRIES

Tries (prefix tree) adalah ordered tree data structure yang digunakan untuk menyimpan array asosiatif (biasanya string)

TRIE berasal dari kata reTRIEval, karena TRIES dapat menemukan satu kata dalam kamus dengan hanya awalan kata.

harshing

Hashing adalah transformasi dari string karakter menjadi nilai panjang biasanya lebih pendek atau kunci yang mewakili string asli.

Hashing digunakan untuk indeks dan mengambil item dalam database karena lebih cepat untuk menemukan item menggunakan kunci hash lebih pendek daripada untuk menemukannya menggunakan nilai asli

HASH TABLE

tabel hash adalah tabel (array) di mana kita menyimpan string asli. Indeks meja adalah kunci hash sementara nilai adalah string asli.

Ukuran tabel hash biasanya beberapa kali lipat lebih rendah dari jumlah total kemungkinan string, sehingga beberapa string yang mungkin memiliki hash-key yang sama.

Sebagai contoh, ada 267 (8031810176) string dengan panjang 7 terdiri dari huruf kecil saja.

btree

pohon AVL adalah sebuah pohon biner berurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'. Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left<root<right.



Insersi
Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).
1) Rotasi Kiri
2) Rotasi Kanan

T1, T2 dan T3 adalah sub pohon
di-root dengan y (di sebelah kiri) atau x (di
sisi kanan)
     y x
    / \ Rotasi Kanan / \
   x T3 - - - - - - -> T1 y
  / \ <- - - - - - / / \
 T1 T2 Putaran Kiri T2 T3
Kunci di kedua pohon di atas mengikuti
mengikuti pesanan
 kunci (T1) <kunci (x) <kunci (T2) <kunci (y) <kunci (T3)
Jadi properti BST tidak dilanggar di mana pun.

Langkah-langkah yang harus diikuti untuk pemasangan
Biarkan simpul yang baru dimasukkan menjadi w
1) Lakukan insert BST standar untuk w.
2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Biarkan z menjadi simpul tidak seimbang pertama, y ​​menjadi anak dari z yang datang di jalan dari w ke z dan x menjadi cucu dari z yang datang di jalur dari w ke z.
3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan z. Ada 4 kemungkinan kasus yang perlu ditangani karena x, y dan z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:
a) y adalah anak kiri dari z dan x adalah anak kiri dari y (Kasing Kiri Kiri)
b) y adalah anak kiri z dan x adalah anak kanan y (Left Right Case)
c) y adalah anak kanan z dan x adalah anak kanan y (Right Right Case)
d) y adalah anak kanan z dan x adalah anak kiri y (Kasus Kiri Kanan)


B-Tree adalah pohon pencarian self-balancing. Di sebagian besar pohon pencarian self-balancing lainnya (seperti AVL dan Red-Black Trees), diasumsikan bahwa semuanya ada dalam memori utama. Untuk memahami penggunaan B-Trees, kita harus memikirkan sejumlah besar data yang tidak dapat ditampung dalam memori utama. Ketika jumlah kunci tinggi, data dibaca dari disk dalam bentuk blok. Waktu akses disk sangat tinggi dibandingkan dengan waktu akses memori utama. Gagasan utama menggunakan B-Trees adalah untuk mengurangi jumlah akses disk. Sebagian besar operasi pohon (pencarian, masukkan, hapus, maks, min, ..etc) memerlukan O (h) akses disk di mana h adalah ketinggian pohon. B-tree adalah pohon yang gemuk. Ketinggian B-Trees dijaga tetap rendah dengan meletakkan kunci maksimum yang mungkin dalam simpul B-Tree. Secara umum, ukuran simpul B-Tree dijaga sama dengan ukuran blok disk. Karena h rendah untuk B-Tree, akses disk total untuk sebagian besar operasi berkurang secara signifikan dibandingkan dengan Binary Search Trees yang seimbang seperti AVL Tree, Red-Black Tree, ..etc.
Properti B-Tree
1) Semua daun berada pada level yang sama.
2) B-Tree didefinisikan dengan istilah tingkat minimum ‘t ’. Nilai t tergantung pada ukuran blok disk.
3) Setiap node kecuali root harus mengandung setidaknya kunci t-1. Root mungkin berisi kunci minimal 1.
4) Semua node (termasuk root) dapat berisi maksimal 2t - 1 kunci.
5) Jumlah anak-anak dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1.
6) Semua kunci simpul diurutkan dalam urutan yang meningkat. Anak antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2.
7) B-Tree tumbuh dan menyusut dari akar yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah.
8) Seperti Pohon Penelusuran Biner seimbang lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).