DIKTATKULIAHALGORITMAdanSTRUKTURDATAII TREE

V3/20092010 1

Pertemuan14Waktu :135menit

TujuanPembelajaran :Mahasiswamampumenjelaskanteknikpemrograman

menggunakanTree.

SubstansiMateri :BinarySearchTree,AVLTree

TabulasiKegiatanPerkuliahan

NoTahapKegiatan

KegiatanPengajarKegiatanMahasiswa

Media&Alat Waktu

1 Pendahuluan 1. Membukapertemuan2. Mengulangmateripertemuan

sebelumnya

MenyimakBertanya

PapanTulis 20Menit

2 PenyajianMateri

1. BinarySearchTree2. AVLTree

MenyimakBertanyaMenjawabPertanyaan

PapanTulis 80Menit

3 Penutup 1. Menyimpulkanmateripertemuan2. Memberikantugaskecil3. Menutuppertemuan

Menyimak Papantulis 35Menit

BinarySearchTree

Binary Search Tree adalah Binary Tree dengan sifat bahwa semua left child harus lebih

kecildaripadarightchilddanparentnya.Jugasemuarightchildharuslebihbesardarileft

childsertaparentnya.Binarysearchtreedibuatuntukmengatasikelemahanpadabinary

tree biasa, yaitu kesulitan dalammelakukan searching / pencarian node tertentu dalam

binarytree.Contohbinarysearchtreeumumadalah:

MATERIKULIAH

Padadas

kecualip

In

y

U

p

la

su

D

m

AVLTree

Adalahb

subtree

tree. De

disederh

Selain a

memilik

sehinga

sarnyaope

padaoperas

nsert

angtepat.

Update

adaposisi

agi, maka h

upayatetap

Delete

mempengaru

e

binary sear

kananmak

engan avl

hanakan

vl tree ter

i perbedaa

avltreeada

AL

Gamba

rasidalam

siinsert,up

:PadaBin

: Seperti

node terseb

harus dilaku

pmenjadiBi

: Seperti

uhistruktur

ch tree yan

simaladala

tree wak

dapat pula

n level ant

alahheightb

3

LGORITMAd

ar2.Binary

BinarySea

datedande

narySearch

pada Binar

but, sehingg

ukan perub

inarySearch

halnya upd

rdaritreet

ngmemiliki

ah1.Avltre

ktu pencar

height bal

tara subtre

balanced1t

10

5

7

DIKTAdanSTRUKTU

SearchTree

rchTreead

elete.

hTree, inse

ry Tree bia

gamenyeba

bahan pada

hTreekem

date, delete

ersebut.

i perbedaan

eemunculu

rian dan b

lanced n tr

ee kiri dan

tree

18

14

17

ATKULIAHURDATAII

esecaraum

dalahsama

rtdilakuka

asa, namun

abkanTree

a tree deng

bali.

dalam bin

n tinggi /lev

untukmeny

bentuk tree

ree , yakni

n subtree

23

21 33

40

V3/200

mum

denganBin

nsetelahd

n jika upda

bukanBina

gan cara m

nary search

vel antara s

yeimbangka

e dapat di

binary sea

kanan mak

3

0

TREE

092010 2

naryTreeb

itemukanlo

ate berpeng

arySearch

melakukan r

tree juga t

subtree kiri

anbinaryse

persingkat

arch tree

ksimal adal

biasa,

okasi

garuh

Tree

rotasi

turut

i dan

earch

dan

yang

ah n

Untukm

+

0

sa

ContohA

ContohO

Keadaan

Inse

mempermud

(tandaminu

(tandaplus

(nol):digu

ama.

AVLTree

OperasiIns

nAVLTreem

ert(5)

AL

4

40

12

12

5

dahmenyei

us):diguna

s):digunaka

unakanapab

sertpadaA

mulamula

0

0

LGORITMAd

12

13

5

78

8

79

0

40

2

mbangkant

akanapabila

anapabilas

bilasubtree

AVLTree

a

0

0

DIKTAdanSTRUKTU

20

16

18

81

99

78

81

79

tree,makad

asubtreeki

subtreekan

ekiridansu

0

0

0

0

0

0

0

ATKULIAHURDATAII

33

44

26

99

digunakans

irilebihpan

nanlebihpa

ubtreekanan

0

0

0

0

0

0

V3/200

67

89

symbolsim

njangdaris

anjangdaris

nmempuny

+

0

0

0

TREE

092010 3

bolbantu.

subtreekan

subtreekiri

yaiheightya

0

BukanAVLT

an

i

ang

Tree

Supaya

menjadiAV

AL

5

5

VLTreeper

LGORITMAd

12

40

rludilakuka

0

0

DIKTAdanSTRUKTU

78

81

79

anSingleR

0

00

ATKULIAHURDATAII

1

99

Rotation

0

0

V3/200

0

TREE

092010 4

AVLTree