AVL TREE
AVL Tree
Adalah binary tree yang dapat menyeimbangkan diri sendiri.
Hal ini agar tidak akan terbentuknya skewed binary search tree yang akan
membuat proses searching binary tree tersebut lama
.
Agar tetap balance dalam AVL Tree terdapat peraturan yaitu kedalaman
atau height subtree kiri dan kanan sebuah node dalam avl tree hanya boleh beda
1. Jika bedanya lebih dari 1 maka peraturan AVL Tree tersebut terlanggar.
Berikut contoh gambar AVL Tree yang tidak seimbang
Dalam gambar diatas dapat dilihat bahwa node yang berisi 17
melanggar peraturan AVL Tree karena subtree kirinya memiliki height 2 sedangkan
subtree kanannya heightnya 0. Sehingga perbedaan heightnya lebih dari 1.
Untuk membalance atau membenarkan AVL Tree yang sudah tidak
seimbang maka terdapat 2 cara yaitu:
1. Single Rotation:
Ketika node yang melanggar peraturan AVL Tree ke arah
node yang membuat tidak seimbangnya itu dua arah pertamanya lurus atau kiri dan
kiri atau kanan dan kanan.
Berikut contoh gambar AVL Tree yang harus di single rotate
Cara kerja single rotation:
Tarik node yang melanggar peraturan AVL ke
arah lawannya terdapat node yang membuat tidak seimbangnya tree tersebut.
Sehingga child dari node yang ditarik tersebut menjadi rootnya dan disesuaikan
child dari node-node tersebut. (Untuk membantu menyesuaikan child coba saja
insert ulang child-child tersebut).
Berikut gambar proses Single Rotation:
2. Double Rotation:
Ketika node yang melanggar peraturan AVL Tree ke arah
node yang membuat tidak seimbangnya itu dua arah pertamanya tidak lurus atau
kiri dan kanan atau kiri dan kanan.
Cara kerja Rotation Pertama Double Rotation:
Tarik
node ke dua dari node yang melanggar peraturan AVL tree kemudian sesuaikan dulu
child nya. Berikut contoh gambar Proses Rotasi pertama pada Double Rotation:
Setelah itu lakukan first rotation dan juga pastikan childnya sesuai agar AVL Tree nya seimbang.
Berikut contoh gambar Proses Rotasi kedua pada Double Rotation:
Deletion & Insertion:
Untuk proses Delete dan Insert pada AVL Tree masih sama
seperti Binary Search Tree tetapi harus diperiksa subtree kiri dan kanan setiap
node dari node yang di insert atau didelete hingga root untuk memastikan AVL
Tree tetap seimbang.
Nama: Jordy Ferdian
Nim: 2301888524
Kelas: LP01
Demikian rangkuman saya untuk AVL Tree dari VC dan juga ppt
Binusmaya. Mohon maaf jika ada kesalahan. Terima kasih.
Heap & Tries
Pada
minggu ini kami belajar heaps & tries, berikut adalah rangkuman saya:
Heap:
Heap
adalah complete binary tree yang memenuhi properti heap.
Properti
heap terdapat 2 yaitu:
1. Min heap:
Setiap
elemen pada node lebih kecil dari pada childnya.
2. Max heap:
Setiap
elemen pada node lebih besar dari pada childnya
Min Heap:
Pada min heap setiap element pada node lebih kecil dari pada
childnya dan elemen terkecil terdapat di root.
Berikut adalah contoh gambar Min Heap:
Heap biasanya diimplementasikan pada array dan dimulai dari
index 1 agar lebih mudah untuk relasi node parent, left dan right childnya.
Untuk mencari tahu index dari node parent, left dan right
child sebuah node adalah
Misalkan index node nya adalah x maka:
Index Parent(x) = x / 2
Index Left-child(x)
= 2 * x
Index Right-child(x)
= 2 * x + 1
Insertion pada Min Heap:
Node baru
diinsertkan pada akhir heap atau setelah index terakhir pada array.
Setelah itu
perbaiki heapnya agar memenuhi property heap dengan cara upheap.
Berikut adalah code untuk Insert Min-Heap:
void insertHeap(int x) {
nelement++; //Tambahkan jumlah elemen di array
arrHeap[nelement] = x; //elemen baru dimasukkan pada akhir array
upHeap(nelement); //Lalu upheap element tersebut
}
Berikut adalah code untuk Insert Min-Heap:
void insertHeap(int x) {
nelement++; //Tambahkan jumlah elemen di array
arrHeap[nelement] = x; //elemen baru dimasukkan pada akhir array
upHeap(nelement); //Lalu upheap element tersebut
}
Upheap pada Min Heap:
Bandingkan nilai pada node sekarang dengan parentnya. Jika nilai pada node sekarang lebih kecil dari pada parent maka ditukar. Lalu dengan parentnya lagi dan seterusnya hingga nilai pada parent node lebih kecil dari pada node sekarang.
Berikut
adalah gambar contoh dari upheap pada min heap:Bandingkan nilai pada node sekarang dengan parentnya. Jika nilai pada node sekarang lebih kecil dari pada parent maka ditukar. Lalu dengan parentnya lagi dan seterusnya hingga nilai pada parent node lebih kecil dari pada node sekarang.
Berikut adalah code untuk Upheap pada Min-Heap:
void upHeap(int index) {
if (index == 1) return; //Jika elemennya di root berarti upheap berhenti
int parentIndex = index / 2;
if (arrHeap[index] < arrHeap[parentIndex]) {
swap(&arrHeap[index], &arrHeap[parentIndex]); //Jika parent lebih besar dari pada element
maka ditukar
upHeap(parentIndex); //Lalu upheap lagi
}
}
Deletion pada Min Heap:
Deletion
pada Min heap hanya menghapus rootnya saja atau delete elemen terkecil. Setelah dihapus maka digantikan
dengan node terakhir pada heap. Setelah itu perbaiki heapnya agar memenuhi property
heap dengan cara downheap.
Berikut adalah code untuk Deletion pada Min-Heap:
void deleteMin() {
//Pada code ini yang dihapus itu root atau elemen min
if (nelement == 0) {
printf("Heap is empty!\n");
}
if (nelement == 1) {
nelement--;
}
swap(&arrHeap[1], &arrHeap[nelement]); //Pertama tukar nilai pada root/minnya dengan elemen pada array terakhir
nelement--; //Lalu didelete elemen terakhir pada array
downHeap(1); Lalu downheap elemen pada root
}
Berikut adalah code untuk Deletion pada Min-Heap:
void deleteMin() {
//Pada code ini yang dihapus itu root atau elemen min
if (nelement == 0) {
printf("Heap is empty!\n");
}
if (nelement == 1) {
nelement--;
}
swap(&arrHeap[1], &arrHeap[nelement]); //Pertama tukar nilai pada root/minnya dengan elemen pada array terakhir
nelement--; //Lalu didelete elemen terakhir pada array
downHeap(1); Lalu downheap elemen pada root
}
Downheap pada Min Heap
Bandingkan nilai pada node sekarang dengan left dan
right childnya. Jika node sekarang lebih kecil dari pada left dan right child
maka tukarkan dengan child yang terkecil. Lalu bandingkan dan tukarkan lagi
dengan child berikutnya hingga node sekarang lebih kecil dari pada kedua
childnya atau sudah sampai leaf.
Berikut
adalah gambar contoh dari deletion dan downheap pada min heap:
void downHeap(int index) {
int toIndex = index;
if (2*index <= nelement && arrHeap[index] > arrHeap[2*index]) {
toIndex = 2*index;
}
if (2*index+1 <= nelement && arrHeap[toIndex] > arrHeap[2*index+1]) {
toIndex = 2*index+1;
}
if (index == toIndex) return;
swap(&arrHeap[index], &arrHeap[toIndex]);
downHeap(toIndex);
}
Max Heap:
Pada max heap setiap element pada node lebih besar dari pada
childnya dan elemen terbesar terdapat di root.
Insertion dan deletion pada Max Heap kurang lebih sama
seperti pada Min Heap bedanya adalah jika upheap pada Min heap node sekarang
ditukar dengan parentnya jika node sekarang lebih kecil dari pada parent.
Tetapi pada Max heap node sekarang ditukar dengan parentnya jika node sekarang
lebih besar dari pada parent.
Kemudian down heap pada Min heap node sekarang ditukar dengan childnya yang
lebih kecil sedangkan pada Max Heap node sekarang ditukar dengan childnya yang
lebih besar.
Min-Max Heap:
Pada Min-max heap kondisi heapnya berganti-ganti antara min
dan max di setiap level. Pada level yang ganjil maka node nya lebih kecil dari pada childnya
sedangkan pada node yang genap maka nodenya lebih besar dari pada childnya.
Berikut adalah contoh gambar min-max heap:
Insertion pada min
max heap :
Insertion node baru pada min-max heap dimasukkan pada akhir
heap atau setelah index terakhir di array. Setelah itu di upheap untuk memenuhi
properti heapnya. Tetapi insertion pada min max heap berbeda yaitu:
Jika node baru terdapat pada min-level maka :
Jika parent node baru lebih kecil dari pada node baru tukar
value mereka lalu upheapmax dari parentnya. Jika parent node baru tidak lebih
kecil dari pada node baru maka upheapmin dari node baru.
Jika node baru terdapat pada max level maka:
jika parent node baru lebih besar dari pada node baru maka tukarkan nilai mereka dan upheapmin dari parentnya. Jika parent node baru tidak lebih besar dari pada node baru maka upheapmax dari node baru.
jika parent node baru lebih besar dari pada node baru maka tukarkan nilai mereka dan upheapmin dari parentnya. Jika parent node baru tidak lebih besar dari pada node baru maka upheapmax dari node baru.
Upheapmax dan Upheapmin
Upheapmin:
bandingkan nilai node sekarang dengan nilai grand parentnya. Jika nilai node
sekarang lebih kecil daripada nilai grand parentnya maka tukarkan nilai mereka
dan lanjutkan upheapmin pada grand-parent node.
Berikut adalah contoh gambar upheapmin:
Upheapmax:
bandingkan nilai node sekarang dengan nilai grand parentnya. Jika nilai node
sekarang lebih besar daripada nilai grand parentnya maka tukarkan nilai mereka
dan lanjutkan upheapmax pada grand-parent node.
Berikut
adalah contoh gambar upheapmax:
Deletion pada Min-Max
Heap
Deletion elemen terkecil:
-Ganti root dengan elemen terakhir di heap
-Hapus elemen terakhir di heap
-Downheapmin dari root
Deletion elemen terbesar:
Ganti left atau right child dari root dengan elemen terakhir
di heap.
Hapus elemen terakhir di heap
Downheapmax dari node yang diganti tadi.
Downheapmin:
Jika m adalah elemen terkecil dari child dan grandchild node sekarang maka:
Jika m adalah elemen terkecil dari child dan grandchild node sekarang maka:
-
Jika m adalah grandchild dari node sekarang maka:
o
Tukar nilai mereka
o
Jika m lebih besar dari pada parentnya maka
tukar nilai mereka
o
Lanjutkan downheapmin dari m
-
Jika madalah child dari node sekarang maka:
o
Jika m lebih kecil dari node sekarang maka tukar
nilai mereka.
Downheapmax:
Jika m adalah elemen terbesar dari child dan grandchild node
sekarang maka:
-
Jika m adalah grandchild dari node sekarang
maka:
o
Tukar nilai mereka
o
Jika m lebih kecil dari pada parentnya maka
tukar nilai mereka
o
Lanjutkan downheapmax dari m
-
Jika m adalah child dari node sekarang maka:
o
Jika m lebih besar dari node sekarang maka tukar
nilai mereka.
Berikut
adalah contoh gambar dari Downheapmax:
Tries
Tries adalah struktur data tree terurut yang digunakan untuk menyimpan array asosiatif (biasanya string)
Tries ini biasanya digunakan untuk spell checker.
Tries adalah sebuah tree dimana setiap vertex melambangkan
satu kata atau prefix.
Root dari Tries adalah karakter kosong atau (‘’)
Berikut adalah contoh gambar dari Tries:
