struktur data & algoritma - perbanyaklah pengetahuan filestruktur data & algoritma suryana...

62
Struktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR HMM AA Fasilkom UI - IKI20100/ IKI80110P AVL Tree Semester Ganjil 2009/2010

Upload: trinhcong

Post on 06-Aug-2019

232 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

Struktur Data & Algoritma

Suryana Setiawan, Ruli Manurung & Ade Azurat(acknowledgments: Denny)‏

1

Fasilkom UI

SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P

AVL Tree

Semester Ganjil – 2009/2010

Page 2: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

2SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Tujuan

Memahami variant dari Binary Search Tree yang

balanced

Page 3: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

3SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Outline

AVL Tree

Definition

Property

operations

Page 4: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

4SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Motivasi

Binary Search Tree yang tidak balance dapat membuat

seluruh operasi memiliki kompleksitas running time

O(n) pada kondisi worst case.

Page 5: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

5SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 6: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

6SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

AVL Trees

10

5

3

20

2

1 3

10

5

3

20

1

43

5

Page 7: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

7SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

AVL Trees

12

8 16

4 10

2 6

14

Page 8: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

8SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

12

8 16

4 10

2 6

14

1

Insertion pada AVL Tree

Setelah insert 1

Page 9: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

9SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 10: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

10SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Kondisi tidak balance

RP

Q

k1

k2

Q

k2

P

k1

R

Sebuah penambahan pada subtree:

P (outside) - case 1

Q (inside) - case 2

Sebuah penambahan pada subtree:

Q (inside) - case 3

R (outside) - case 4

HP=HQ=HR

Page 11: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

11SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

A

k2

B

k1

CCBA

k1

k2

Single Rotation (case 1)‏

HA=HB+1HB=HC

Page 12: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

12SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Single Rotation (case 4)‏

C

k1

B

k2

AA B C

k2

k1

HA=HBHC=HB+1

Page 13: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

13SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 14: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

14SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

C

k3

A

k1

D

B

k2

Double Rotation: Langkah

C

k3

A

k1

D

B

k2

HA=HB=HC=HD

Page 15: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

15SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

C

k3

A

k1

DB

k2

Double Rotation: Langkah

Page 16: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

16SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

C

k3

A

k1

D

B

k2

C

k3

A

k1

DB

k2

Double Rotation

HA=HB=HC=HD

Page 17: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

17SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

B

k1

D

k3

A

C

k2

B

k1

D

k3

A C

k2

Double Rotation

HA=HB=HC=HD

Page 18: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

18SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

3

Contoh

penambahan 3 pada AVL tree

11

8 20

4 16 27

8

8

11

4 20

3 16 27

Page 19: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

19SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Contoh

penambahan 5 pada AVL tree

5

11

8 20

4 16 27 8

11

5 20

4 16 27

8

Page 20: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

20SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 21: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

21SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Operasi: Remove pada AVL Tree

1. 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 22: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

22SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 23: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

23SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 55 (Kasus 1)‏

60

20 70

10 40 65 85

5 15 30 50 80 90

55

Page 24: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

24SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 55 (Kasus 1)‏

60

20 70

10 40 65 85

5 15 30 50 80 90

55

Page 25: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

25SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 50 (Kasus 2)‏

60

20 70

10 40 65 85

5 15 30 50 80 90

55

Page 26: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

26SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 50 (Kasus 2)‏

60

20 70

10 40 65 85

5 15 3050 80 90

55

Page 27: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

27SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 60 (Kasus 3)‏

60

20 70

10 40 65 85

5 15 30 50 80 90

55

prev

Page 28: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

28SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 60 (Kasus 3)‏

55

20 70

10 40 65 85

5 15 30 50 80 90

Page 29: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

29SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 55 (Kasus 3)‏

55

20 70

10 40 65 85

5 15 30 50 80 90

prev

Page 30: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

30SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 55 (Kasus 3)‏

50

20 70

10 40 65 85

5 15 30 80 90

Page 31: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

31SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 50 (Kasus 3)‏

