Topik 8 Tree

8-1

Tree merupakan suatu bentuk khusus dari graph. Di dalam tree dijamin ada path dari satu vertek ke vertek lain. Ini merupakan sifat tree yang sangat bermanfaat. Di dalam ilmu komputer, banyak sekali penerapan tree, terutama untuk memberikan gambaran logic dari suatu model data. Beberapa bahasa pemrograman telah disediakan tipe data tree, namun pada beberapa yang lain struktur data tree harus didefinisikan dari struktur data yang lebih sederhana. Pembahasan dalam bagian ini lebih diarahkan pada pengenalan termonologi tree. Juga beberapa searching pada tree akan dibahas.

8.1 Pengertian Tre

Tree, T(V,E) : merupakan graph G(V,E) yang bersifat connected (terhubungkan) dan tidak mempunyai cycle (no cycle). Sebagai ilustrasi perhatikan gambar di bawah ini :

G1 G2 G3 G4

G1 : adalah Tree

G2 : adalah bukan Tree

G3 : adalah bukan tree. Karena setiap komponennya adalah tree, maka disetut sebagai Forest.

G4 : adalah bukan tree dan bukan forest

Dalil 1 : Jika a dan b adalah dua vertek yang berbeda di dalam T=(V,E) maka dijamin ada tepat satu path yang menghubung dari vertek a ke vertek b.

Dalil2 : Jika G=(V,E) adalah graph undirected (tak berarah), maka G adalah connected (terubungkan) jika dan hanya jika G mempunyai spanning tree. Spanning tree adalah tree yang merupakan spanning graph dari graph G.

Dalil 3 : Pada sembarang tree T=(V,E) berlaku |V|=|E|+1.

Dalil 4 : Pada sembarang tree T=(V,E), jika |V|>1 maka tree tersebut akan mempunyai dua pendant vertek.

Topik 8 Tree

8-2

Dalil 5 : Lima pernyataan berikut adalah equivalen untuk suatu graph tak berarah G=(V,E) yang tidak mempunyai loop :

a. G adalah tree

b. G adalah terhubungkan, tetapi dengan menghapus salah satu edge akan menyebabkan graph tersebut menjadi tidak terhubungkan (menjadi dua subgraph yang masing-masing adalah tree)

c. G tidak mempunyai cycle dan |V|=|E|+1

d. G adalah terhubungkan dan |V|=|E|+1

e. G tidak mempunyai cycle, dan jika a, bV dengan {a,b}E, maka dengan menambahkan edge {a,b} ke dalam graph G akan menghasilkan graph baru yang tepat mempunyai satu cycle.

8.2 Rooted Tree

Rooted tree merupakan directed tree dengan sifat : hanya ada satu vertek (dan disebut sebagai root, disimbolkan dengan r) yang mempunyai incoming degree 0, id(r)=0, dan vertek-vertek lainnya mempunyai incoming degree 1, id(v)=1. Sebagai ilustrasi perhatikan tree berikut :

T1 T2 T3

T1 adalah bukan root tree, sedangkan T2 dan T3 adalah root tree (Coba anda tentukan, vertek mana yang sebagai root).

Ada beberapa istilah di dalam root tree, untuk itu perhatikan tree berikut :

a

g

b c

d e

na

j k

h

l

f

m

p o

q

i

Topik 8 Tree

8-3

Root : vertek a

Leaf/terminal : adalah vertek dengan id(v)=1 dan od(v)=0, contoh : b, j, m, n, p, dan q

Internal vertek : vertek lain selain leaf, yaitu a, c, d, f, e, g, h, i, k, l, dan o.

Level suatu vertek : panjang path dari root hingga vertek tersebut.

Level vertek a adalah 0

Level vertek g adalah 3

Level vertek q adalah 6

Dsb.

Parent (ayah) : vertek tepat di atasnya

Parent vertek c adalah a

Parent vertek k adalah h

Parent vertek n adalah i.

Dsb.

Child (anak) : vertek tepat di bawahnya

Child vertek a adalah c dan f

Child vertek h adalah k, l, dan m

Parent vertek i adalah n.

Dsb.

Ancestor : adalah vertek-vertek level atasnya yang berada dalam path dari root ke vertek tersebut.

Ancestor dari vertek i dan g adalag d, c, dan a

Ancestor dari vertek o adalah k, h, c, f, dan a

Dsb.

Descendent : adalah vertek-vertek di level bawahnya hingga ke leaf.

Descendent dari vertek g adalah vertek i, c, dan n.

Descendent dari vertek k adalah o dan q.

Dsb.

Sibling : adalah vertek-vertek yang mempunyai parent yang sama.

Vertek-vertek b dan d adalah sibling

Tinggi (height) suatu tree : adalah level tertinggi dari vertek dalam tree tersebut. Untuk tree di atas, amka tingginya adalah 6.

8.3 Binary Root Tree

Binary root tree atau binary tree (BT) adalah root tree dengan sifat : out degree, od(v), dari vertek-verteknya adalah 0, 1, atau 2. Graph pada bagian 9.2. di atas adalah bukan binary tree, sebab ada satu vertek dengan out degree 3, yaitu vertek h.

Jika out degree dari setiap vertek dalam binary tree tersebut adalah 0 atau 2 (tidak ada yang 1), maka disebut Completee Binary Tree (CBT). Dan jika tinggi dari tree adalah h, serta semua leaf yang ada mempunyai level h atau (h-1) maka binary tree tersebut disebut Balanced Binary Tree (BBT). Beberepa contoh berikut adalah binary tree :

Topik 8 Tree

8-4

T1 T2 T3 T4 T5

Untuk tree di atas :

T1, T2, T4, dan T5 adalah complete binary tree

T1, dan T5 adalah balanced binary tree

Latihan 9.1.

1. Dari yang berikut, mana yang merupakan tree ?

a. b. c.

2. Untuk suatu tree berlaku : |V|=|E|+1. Kerjakan soal-soal berikut :

a. Jika T1=(V1,E1) dan T2=(V2,E2), dan |E1|=17, serta |V2|=2|V1|, tentukan |V1|, |V2|, dan |E2|.

b. Jika F1=(V1,E1) adalah forest yang terdiri dari 7 tree, dan |E1|=40, tentukan |V1| !

c. Jika F2=(V2,E2) adalah forest dengan |V2|=62 dan |E2|=51, maka ada berapa tree yang menyusun forest tersebut ?

3. Tuliskan 3 contoh spanning tree dari graph berikut :

Topik 8 Tree

8-5

4. Mana di antara tree berikut yang merupakan rooted tree :

(i) (ii)

5. Untuk soal nomor (4), tentukan rootnya (untuk yang rooted tree).

6. Untuk rooted tree berikut :

a. Berapa tinggi dari rooted rtee tersebut ?

b. Berapa level dari vertek s ?

c. Tentukan leaf dari tree tersebut !

d. Tentukan parent dari vertek h !

e. Tentukan child dari vertek h !

f. Ada berapa internal vertek tree tersebut ?

g. Apakah vertek p dan s merupakan sibling ?

h. Tentukan ancestor dari vertek h, k , r dan v !

i. Tentukan descendant dari vertek a, c dan g !

j. Tentukan path terpanjang di mulai dari dari root!

k. Tentukan semua vertek yang ber level 4 !

l. Apakah tree tersebut merupakan binary tree ?

m. Apakah tree tersebut merupakan complete binary tree ?

n. Apakah tree tersebut merupakan balanced binary tree ?

a

b c

f g

ja

e d

i

q

h

k o l p

s t

r

u v

w