Rangkuman Akhir
Rangkuman akhir
9-juni-2020
Nama : Leander Ignacio Jose Antonius
NIM : 2301922285
Nama Dosen : Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522)
Nama Dosen : Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522)
AVL Tree
AVL atau Balanced Binary Search Tree adalah BST yang mempunyai minimal tinggi (height) sebesar log n agar bisa mempersingkat waktu dalam memasukan, mencari, dan menghapus data.
biasanya bila kita menggunakan bst dan memasukan data berurut 1 sampai 10, akan menjadi seperti gambar dibawah
dan jika kita mau memasukkan data 11, tree ini akan mencari dari root sampe data ke 10 terlebih dahulu dan baru memasukkan data 11.
di AVL Tree, kita membuat tree dalam bentuk seimbang, bagaimana cara mengetahui apakah pohon itu seimbang atau tidak?
maksimum height kanan dikurang kiri adalah 1.
lihat gambar dibawah
kita lihat dari node 10 yang merupakan root dari tree
height yang ada dikanan adalah 3
height di kiri adalah 2
height kanan kurang kiri adalah 1
jadi tidak menyalahi aturan.
lalu lihat node 6
height di kiri 6 adalah 1
di kanan adalah 1
1-1=0
tidak menyalahi aturan.
lihat node 17
di kanannya 0
di kiri ada 2
|0-2|=2
ini menyalahi aturan.
bagaimana cara membuat pohon ini seimbang?
ada 2 tipe case dalam penyeimbangan tree
case 1 :
node yang bermasalah adalah 4 karena kanannya 0 kirinya 2
|0-2|=2
dan yang membuat kelebihan adalah node 2 di kiri,
bila dilihat dari atas untuk mencapai node 4, menggunakan path kiri kiri
bila path yang digunakan untuk mencapai node yang bermasalah adalah kiri-kiri, atau kanan-kanan.
cukup menggunakan single rotation
pada kasus ini kita akan menggunakan single rotation dan membuat 3 sebagai poros
kita akan rotate 4 agar bisa seimbang
bayangkan 3 menjadi poros dan tarik 4 kesebelah kanan
balance tree nya akan menjadi seperti ini
Case 2 :
node yang bermasalah adalah 30 dan yang membuat berat sebelah kiri adalah 26
untuk mencapai 26, kita mengambil path kiri-kanan
untuk kasus path kiri-kanan atau kanan-kiri
kita menggunakan double rotation
single rotate pada poros 22
dan lakukan single rotate lagi pada poros 27
Pada AVL, kita juga bisa menghapus node
namun setelah kita menghapus sebuah node,
kita harus cek lagi apakah pohon itu sudah seimbang atau belum
bila tidak seimbang, maka kita harus menyeimbangkan lagi dengan single rotation atau double rotation.
contoh kasus :
kita akan menghapus node 60
tetapi setelah node 60 dihapus, pohonnya menjadi tidak seimbang
maka kita harus menyeimbangkan lagi pohonnya.
kita lihat yang tidak seimbang disini adalah node 55 dan yang menyebabkannya adalah node 70
untuk sampai ke node 70 ambil path kanan-kanan
maka kita pakai single rotation.
setelah diseimbangkan, ternyata masih ada yang tidak seimbang
node 50 memiliki height 2 dikanan dan 4 dikiri
|2-4|=2
maka harus diseimbangkan kembali
node yang menyebabkan berat dikiri adalah 42
untuk sampai ke 42, kita ambil path kiri-kanan
untuk kasus ini kita akan pakai double rotation
hasil setelah double rotation :
Heaps and Tries
cara memasukkan datanya adalah masukkan data dari array secara berurutan dari index 1-10
data pertamanya sebagai root, data ke 2 dan 3 sebagai left child dan right child, dan seterusnya.
cara menghitung index
x sebagai index
menghitung index parent : x/2
menghitung index left child : 2*x
menghitung index right child : (2*x)+1
misal kita mengambil node 18 yang memiliki index 4 (dari gambar di atas)
untuk menghitung index parent (node 15) : 4/2=2
untuk menghitung index left child : 4*2=8
untuk menghitung index right child : (4*2)+1=9
Min heap dan max heap
Min heap : setiap node pasti lebih kecil dari pada child node.
angka terkecil yang ada di min heap pasti ada di rootnya.
Insertion di Min heap
ada 2 cara untuk insert di min heap
cara 1 : Upheap
Masukkan node seperti biasa, lalu bandingkan dengan node di atasnya (parent) bila parent nilai nya lebih besar, tukar. Setelah ditukar lakukan hal yang sama dengan node diatasnya. Berhenti ketika node yang diatas nya sudah lebih kecil.
contoh :
cara 2 : Downheap
Masukkan node seperti biasa, mulai dari node root, bandingkan dengan left dan right child, bila lebih kecil, tukar node nya dengan node yang lebih kecil. lanjutkan terus dan berhenti bila node dibawahnya.
Deletion di Min heap :
deletion menggunakan konsep down heap.
Max heap : setiap node pasti lebih besar dari pada child node.
Max-Min heap
dalam max-min heap, max dan min bergantian pada setiap level
level ganjil memakai max heap
level genap memakai min heap
insertion di max-min heap
masukkan node seperti biasa,
bila node ada di min heap:
-jika node parent lebih kecil, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih kecil, tukar.
bila node ada di max heap:
-jika node parent lebih besar, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih besar, tukar.
Tries
Tries adalah tree yang node nya berisikan sebuah char (single character) dan root nya berisikan NULL.
contoh tries
tries di atas mengandung kata :
ALGO, API, BOM, BOS, BOSAN, dan BOR
struct trie {
char chr;
int word;
struct trie* edge[128];
} *root = 0;
root = (struct trie*)malloc(sizeof(struct trie));
root->chr = ‘’;
root->word = 0;
ini adalah structure dari tries
insert word dalam tries
#include<stdio.h>
#include<stdlib.h>
void insert(struct trie *curr, char *p) {
if ( curr->edge[*p] == 0 )
curr->edge[*p] = newnode(*p);
if ( *p == 0 ) curr->word = 1;
else insert(curr->edge[*p],p+1);
else insert(curr->edge[*p],p+1);
}
struct trie* newnode(char x) {
struct trie* node =
(struct trie*)malloc(sizeof(struct trie));
node->chr = x;
node->word = 0;
for (i = 0; i < 128; i++ )
node->edge[i] = 0;
return node;
}
int main()
{
char s[100];
insert (root,s);
return 0;
}
cari kata dalam tries
char s[100] = {“...”}; // global
void find(struct trie *curr, int x)
{
if ( curr->word == 1 )
{
s[x] = 0;
puts( s );
}
for ( i = 0; i < 128; i++ )
if ( curr->edge[i] != 0 )
{
s[x] = i;
find(curr->edge[i],x+1);
}
}
int main()
{
int i, n, okay;
struct trie *curr;
n = strlen(s);
okay = 1;
curr = root;
for(int i = 0; i < n; && okay == 1; i++)
{
if(curr->edge[s[i]] == 0) okay=50;
else curr=curr->edge[s[i]];
}
if(okay) find(curr,n);
}
Terima kasih
Terima kasih
Comments
Post a Comment