50

20 70

10 40 65 85

5 15 30 80 90

prev

Page 32: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

32SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 50 (Kasus 3)‏

40

20 70

10 30 65 85

5 15 80 90

Page 33: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

33SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 40 (Kasus 3)‏

40

20 70

10 30 65 85

5 15 80 90

prev

Page 34: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

34SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 40 : Rebalancing

30

20 70

10 65 85

5 15 80 90

Kasus ?

Page 35: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

35SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 40: setelah rebalancing

30

7010

20 65 855

15 80 90

Single rotation is preferred!

Page 36: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

36SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 5

30

7010

20 65 855

15 80 90

Page 37: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

37SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 5

30

7010

20 65 85

15 80 90

Double rotation is required!

Page 38: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

38SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 5 (After Rotation)

30

70

1020 65 85

15

80 90

Double rotation is required!

Page 39: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

39SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 10 & 15

30

70

1020 65 85

15

80 90

Double rotation is required!

Page 40: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

40SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 10 & 15

30

7020

65 85

80 90

Single rotation is required!

Page 41: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

41SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 10 & 15

30

70

2065

85

80 90

Single rotation is required!

Page 42: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

42SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 60

30

50

2040

70

60 80

1015

5

4590

Page 43: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

43SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 60 (Setelah rotasi pertama)

30

50

2040

80

70 90

1015

5

45

Page 44: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

44SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Delete 60 (Setelah rotasi kedua)

30

5020

4080

70 90

1015

5 45

Page 45: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

45SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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-1

SH-2

H

H-1H-2

Page 46: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

46SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

AVL Tree: analisa (1)

1.3282log1.44

5/

(roughly)leastathasHheightofTree

1.6182/51

5/

