binary-search-tree-avl-tree.ppt

7/22/2019 binary-search-tree-avl-tree.ppt

1/13

Binary Search Tree

(BST)

Binary Tree Sebagai Struktur File


2/13

Binary Search Tree

Struktur Binary Tree banyak digunakanuntuk membantu memecahkan persoalansuatu algoritma, contohnya untuk

memecahkan masalah organisasi file direct. Penggunaan Binary Tree sebagai suatu

struktur file yang disebut Binary Search Tree(BST).

Aturan Insert ke dalam File BST :< Node Masuk Ke Kiri> Node Masuk Ke Kanan


3/13

Contoh Insert ke

File Binary Search TreeKey : 30, 62, 69, 41, 25, 39, 14, 93

30

25 62

14 41 69

39 93


4/13

Ketidakefisienan

Binary Search TreeKey : 14, 25, 30, 39, 41, 62, 69, 93

14 2530

39

4162

69

93


5/13

AVL TREE (Adelson,

Velskii, Landis)

BST Yang Seimbang


6/13

Balance Factor

B ---> level 1

A D ---> level 2

C F ---> level 3

E ---> level 4

Subtree : Tree yang terbentuk disebelah kananatau kiri dari suatu node. (Catatan : Node tsbdisebut root subtree)

Tinggi subtree : Level node terbawah dari subtreedikurang level root subtree tsb

Balance Factor : Tinggi subtree kanan dikurangtinggi dari subtree kiri dari suatu node


7/13

AVL Tree

Binary Search Tree yang memiliki aturan setiapnode selalu memiliki balance factor 0, +1 atau -1

Maka : setiap kali key baru diinsert ke dalam file,

setiap node dilihat balance factornya Apabila ada node yang balance factornya tidak 0,

+1 atau -1 (tidak imbang) maka struktur filedilakukan transformasi :

pemutaran dan atau penggeseran Kemungkinan tidak imbang hanya 2 dan

diselesaikan dengan solusi : Rotasi Tunggal danRotasi Ganda


8/13

Kemungkinan Transformasi 1

(Rotasi Tunggal)

X

Y

A

B C

h

hh+1

NodeBaru

Rotasikiri

+1

0

0

0

h

h+1h

Y

X

A BC

h

+1

+2


9/13

X

-2

-1

Y

A

BC

h

hh+1

NodeBaru

Rotasikanan

0

0

h

h+1

Y

X

ABC

h


(Rotasi Tunggal)


10/13

h-1

C

h


(Rotasi Ganda)+1

0

0

B

h-1

NodeBaru

D

h

X

Y

ZA

h

D

h

+2X

0 Y

+2Z

A

h B

h-1

C

h

-1X

0Z

0Y

DA

h

B

h-1

C

h

1

2

3

Geser kanan (Y)

Geser kiri (X)

+2

-1

+1


11/13


(Rotasi Ganda)-2

+1

-1

B

h-1

NodeBaru

D

h

X

Y

Z

A

h

C

h

D

h

-2X

0

Y

-2Z

Ah

B

h-1

C

h

+1X

0Z

0Y

DA

h

B

h-1

C

h

1

2

3

Geser kiri (Y)

Geser kanan (X)


12/13

Transformasi Mana ?

Bila 2 node teratastandanya sama makagunakan Transformasi

1 (rotasi tunggal)

Bila 2 node teratastandanya beda maka

gunakan Transformasi2 (rotasi ganda)


13/13

CONTOH SOAL AVL-TREE

Masukkan key berikut ke dalam AVLTree :

51, 88, 92, 72, 41, 55, 35, 10

binary-search-tree-avl-tree.ppt

Documents