avl trees
DESCRIPTION
AVL Trees. Untuk setiap node dalam tree, ketinggian subtree di anak kiri dan subtree di anak kanan hanya berbeda maksimum 1. X. X. H. H-2. H-1. 10. 10. 5. 20. 5. 20. 43. 3. 3. 1. 2. 1. 3. AVL Trees. 5. AVL Trees. 12. 8. 16. 4. 10. 14. 2. 6. Insertion pada AVL Tree. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/1.jpg)
X X
AVL Trees• Untuk setiap node dalam tree, ketinggian
subtree di anak kiri dan subtree di anak kanan hanya berbeda maksimum 1.
H
H-1H-2
![Page 2: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/2.jpg)
AVL Trees
10
5
3
20
2
1 3
10
5
3
20
1
43
5
![Page 3: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/3.jpg)
AVL Trees
12
8 16
4 10
2 6
14
![Page 4: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/4.jpg)
12
8 16
4 10
2 6
14
1
Insertion pada AVL Tree• Setelah insert 1
![Page 5: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/5.jpg)
Insertion pada AVL Tree
• Untuk menjamin kondisi balance pada AVL tree, setelah penambahan sebuah node. jalur dari node baru tersebut hingga root di simpan dan di periksa kondisi balance pada tiap node-nya.
• Jika setelah penambahan, kondisi balance tidak terpenuhi pada node tertentu, maka lakukan salah satu rotasi berikut: – Single rotation– Double rotation
![Page 6: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/6.jpg)
Kondisi tidak balance
• Sebuah penambahan pada subtree:– P (outside) - case 1– Q (inside) - case 2
• Sebuah penambahan pada subtree:– Q (inside) - case 3– R (outside) - case 4
RP
Q
k1
k2
Q
k2
P
k1
R
HP=HQ=HR
![Page 7: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/7.jpg)
A
k2
B
k1
CCBA
k1
k2
Single Rotation (case 1)
HA=HB+1HB=HC
![Page 8: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/8.jpg)
Single Rotation (case 4)
C
k1
B
k2
AA B C
k2
k1
HA=HB
HC=HB+1
![Page 9: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/9.jpg)
Q
k2
P
k1
RR
P
Q
k1
k2
Keterbatasan Single Rotation• Single rotation tidak bisa digunakan untuk
kasus 2 dan 3 (inside case)
HQ=HP+1HP=HR
![Page 10: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/10.jpg)
C
k3
A
k1
D
B
k2
Double Rotation: Langkah
C
k3
A
k1
D
B
k2
HA=HB=HC=HD
![Page 11: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/11.jpg)
C
k3
A
k1
DB
k2
Double Rotation: Langkah
![Page 12: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/12.jpg)
C
k3
A
k1
D
B
k2
C
k3
A
k1
DB
k2
Double Rotation
HA=HB=HC=HD
![Page 13: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/13.jpg)
B
k1
D
k3
A
C
k2
B
k1
D
k3
A C
k2
Double Rotation
HA=HB=HC=HD
![Page 14: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/14.jpg)
3
Contoh• penambahan 3 pada AVL tree
11
8 20
4 16 27
8
8
11
4 20
3 16 27
![Page 15: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/15.jpg)
Contoh• penambahan 5 pada AVL tree
5
11
8 20
4 16 27 8
11
5 20
4 16 27
8
![Page 16: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/16.jpg)
AVL Trees: Latihan• Coba simulasikan penambahan pada sebuah
AVL dengan urutan penambahan:10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55
![Page 17: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/17.jpg)
Operasi: Remove pada AVL Tree1. Menghapus node pada AVL Tree sama dengan menghapus binary search
tree procedure dengan perbedaan pada penanganan kondisi tidak balance.
2. Penanganan kondisi tidak balance pada operasi menghapus node AVL tree, serupa dengan pada operasi penambahan. Mulai dari node yang diproses (dihapus) periksa seluruh node pada jalur yang menuju root (termasuk root) untuk menentukan node tidak balance yang pertama
3. Terapkan single atau double rotation untuk menyeimbangkan tree.
4. Bila Tree masih belum balance, ulangi lagi dari langkah 2.
![Page 18: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/18.jpg)
Menghapus node X pada AVL Trees
• Deletion:– Kasus 1: jika X adalah leaf, delete X– Kasus 2: jika X punya 1 child, X digantikan oleh
child tsb.– Kasus 3: jika X punya 2 child, ganti X secara rekursif
dengan predecessor-nya secara inorder• Rebalancing
![Page 19: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/19.jpg)
Delete 55 (Kasus 1)
60
20 70
10 40 65 85
5 15 30 50 80 90
55
![Page 20: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/20.jpg)
Delete 55 (Kasus 1)
60
20 70
10 40 65 85
5 15 30 50 80 90
55
![Page 21: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/21.jpg)
Delete 50 (Kasus 2)
60
20 70
10 40 65 85
5 15 30 50 80 90
55
![Page 22: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/22.jpg)
Delete 50 (Kasus 2)
60
20 70
10 40 65 85
5 15 30 50 80 90
55
![Page 23: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/23.jpg)
Delete 60 (Kasus 3)
60
20 70
10 40 65 85
5 15 30 50 80 90
55
prev
![Page 24: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/24.jpg)
Delete 60 (Kasus 3)
55
20 70
10 40 65 85
5 15 30 50 80 90
![Page 25: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/25.jpg)
Delete 55 (Kasus 3)
55
20 70
10 40 65 85
5 15 30 50 80 90
prev
![Page 26: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/26.jpg)
Delete 55 (Kasus 3)
50
20 70
10 40 65 85
5 15 30 80 90
![Page 27: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/27.jpg)
Delete 50 (Kasus 3)
50
20 70
10 40 65 85
5 15 30 80 90
prev
![Page 28: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/28.jpg)
Delete 50 (Kasus 3)
40
20 70
10 30 65 85
5 15 80 90
![Page 29: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/29.jpg)
Delete 40 (Kasus 3)
40
20 70
10 30 65 85
5 15 80 90
prev
![Page 30: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/30.jpg)
Delete 40 : Rebalancing
30
20 70
10 65 85
5 15 80 90
Kasus ?
![Page 31: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/31.jpg)
Delete 40: setelah rebalancing
30
7010
20 65 855
15 80 90
Single rotation is preferred!
![Page 32: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/32.jpg)
Jumlah node minimum pada AVL Tree
• Sebuah AVL Tree dengan tinggi H memiliki paling tidak sebanyak FH+3-1 nodes, dimana Fi elemen ke-i dari deret bilangan fibonacci.
• S0 = 1
• S1 = 2
• SH = SH-1 + SH-2 + 1
SH-1SH-2
H
H-1H-2
![Page 33: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/33.jpg)
AVL Tree: analisa (1)
328.1)2log(44.1
5/φ
)(
618.12/)5(1φ
5/φ
3H
i
NH
roughlyleastathasHheightofTreeAVL
Fi
![Page 34: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/34.jpg)
AVL Tree: analisa (2)• Tinggi sebuah AVL tree merupakan fungsi
logaritmik dari jumlah seluruh node. (ukuran AVL Tree)
• Oleh karena itu, seluruh operations pada AVL trees juga logaritmik
![Page 35: AVL Trees](https://reader033.vdokumen.com/reader033/viewer/2022061503/56813518550346895d9c6eb5/html5/thumbnails/35.jpg)
Rangkuman• Mencari elemen, menambahkan, dan
menghapus, seluruhnya memiliki kompleksitas running time O(log n) pada kondisi worst case
• Insert operation: top-down insertion dan bottom up balancing