3

)+(N<H

φ

AVL

)+(=φ

φF

+H

i

i

Page 47: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

47SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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 48: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

48SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Implementasi AVL Tree

Beberapa method sama atau serupa dengan Binary

Search Tree.

Perbedaan utama terdapat pada tambahan proses

balancing dengan single dan double rotation.

Perlu tidak nya dilakukan balancing perlu diperiksa

setiap kali melakukan insert dan remove.

Kita akan pelajari lebih dalam bagaimana implementasi

method insert pada AVL Tree.

Page 49: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

49SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Ide

Setiap kali melakukan insert, perlu mencek pada node

yang dilewati apakah node tersebut masih balance

atau tidak.

Proses insertion adalah top-down, dari root ke leaf.

Proses pengecekan balancing adalah bottom-up, dari

leaf ke root.

Page 50: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

50SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Algoritma insertion

1. Letakkan node baru pada posisi yang sesuai

sebagaimana pada Binary Search Tree. Proses

pencarian posisi dapat dilakukan secara rekursif.

2. Ketika kembali dari pemanggilan rekursif, lakukan

pengecekan apakah tiap node yang dilewati dari leaf

hingga kembali ke root, apakah masih balance atau

tidak.

3. Bila seluruh node yang dilewati hingga kembali ke

root masih balance. Proses selesai.

Page 51: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

51SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Algoritma insertion (lanj.)

1. Untuk setiap node yang tidak balance lakukan

balancing.

a. Bila insertion terjadi pada “outside” lakukan single

rotation

b. Bila insertion terjadi pada “inside” lakukan double

rotation.

2. Lakukan pengecekan dan balancing hingga root.

Page 52: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

52SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Diskusi?

Bagaimana menentukan insertion terjadi pada bagian

“inside” atau “outside” ?

Page 53: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

53SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudo code

public static <A extends Comparable<A>> AvlNode<A>

insert( A x, AvlNode<A> t ){

if( t == null )

t = new AvlNode<A>( x, null, null );

else if( x.compareTo( t.element ) < 0 )

{

t.left = insert( x, t.left );

if(Math.abs(height( t.left ) - height( t.right )) == 2 )

if( x.compareTo( t.left.element ) < 0 )

t = rotateWithLeftChild( t );

else

t = doubleWithLeftChild( t );

}

else if( x.compareTo( t.element ) > 0 )

{

// simetris dengan program diatas

}

return t;

}

Page 54: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

54SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Diskusi

Apakah implementasi tersebut sudah efisien?

Perhatikan pemanggilan method height !

Page 55: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

55SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudo code

public static <A extends Comparable<A>> AvlNode<A>

insert( A x, AvlNode<A> t ){

if( t == null )

t = new AvlNode<A>( x, null, null );

else if( x.compareTo( t.element ) < 0 )

{

t.left = insert( x, t.left );

if(Math.abs(height( t.left ) - height( t.right )) == 2 )

if( x.compareTo( t.left.element ) < 0 )

t = rotateWithLeftChild( t );

else

t = doubleWithLeftChild( t );

}

else if( x.compareTo( t.element ) > 0 )

{

// simetris dengan program diatas

}

return t;

}

Page 56: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

56SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudo code AvlNode

class AvlNode<A extends Comparable<A>> extends BinaryNode<A>{

// Constructors

AvlNode( A theElement ) {

this( theElement, null, null );

}

AvlNode( A theElement, AvlNode<A> lt, AvlNode<A> rt ) {

element = theElement;

left = lt;

right = rt;

height = 0;

}

public int height(){

return t.height;

}

// Friendly data; accessible by other package routines

A element; // The data in the node

AvlNode<A> left; // Left child

AvlNode<A> right; // Right child

int height; // Height

}

Page 57: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

57SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudo code

public static <A extends Comparable<A>> AvlNode<A>

insert( A x, AvlNode<A> t ){

if( t == null )

t = new AvlNode<A>( x, null, null );

else if( x.compareTo( t.element ) < 0 )

{

t.left = insert( x, t.left );

if(Math.abs(height( t.left ) - height( t.right )) == 2 )

if( x.compareTo( t.left.element ) < 0 )

t = singleRotateWithLeftChild( t );

else

t = doubleRotateWithLeftChild( t );

}

else if( x.compareTo( t.element ) > 0 )

{

// simetris dengan program diatas

}

t.height = max( height( t.left ), height( t.right ) ) + 1;

return t;

}

Page 58: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

58SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Diskusi

Apakah ada cara lain?

Hanya menyimpan nilai perbandingan saja.

• Nilai -1, menyatakan sub tree kiri lebih tinggi 1 dari sub tree kanan.

• Nilai +1, menyatakan sub tree kanan lebih tinggi 1 dari sub tree kiri

• Nilai 0, menyatakan tinggi sub tree kiri = tinggi sub tree kanan

Kapan dilakukan rotasi?

• Bila harus diletakkan ke kiri dan node tersebut sudah bernilai -1

maka dinyatakan tidak balance

• Berlaku simetris

• Lihat contoh animasi

Page 59: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

59SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudocode: Single rotasi

static <A extends Comparable<A>> AvlNode<A>

singleRotateWithLeftChild( AvlNode<A> k2 )

{

AvlNode<A> k1 = k2.left;

k2.left = k1.right;

k1.right = k2;

// update tinggi kedua node.

return k1;

}

Page 60: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

60SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

Pseudocode: Double rotasi

static <A extends Comparable<A>> AvlNode<A>

doubleRotateWithLeftChild( AvlNode<A> k3 )

{

k3.left = singleRotateWithRightChild( k3.left );

return singleRotateWithLeftChild( k3 );

}

Page 61: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

61SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

AVL Trees: Latihan

Coba simulasikan urutan proses pada sebuah AVL Tree

berikut ini

insert 10, 85, 15, 70, 20, 60, 30,

delete 15, 10,

insert 50, 65, 80,

delete 20, 60,

insert 90, 40, 5, 55

delete 70

Gambarkan kondisi akhir dari AVL Tree tersebut.

Page 62: Struktur Data & Algoritma - Perbanyaklah Pengetahuan fileStruktur Data & Algoritma Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny) 1 Fasilkom UI SUR –HMM –AA

62SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P Semester Ganjil – 2009/2010

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