MODUL 3 Kuliah 5, 6
-
Tree
Adalah graph tak berarah yang terhubung dan tidak memuat cycle. Suatu Tree paling sedikit mengandung satu vertex. Contoh :
Tree dgn 1 vertex (a)
Tree dgn 2 vertex (b)
Tree dgn 3 vertex (c)
Tree dgn 4 vertex (e)
Tree dgn 4 vertex (d)
Contoh 18
-
Contoh aplikasi Tree
Misalkan v = { A, B, C, D, E, F, G, H, I } adalah himpunan petinju-petinju yang sudah disusun menurut urutan bertanding merebutkan piala SEA GAMES. x dan y termasuk v akan dihubungkan oleh suatu edge jika x dan y adalah pasangan untuk bertanding, yang menang akan berpasangan dengan berikutnya, sedangkan yang kalah tidak akan bertanding lagi. Misalkan mula- mula A bertanding dengan B dan A menang, kemudian A bertanding dengan C dan A menang, berikutnya A bertanding dengan D dan A menang lagi. Akhirnya A bertanding dengan E dan E yang menang. Selanjutnya E melawan F, E
menang, kemudian E melawan G dan E tetap menang, lalu E melawan H yang dimenangkan oleh H. terakhir H harus melawan I. Maka pertandingan tinju ini dapat digambarkan oleh Tree berikut. A
F
B
B C
A
E
E
C D
G H
D H
F
I
G I
Contoh – 19
-
Leaf (pendant vertex, terminal node) Yaitu vertex dalam sebuah Tree dengan degree Satu. Pada contoh – 19, A, B, C, D, E, F, G dan I adalah leaf.
-
Branch (internal node) Adalah vertex dalam sebuah Tree dengan degree lebih dari satu. Pada contoh – 19, A, E,dan H adalah branch.
-
Teorema tentang Tree :
1. Untuk setiap pasang vertex dalam suatu Tree T ada lintasan tunggal yang menghubungkannya.
Bukti : Jelas ada lintasan yang menghubungkan setiap dua vertex sebab T connected. Sekarang ada dua vertek yang dihubungkan oleh dua lintasan, maka kedua lintasan ini akan membentuk suatu cycle dalam T, ini tidak mungkin sebab T acyclic. 2. Jia dalam suatu graph G setiap dua vertex hanya ada satu lintasan, maka graph G adalah satu Tree.
Bukti : Adanya lintasan untuk setiap vertex di G menjamin G terhubung. Misalkan G mempunyai satu sirkuit, berarti ada dua vertex a dan b sehingga ada dua lintasan yang menghubungkan a dan b, ini bertentangan dengan hipotesa, maka G tidak mempunyai sirkuit. Jadi G adalah sebuah Tree. 3. Dalam sebuah Tree dengan n vertex dan q edge, berlaku hubungan berikut: n = q + 1.
Bukti : Dibuktikan dengan induksi matematika. Pernyataan di atas benar untuk n = 1, sebab n = 1, Tree Tersebut tidak mempunyai sisi, jadi q = 0, atau n = q + 1. untuk n = 2, tree tersebut, Hanya mempunyai satu sisi, jadi q = 1 atau n = q + 1 pula. Andaikan pernyataan benar untuk tree dengan banyaknya vertex kurang dari n. Sekarang misalkan T adalah suatu tree dengan n vertex, dan a adalah suatu edge dalam tree T tersebut. Yang menghubungkan vi dan vj, pandang T – a. Karena teorema 1, maka dengan ini tidak ada lagi lintasan yang menghubungkan antara vi dan vj. Dengan demikian T akan terpisah menjadi dua komponen yang yang juga berupa tree, katakan T1 dan T2. banyaknya vertex dalam T1 misalkan adalah n dan banyaknya edge q, maka
n< n dan berlaku n =
q + 1. Sedangkan banyaknya vertex di T2 misalkan adalah n dan banyaknya edge dalam T2 adalah q , maka n< n dan berlaku n = q + 1. Sehingga
n + n = q+ q + 2
Sedangkan
n
= n+ n
Dan
q
= q + q + 1
Maka
n
=q+1
Jadi pernyataan di atas benar untuk setiap tree.
a Vi
T1
Vj
T2
4. setiap graph terhubung dengan n vertex dan n – 1 edge adalah sebuah tree.
Bukti : misalkan G adalah sebuah graph terhubung dengan n vertex dan n-1 edge. Untuk membuktikan G adalah sebuah tree tinggal dibuktikan bahwa G tidak mempunyai sirkuit. Misalkan G mempunyai suatu sirkuit elementer vi1, vi2,…,vim,vi1. Pada sirkuit ini terdapat m revtex dan m edge ( m < n ). Jadi masih sisa n – m vertex, karena g terhubung, maka paling sedikit masih ada n – m edge lagi diluar sirkuit tersebut. Yang berarti bahwa G mempunyai m + (n – m) = n vertex dan m + (n – m) = n edge, ini bertentangan dengan hipotesa. Jadi G tidak mungkin mempunyai sirkuit. Dpl. G adalah sebuah Tree.
5. graph G adalah suatu tree jika dan hanya jika G adalah terhubung minimal, yang berarti bila suatu edge di G dihilangkan, G akan menjadi tidak terhubung.
Bukti : Jika G suatu tree, maka G terhubung dan tidak mempunyai sirkuit. Misalkan G terhubung tidak minimal, berarti ada edge ei di G sehingga G – ei masih terhubung, dpl. Ei berada dalam sebuah. Sirkuit. Bertentangan dengan G adalah sebuah tree, maka G adalah terhubung minimal. Sebaliknya, jika G terhubung minimal maka G tidak mungkin mempunyai sebuah sirkuit, ini berarti bahwa G adalah sebuah tree.
6. Suatu graph G dengan n revtex dan n – 1 edge dan tedak mempunyai sirkuit adalah terhubung. Bukti :
e Vi
Vj
G1
G2
Misalkan G adalah suatu graph dengan n revtex dan n – 1 edge dan tidak mempunyai sirkuit yang tidak terhubung. Maka G terdiri dari dua komponen atau lebih, misalkan G terdiri dari
dua komponen G1 dan g2. Ambil vertex vi di G1 dan vj di g2, buat satu edge e yang menghubungkan vi dan vj. Karena G1 dan G2 adalah komponen, jadi di G tidak ada lintasan antara vi dan vj, berarti dengan menambahkan edge e tidak akan membentuk suatu sirkuit di G. dengan demikian G = G e tetap tidak mengandung sirkuit dan terhubung. Jadi G adalah suatu tree dengan n vertex dan (n – 1) + 1 edge, menurut teorema 3 hal ini tidak mungkin. Maka G harus terhubung.
- Dari keenam teorema di atas dapat disimpulkan bahwa pernyataan dibawah ekivalen :
1. Suatu graph G adalah tree jika G terhubung dan tidak mempunyai sirkuit.
2. Suatu graph G dengan n vertex adalah tree jika G terhubung dan mempunyai
n–
1 edge.
3. Suatu graph G dengan n vertex adalah tree jika G mempunyai n – 1 edge dan tidak mempunyai sirkuit.
4. Suatu graph G adalah tree jika antara setiap pasang vertex ada tepat satu lintasan di G.
5. Suatu graph G dengan adalah tree jika G terhubung minimal.
- Teore ma. Dalam suatu tree dengan dua vertex atau lebih , paling sedikit mengandung dua pendant vertex.
Bukti : Misalkan tree T mempunyai n (n > 1) vertex, maka T mempuyai n-1 edge, yang berarti bahwa T mempunyai 2 * ( n 1) degree yang dibagikan ke n vertex. Karena tidak ada vertex yang ber-degree 0, maka paling sedikit ada dua pendant vertex (leaf). Tree berarah
Suatu graph berarah dikatakan tree bila setelah arahnya diabaikan dia menjadi tree.
Rooted Tree Suatu tree di mana satu vertexnya dibedakan dengan vertex lainnya disebut rooted tree, vertex yang dibedakan tersebut disebut akar atau root. Suatu tree berarah dikatakan rooted tree berarah bila ada tepat satu vertex dengan in-degree 0. Vertex dengan in-degree 0 disebut akan atau root, sedangkan vertex dengan out-degree 0 disebut leaf (pendant vertex). Contoh :
Pe rmulaan V1 e1 V2
V3
4
e2 V4
1
13
e3
e4
V5
e6
e5 V6
7
e9 e8
e7 V7
0
V8
2
V10
8
V9
11
e10 e11 e12 e13 V12
V11
7
13
e14
8 V13
V14
V27 V21
11
e15 e16 V16
13 e30
e31
e32
7
e17 e18 e19 V18
2
8
V17
V15
8 3
V19
V20
V34
8
11
11
V32
V33
e45
1
V47
11
V24
2
V25
8
V26
11
3
11
11
V36
8
11
8
V35 e46
V46
V30
3
V45 V40
V31
V29
11
11 V23
11
V28
8
V22
11
11
3
V37
V38
11
V41
e47
11
8
V39
11
3
11
V42
V43
V44
e48
11
V48
V49
Contoh 20 Misalkan ada suatu barisan bilangan bulat di mana unsur-unsurnya tidak ada yang sama sebagai berikut: 4, 1, 13, 7, 0, 2, 8, 11, 3. Tentukan subbarisan monoton naik yang terpanjang dari barisan tersebut. Persoalan ini dapat dinyatakan dalam bentuk tree, di mana vertex-nya ( kecuali vertex permulaannya ) menyatakan bilangan tertentu dalam barisan tersebut, dan setiap lintasan dari vertex permulaan ke vertext v menyatakan suatu subbarisan monoton naik yang berakhir dengan bilangan yang dinyatakan oleh v. Tree tersebut digambarkan pada contoh 20 di atas.
3
Dari gambar di atas terlihat bahwa subbarisan-subbarisan yang ada adalah : 4, 13 4, 7, 8, 11
subbarisan terpanjang
4, 7, 11 4, 8, 11 1, 13 1, 7, 8, 11
subbarisan terpanjang
1, 7, 11 1, 2, 8, 11
sub barisan terpanjang
1, 2, 11 1, 2, 3 1, 8, 11 1, 11 13 7, 8, 11 7, 11 0, 2, 8, 11
sub barisan terpanjang
0, 2, 11 0, 2, 3 0, 8, 11 0, 11 0, 3 2, 8, 11 2, 11 2, 3 8, 11 11 3 Jarak antara 2 vertex Jarak antara 2 vertex vi dan vj di dalam suatu graph terhubung adalah panjang terkecil dari lintasan-lintasan yang ada antara vi dan vj. Dinyatakan oleh d(vi, vj) Contoh:
Pada graph contoh-21 di bawah hendak ditentukn jarak antara vertex v1 dan v2, maka dicari semua lintasan yang ada antara v1 dan v2: Lintasan-1
: a, e
dengan panjang p1 = 2
Lintasan-2
: a, c, f
dengan panjang p2 = 3
Lintasan-3
: b, c, e
dengan panjang p3 = 3
Lintasan-4
: b, f
dengan panjang p4 = 2
Lintasan-5
: b, g, h
dengan panjang p5 = 3
Lintasan-6
: b, g, i, j
dengan panjang p6 = 4
Jadi d (v1, v2) = min ( p1, p2, p3, p4, p5 ) = 2
e
V2 j
a c
h f
V1 b
i g Contoh 21
Anak, Saudara dan Bapak Dalam suatu rooted tree T vertex B disebut anak dari branch A bila ada edge yang menghubungkan A ke B dan A disebut bapak dari B. Dua vertex di T disebut bersaudara bila mereka adalah anak dari vertex yang sama. Descendent dan Ancestor Dalam suatu rooted tree berarah vertex v1 dikatakan descendant dari vertex v2 bila ada lintasan dari v2 ke v1,dan v2 dikatakan ancestor dari v1. Contoh : Pada contoh-20 : v2, v3, v4, v5, v6, v7, v8, v9, dan v10 adalah bersaudara dan semua adalah anak dari v1. v11, v12, v13 dan v14 adalah bersaudara dan semua adalah anak dari v2. v15 tidak bersaudara dengan v11 v46, v31, v12 dan v2 adalah descendant dari v1 v1, v2, v12 dan v31, adalah ancestor dari v46.
v47 bukan descendant dari v2, tapi v47 adalah descendant dari v2, tapi v47 adalah descendent dari v1. Subtree dari suatu branch sebagai root. Andaikan v1 adalah suatu branch dalam suatu rooted tree berarah T. suatu sub tree denganroot di v1 adalah T’= (V’,E’) sehingga V’ memuat v1 dan semua descendent v1 sedangkan E’ memuat sisi-sisi pada semua lintasan yang berasal dari v1.
Contoh : Pada contoh-20, rooted tree berarah T = (V,E), di mana V = v1, v2, ……,v49 dan E = e11, e2, ……., e48 terdapat subtree-subtree dengan branch tertentu sebagai root sebagai berikut : Subtree T1 = (V1, E1) V1 = v1, v11, v12, v13, v14, v31, v32, v33, v46 E1 = e10,e11, e12, e13, e30, e31, e32, e45 Subtree T2 = (V2, E2) dengan root v12 dimana V2 = v12, v31, v32, v46 E2 = e30, e31, e45 Subtree T3 = (V3, E3) dengan root v31 dimana V3 = v31, v46 E2 = e45
Subtree dari suatu branch. Subtree dari suatu branch v1 dalam suatu rooted tree adalah subtree dengan salah satu anak dari v1 sebagai root. Contoh : Pada contoh-20, subttree dari branch v4 ada 4 buah, masing- masing adalah : T1 = (V1, E1) di mana V1 = V11 dan E1 = kosong T2 = (V2, E2) di mana V2 = v12, v31, v32, v46 E2 = e30, e31, e45 T3 = (V3, E3) di mana V3 = V13, V33 E3 = e32 T4 = (V4, E4) di mana V4 = V14 dan
E4 = kosong
Ordered tree Adalah rooted tree dengan sisi-sisi yang insiden dengan masing- masing cabang diberi label bilangan bulat 1,2,….dst. Contoh : Sentence 1
2
3
Verb Subject 1
Object 2 Noun phrase 1 2
Article
1
Sentence
1
Adjective
1
Article
noun
1
1
Little
Girl
1 Wears
A
2 Noun phrase 1 2 Adjective 1 Red
noun 1 Dress
Contoh-22 m-ary tree adalah ordered tree dengan yang setiap cabangnya 1 mempunyai 1 paling banyak m anak. Bila setiap cabang mempunyai m anak maka m –ary tree tersebut. Disebut reguler m-ary tree. Binary tree Adalah tree dengan banyak vertex lebih dari dua dan mempunyai tepat satu vertex dengan degree 2 sedang yang lain dengan degree 1 atau 3. vertex dengan degree 2 disebut akar dari binary tree tersebut. Jadi binary tree adalah suatu rooted tree, tapi suatu rooted tree bukan suatu binary tree. Contoh
(a) Binary tree
(b) Bukan binary tree Contoh-23
- Sifat-sifat binary tree 1. Banyaknya vertex dalam suatu binary tree selalu ganjil Bukti : Telah diketahui bahwa dalam suatu graph banyaknya vertex dengan degree ganjil adalah genap, sedangkan dalam suatu binary tree setiap vertex ber-degree ganjil kecuali akarnya yang ber-degree 2, maka bila n adalah banyaknya vertex di binary tree T, akan berlaku n-1 genap, dengan perkataan lain n adalah ganjil.
2. Jika p adalah banyaknya leaf dalam suatu binary tree T dengan n vertex maka p = ½ (n + 1). Bukti : Banyaknya vertex di T
=n
Banyaknya vertex dengan degree 1 di T = p Banyaknya vertex dengan degree 2 di T = 1, maka : Banyaknya vertex dengan degree 3 di T = n – p – 1 Jadi banyaknya sisi dari T adalah ½ [1 * p + 2 * 1 + 3 * (n-p-1)] dan dari teorema sebelumnya diketahui bahwa banyaknya sisi dalam sebuah tree dengan n vertex adalah (n – 1) , maka diperoleh persamaan berikut ½ [1 * p + 2 * 1 + 3 * (n-p-1)] = n – 1 atau atau
p + 2 + 3n – 3p – 3 = 2n – 2 p = ½ ( n + 1)
3. Jika p adalah banyaknya leaf dalam suatu binary tree T dan q adalah banyaknya branch di T maka berlaku p = q + 1. Bukti : Sebab banyaknya vertex dengan degree 1 = p banyaknya vertex dengan degree 2 = 1 banyaknya vertex dengan degree 3 = q - 1 Jadi
banyaknya vertex di adalah
n = p + 1 + (q – 1)
Dari sifat di atas diketahui bahwa
p = ½ (n + 1)
Jadi
2p = p + 1 + (q – 1) + 1
atau
P=q+1 - Level Dalam suatu binary tree vi dikatakan mempunyai level li bila vi mempunyai jarak
dari root. Akar dari setiap binary tree berlevel 0. Contoh : Salah satu binary tree dengan 13 vertex yang berlevel 4 adalah :
Level 1 Level 2 Level 3
Level 4
Contoh-24 Pada level 0 ada 1 vertex, Pada level 1 ada 2 vertex,
Pada level 2 ada 2 vertex, Pada level 3 ada 4 vertex, dan Pada level 4 ada 4 vertex,
4. Jika banyak vertex suatu binary tree berlevel k adalah n, maka berlaku : n 2 0 2 1 2 2 ...... 2 k . Bukti : Pada suatu binary tree, berlaku : di level 0, paling banyak ada 1 vertex atau 2 0 vertex, di level 1, paling banyak ada 2 vertex atau 21 vertex, di level 2, paling banyak ada 4 vertex atau 2 2 vertex, di level k, paling banyak ada
2 k vertex.
Jadi berlaku : N 2 0 + 21 + 2 2 + 2 k . - Tinggi dari suatu binary tree adalah level maksimum 1max yang ada pada binary tree tersebut.
5. Tinggi minimum dari suatu binary tree dengan n vertex adalah min 1max [log 2 (n 1) 1] di mana [n] adalah bilangan bulat lebih besar atau sama dengan n. Bukti : Dari rumus (x - 1)( x 0 x1 x 2 ...... x n ) x n1 1, diperoleh : 2 0 + 21 + 2 2 + ………+ 2 k = ( 2 k 1 -1) / (2 – 1) = 2 k 1 -1 berdasarkan sifat di atas : 2 k 1 -1 n 2 k 1 > n + 1, maka
k + 1 > log 2 (n +1),
jadi
min 1 max = [log 2 ( n + 1) – 1]. 6. Tinggi maksimum dari suatu binary tree dengan n vertex adalah : max 1max (n 1) / 2
Bukti : Supaya tinggi binary tree dengan n vertex mencapai maksimum, maka banyaknya di setiap level harus minimum, yaitu 2, maka tinggi maksimum yang dapat dicapai oleh binary tree dengan 0 vertex adalah : max 1max (n 1) / 2 Contoh : (a) Binary tree dengan 15 vertex yang mempunyai tinggi minimum. (b) Binary tree dengan 11 vertex yang mempunyai tinggi maksimum level 1 level 1 level 2 level 3 level 4 level 5
(a)
Jadi min
Contoh 25
(b)
= [2,........] = 3 dan max = (11 - 1) / 2 = 5 - Prefix codes Andaikan kita akan menyandikan huruf- huruf sebagai barisan biner sedemikian hingga setiap huruf mempunyai kode yang tunggal. Karena banyaknya huruf ada 26, maka barisan biner dengan panjang 5 (karena ) dapat dengan tunggal menyandikan huruf- huruf tersebut. Masalah yang timbul adalah sandi yang terjadi terlalu panjang. Kita tahu bahwa huruf- huruf tersebut tidak merata frekuensi penggunaannya, misal saja huruf a dan i akan lebih sering digunakan dari pada x dan v. Maka akan lebih menghemat jika kita mengambil kebijaksanaan bahwa huruf-huruf yang sering digunakan kita sandikan dengan barisan yang lebih pendek daripada untuk huruf-huruf yang jarang dipakai. Masalah yang timbul kemudian adalah kemungkinan adanya sandi yang membingungkan penerima berita. Misal saja jika kita menyandikan a sebagai 00 dan u sebagai 01 dengan q sebagai 0001, maka bila kita mengirim sandi 0001 akan dapat berarti 'au' atau 'q'. Untuk itu kita definisikan suatu prefix code.
Prefix Code adalah himpunan barisan biner dimana tidak ada anggotanya yang merupakan prefix dari salah satu anggota yang lain. Misalnya : {000, 001, 01, 10, 11} adalah prefix code, sedangkan {1, 00, 01, 000, 0001} bukan prefix code, karena 00 adalah prefix dari 01, dan 000 adalah prefix dari 1. Suatu prefix code dapat kita peroleh dengan menggunakan binary tree. Dari suatu binary tree, kita beri label dua sisi yang insiden dari masing- masing cabang dengan 0 dan 1. Pada setiap leaf kita pasangkan barisan yaitu barisan label sisi-sisi pada lintasan yang menghubungkan root dengan leaf tersebut. Contoh : 0 0
0 0
01
10
11
Sebaliknya 000kita juga dapat 001 mengkonstruksikan suatu binary Tree dari suatu prefix Contoh 26 yang diketahui sebagai berikut. Andaikan h adalah pangjang barisan terpanjang dalam prefix code yang diketahui. Konstruksikan binary Tree regular penuh dengan tinggi h dan setiap dua sisi yang insiden pada suatu cabang kita beri label 0 dan1. selanjutnya pada setiap vertex kita tentukan setiap barisan label yaitu yang berada dalam lintasan yang menghubungkan vertex tersebut dengan root. Kita cocokan dengan prefix code yang diberikan, setiap vertex yang cocok dengan salah satu anggota dari prefix code diberi tanda, kemudian vertex-vertex yang tidak bertanda tanda beserta descendantnya juga tidak bertanda ditebang, dpl. SubTree dengan vertex itu sebagi root dihapus, maka yang tinggal adalah binary tree yang berkoresponden dengan prefix code yang diberikan. Contoh : Misalkan diketahui prefix code { 1, 01, 000, 001 }, Contoh – 27 (a) adalah binary tree regular penuh dengan tinggi 3, dan Contoh – 27 (b) adalah binary tree yang berkoresponden dengan prefix code yang dimaksud.
0
1 1
0
1
0 01
0
0
000
1
0
1
0
1
001 (a)
1
01
000
001 (b)
Contoh – 27
- Binary Search Tree Andaikan diberikan item- item yang mempunyai urutan linear <. Andaikan juga K1, K2,....., Kn adalah n item dalam daftar terurut yang kita namakan kunci. Anggap K1 < K2......< Kn. Diketahui suatu item x, masalahnya adalah melacak kunci-kunci dan menentukan apakah x akan sama dengan salah satu kunci atau apakah x berada di antara K1 dan Ki + 1 untuk suatu i. Dalam pelacakan ini akan ada 2n + 1 hasil yang mungkin yaitu : x < K1,
x = K1,
K1 < x
x = K2,
K2< x < K3,
x = K3,
. . . Kn-1 < x < Kn,
x = Kn,
x > Kn. Pada prosedur pelacakan ini akan ada beberpa pembandingan antara x dengan kunci-kunci yang diberikan di mana di setiap pembandingan akan dinyatakan apakah x sama,
dari suatu kunci. Prosedur ini dapat kita sajikan dengan suatu binary tree. Kita definisikan suatu binary search tree untuk suatu set kunci-kunci K1,K2,....,Kn sebagai binary tree dengan N cabang dan n+1 leaf. Titik-titik cabang kita tandai dengan K1....Kn
Leafnya tree ini kita namakan K0...Kn Sedemikian hingga untuk setiap titik-titik cabang Ki, sub tree kirinya hanya akan memuat vertex-vertex Kj dengan j < i sedangkan subtree kanannya memuat Kj dengan j >= i. Contoh : Binary search tree untuk kunci K1, K2, K3, dan K4 K3 K4
K1 K3
K2
K0 K1
K5
K2 Contoh 28
Prosedur pelacakan ini adalah sebagai berikut : Mula- mula membadingkan x dengan akar dari binary search treenya, Ki, maka akan ada 3 kemugkinan : x = Ki ==> selesai. x < Ki ==> bandingkan x dengan anak dari Ki yang ada di sebelah kiri Ki, x > Ki ==> bandingkan x dengan anak dari Ki yang ada disebelah kanan Ki. Prosedur ini diterusjan ke cabang-cabang erikutnya sampai x sama dengan salah satu kunci atau sampai pada satu leaf. Jika leaf yang dicapai adalah Kj, berarti x akan lebih besar dari Kj tapi lebih kecil dari Ki + 1. Jika yang dicapai adalah Ko, berarti bahwa Kx lebih kecil dari K1. Jika yang dicapai adalah leaf Kn, berarti bahwa x lebih besar dari Kn. Contoh : misalkan pada contoh-28 kuknci-kuncinya adalah sbb. : K1 = ‘AC’, K2 = ‘CF’, K3 = ‘EG’ dan K4 = ‘PP’ 1. Jika x = ‘BB’, maka (i)
bandingka ‘BB’ dengan kunci K3, yaitu ‘EG’
(ii)
‘BB’ < ‘EG’, maka bandingkan ‘BB’ dengan K1, yaitu ‘AC’
(iii)
‘BB’ > ‘AC’, maka bandingkan ‘BB’ dengan K2, yaitu ‘CF’
(iv)
‘BB’ < ‘CF’, maka bandingkan dengan K1, yang merupakan suatu leaf,
jadi K1 < x
2. Jika x =’AB’, maka (i)
bandingkan ‘AB’ dengan kunci K3, yaitu ‘EG’
(ii)
‘AB’ < ‘EG’, maka bandingkan ‘AB’ dengan K1, yaitu ‘AC’
(iii)
‘AB’ < ‘AC’, maka bandingkan ‘AB’ dengan K0, yang merupakan suatu leaf,
jadi x < K1 atau ‘AB’ < ‘AC’.
3. Jika x =’ST’, maka (i)
bandingkan ‘ST’ dengan kunci K3, yaitu ‘EG’
(ii)
‘ST’ > ‘EG’, maka bandingkan ‘ST’ dengan K4, yaitu ‘PP’’
(iii)
‘ST’ < ‘PP’, maka bandingkan ‘ST’ dengan K4, yang merupakan suatu leaf,
jadi x < K1 atau ‘ST’ > ‘PP’.
-
Balanced binary tree Suatu binary tree dngan n leaf disebut balanced binary tree jika : (a) n = 2m mengakibatkan d = m, (b) 2m < n < 2m+1 mengakibatkan d = m atau d = m + 1,
di mana m = bilangan bulat nonnegatif dan d = panjang lintasan dari root ke leaf.
Contoh :
(a)
(b)
(c)
(d) Contoh-29
Contoh-29 (a) adalah balanced binary tree, sebab n =4 m= 2 panjang lintasan dari root ke setiap leaf adalah d = n maka d = m.
Contoh-29 (b) juga suatu balanced binary tree, sebab n =5 m= 2 panjang lintasan dari root ke leaf adalah d yang sama dengan 2 atau 3, maka d = m atau d = m +1,
Contoh –29 (c) bukan suatu balanced binary tree, sebab n =5 m= 2 Sedangkan panjang lintasan dari root ke leaf adalah d yang sama dengan 1 atau 2 atau 4, maka d = m atau d = m + 1 tidak selalu dipenuhi.
Contoh-29 (d) juga bukan suatu balanced binary tree, sebab n =5 m= 2 Sedangkan panjang lintasan dari root ke leaf adalah yang sama dengan 1 atau 3, maka d = m atau d = m + 1 tidak selalu dipenuhi.
