BEBERAPA SIFAT JARAK ROTASI PADA POHON BINER TERURUT DAN TERORIENTASI

JTRISTE, Vol.1, No.1, Februari 2014, pp. 28~40 ISSN: 2355-3677

BEBERAPA SIFAT JARAK ROTASI PADA POHON BINER TERURUT DAN TERORIENTASI Oleh: Hasniati STMIK KHARISMA Makassar [email protected]

Abstrak Andaikan Bn adalah himpunan struktur data pohon biner dengan n simpul dalam (internal nodes) yang mempunyai akar. Pada setiap pohon T  Bn, didefinisikan urutan dari semua simpul dengan menggunakan preorder traversal. Kemudian orientasi dari pohon biner didefinisikan melalui konsep rotasi. Konsep rotasi ini menentukan suatu relasi terurut parsial dalam Bn, sedemikian sehingga terhadap relasi ini, kami tunjukkan bahwa Bn merupakan sebuah kisi-kisi (lattice). Lebih lanjut dari konsep rotasi juga diturunkan konsep jarak rotasi antara dua pohon dalam Bn. Terhadap konsep jarak ini, kami tunjukkan pula bahwa Bn merupakan ruang metrik. Kata-kata kunci: Pohon biner berakar-terorientasi-terurut, rotasi, ruang metrik, kisi-kisi (lattice) Abstract Let Bn be the set of binary trees with n internal-node and a root. The order of a tree T  Bn is defined by using pre-order traversal and its orientation is defined using the notion of rotation. This notion of rotation determines a partial order relation in Bn. Hence, Bn is a lattice. The same notion also shows the way to define a distance between a pair of trees in Bn. With respect to this distance, Bn is a metric space. Key words: rooted-ordered-oriented binary tree, rotation, lattice.

A. PENDAHULUAN Salah satu bentuk khusus struktur data dari graf adalah struktur data pohon. Penerapan konsep pohon dalam kajian ilmu komputer sangatlah penting khususnya dalam masalah pencarian (searching) dan pengurutan (sorting) data yang mampu menghasilkan kompleksitas algoritma yang sangat efisien. Konsep struktur data pohon tentu saja digunakan dalam merancang algoritma pencarian solusi untuk metode-metode blind search atau uniformed search. Dengan struktur pohon, algoritma mampu memberikan kompleksitas dengan batas asimptotik terhadap fungsi logaritmik. Pada aplikasi pohon, simpul utama pohon dinyatakan sebagai akar pohon. Pohon bersama akarnya menghasilkan graf berarah yang disebut pohon berakar. Simpul pada pohon berakar yang bercabang disebut simpul-dalam (internal node) sedangkan yang tidak bercabang disebut simpul-luar (external node) atau daun (leaf). Sebuah pohon berakar terurut merupakan pohon berakar dimana cabang-cabang dari setiap simpul-dalam diurutkan dari kiri ke kanan. Pohon yang setiap simpul-dalamnya paling banyak berderajat 3 disebut pohon biner [5].

Received May 9th, 2010; Revised August 3rd, 2010; Accepted August 16th, 2010

JTRISTE

ISSN: 2355-3677

 29

Menghitung ‘jarak’ antara dua pohon biner dengan banyak simpul yang sama sebagai cara membandingkan dua struktur pohon biner, diwujudkan dengan cara menghitung banyaknya pemakaian minimum dari ‘rotasi’ yang dapat terjadi ketika mentransformasikan suatu pohon biner kedalam pohon biner yang lain. Pada jurnal ini, kami tunjukkan bahwa konsep rotasi pohon biner yang didefinisikan membentuk struktur lattice (kisi-kisi) dan sekaligus ruang metrik pada himpunan pohon-pohon biner. Dengan menggunakan konsep rotasi, jarak antara dua pohon biner dapat didefinisikan [3]. Konsep jarak pada himpunan pohon-pohon biner yang dimaksud adalah konsep jarak antara dua pohon biner yang ‘sejenis’ dibatasi hanya pada kumpulan pohon dengan sifat berakar, terurut, terorientasi, dan memiliki simpul yang sama banyak.. Konsep ini didefinisikan berdasarkan konsep transformasi dari bentuk satu pohon biner ke bentuk pohon biner yang lain sedangkan konsep transformasi sendiri didefinisikan dengan menggunakan konsep rotasi pada sebuah pohon biner. Dalam mentransformasi suatu pohon biner ke pohon biner lain, dapat dipelajari sifat-sifat dan struktur khusus dari suatu kumpulan pohon biner.

B. POHON BINER TERURUT DAN TERORIENTASI Secara formal, suatu graf tak berarah G adalah pasangan (V(G),E(G)) dengan V(G) adalah himpunan berhingga yang unsur-unsurnya disebut simpul (vertex) dan E(G) adalah himpunan pasangan-pasangan tak berurut dari unsur-unsur V(G) yang berbeda, yang disebut sisi (edge) [5].

Definisi 2.1: [5] Pohon dengan n simpul adalah graf tak-berarah terhubung yang tidak memuat siklus.

Sebuah pohon berakar disebut pohon ari-m (m-ary) jika setiap simpul memiliki paling banyak (m+1) derajat. Jika suatu pohon memiliki lebih dari satu simpul, simpul yang berderajat satu disebut simpul-luar (external node) sedangkan simpul yang berderajat lebih dari satu disebut simpul-dalam (internal node). Suatu pohon disebut pohon ari-m penuh (full m-ary) jika setiap simpul-dalamnya mempunyai tepat m cabang. Sebuah pohon ari-m dengan m = 3 disebut pohon triner sedangkan bila m = 2 disebut pohon biner. Sebuah pohon berakar terurut merupakan pohon berakar dimana cabang-cabang dari setiap simpul-dalam mempunyai urutan. Pohon berakar terurut digambar sedemikian rupa sehingga setiap cabang dari simpul-dalam diurutkan dari kiri ke kanan [5].

Title of manuscript is short and clear, implies research results (First Author)

30 

ISSN: 2355-3677

Sebuah himpunan B dari pohon biner (berakar, terurut, dan terorientasi) secara rekursif dapat didefinisikan sebagai:

dimana  adalah simpul-dalam dan  adalah simpul-luar. |T| dinotasikan sebagai banyaknya ~

simpul dalam. Sehingga suatu bobot T dari sebuah pohon T adalah banyaknya simpul-luar dari ~

T yaitu T = |T| + 1. Misalkan Bn adalah himpunan pohon biner dengan simpul-dalam n (yaitu n + 1 simpul-luar). Suatu simpul-luar dari sebuah pohon T diberi nomor oleh sebuah pre-order traversal dari T [3].

Definisi 2.2: [4] Diberikan T ϵ Bn, barisan bobot dari T adalah suatu barisan bilangan bulat wT = (wT(1), wT(2), ..., wT(n))

(1)

dimana wT(i) adalah bobot dari subpohon terbesar T dengan simpul-luar terakhir merupakan simpul-luar i pada T. Contoh 1: Jika diberikan pohon T seperti pada Gambar 2.1, maka wT=(1,2,1,1,5,1,1,3).

T = 9

1

2

6

3

4

5

7

8

Gambar 1. Pohon biner T. Jika simpul-luar i adalah simpul-luar pertama (daun sebelah kiri) dari sebuah subpohon pada T maka wT(i)= 1 dan jika simpul-luar i adalah simpul-luar terakhir dari sebuah subpohon pada T maka wT(i) ≥ 2. Untuk setiap i berlaku 1 ≤ wT(i) ≤ i [4].

JTRISTE Vol. 1, No. 1, 2014

JTRISTE

 31

ISSN: 2355-3677

C. ROTASI POHON BINER Dalam melakukan rotasi pada pohon biner menjadi pohon biner lain, kita harus tetap memperhatikan sifat dari pohon biner itu sendiri. Ada dua jenis rotasi yaitu: rotasi kiri dan rotasi kanan. Definisi 3.1: [3] Rotasi kiri

u pada simpul-dalam u pada Bn didefinisikan sebagai berikut: Untuk setiap pohon

T1, T2 ϵ Bn, T1

u T2 jika dan hanya jika diantara simpul-luar i dan j, subpohon 3.1 (a)

berada dalam T1, dan subpohon 3.1 (b) berada dalam T2, dimana T, T’, T” adalah subpohon dari T1 dan T2.

u

v u

v T

T”

j

i T’

T

T”

T’

i

j a (a)

(b)

Gambar 2. Subpohon dari pohon T1 dan T2.

1  v melambangkan rotasi kanan pada simpul-dalam v. Sama saja dengan definisi 3.1

tetapi

kedua

bentuk

subpohon

dipertukarkan.

Rotasi

mentransformasi pohon biner ke dirinya sendiri. Misalkan refleksif transitif dari

identitas

adalah

rotasi

yang

*

  dinotasikan sebagai klosur

u [3].

Ini berarti, untuk setiap pohon biner T berlaku T T3, perdefinisi berlaku T1

*   T. Lebih jauh jika T1  T2 dan T2 

* * * T2, T2  T3, dan T1  T3.`    

Suatu relasi pada A adalah sebuah subhimpunan R  A x A. Pernyataan (a, b)  R lebih sering ditulis sebagai aRb. Misalkan A adalah sebuah himpunan dan R adalah relasi pada himpunan A. Jika a ϵ A maka klosur refleksif dari R adalah relasi R ditambah semua relasi berbentuk aRa. Dengan kata lain, klosur refleksif dari R adalah relasi R’ = R  ∆, dimana ∆ = { aRa | a ϵ A}. Misalkan R adalah sebuah relasi pada himpunan A. Jika aRb  R dan bRc  R, maka belum tentu aRc  R sehingga R belum tentu transitif. Tetapi jika semua bentuk aRc


32 

ISSN: 2355-3677

ditambahkan sedemikian sehingga terbentuklah sebuah relasi baru R* yang disebut klosur transitif dari relasi R. Secara formal, R* = R   dimana  = {aRc | terdapat b  A yang memenuhi aRb dan bRc}. Untuk sembarang relasi R, klosur refleksif transitif dari R adalah relasi R  ∆  . Dalam setiap graf berarah sederhana, jika (a, b) menyatakan keberadaan sebuah lintasan dari simpul a ke simpul b, maka himpunan lintasan-lintasan (a, b) membentuk relasi transitif (tetapi tidak refleksif, karena lintasan dari a ke dirinya sendiri, loop pada a, tidak diperbolehkan) [5].

D. KISI-KISI Definisi 4.1: (Rosen, 1998) Sebuah relasi R dalam suatu himpunan S disebut relasi urutan parsial jika relasi tersebut bersifat: a. refleksif, yaitu untuk setiap x  S berlaku x R x. b. antisimetri, yaitu untuk setiap x, y  S berlaku implikasi xRy c.



yRx



x = y.

transitif, yaitu untuk setiap x, y, z  S berlaku implikasi xRy



yRz



x R z.

Himpunan S dengan relasi terurut parsial R yang didefinisikan dalam S seperti di atas disebut himpunan terurut parsial atau disingkat poset (partially ordered set).

Suatu unsur x dalam poset S disebut batas bawah [atas] dari suatu himpunan A  S jika untuk setiap a  A berlaku x R a [a R x]. Suatu batas bawah [atas] x  S dari himpunan A disebut batas bawah terbesar [batas atas terkecil] dari himpunan A  S, ditulis x = inf A [ x = sup A] jika untuk setiap batas bawah [atas] x’ dari A berlaku x’  x [x  x’]. Sebuah himpunan terurut parsial dimana setiap pasangan unsur-unsur di dalamnya mempunyai batas atas terkecil dan sekaligus memiliki batas bawah terbesar disebut kisi-kisi (lattice) (Rosen, 1998). E. JARAK ROTASI Sebelum membahas jarak rotasi, terlebih dahulu akan dijelaskan apa yang dimaksud dengan ruang metrik. Metrik didefinisikan sebagai berikut.


JTRISTE

ISSN: 2355-3677

 33

Definisi 5.1: [2] Misalkan X adalah suatu himpunan. Suatu metrik d pada X adalah suatu fungsi bernilai real yang terdefinisi pada X  X, yaitu d: X  X  , sedemikian sehingga untuk setiap x, y, z  X berlaku 1) d(x, y)  0. 2) d(x, y) = 0 jika dan hanya jika x = y. 3) d(x, y) = d(y, x). 4) d(x, y)  d(x, z) + d(z, y).

Suatu ruang metrik adalah pasangan (X, d) dengan X adalah himpunan dan

d adalah sebuah

metrik yang terdefinisi pada X  X. d biasa disebut fungsi jarak pada X [2]. Jarak rotasi pada setiap dua pohon biner dengan jumlah simpul yang sama adalah banyaknya rotasi yang digunakan untuk mentransformasi suatu pohon biner ke pohon biner lain. Dengan jarak tersebut, akan mengubah himpunan pohon-pohon biner menjadi sebuah ruang metrik [6].

Definisi 5.2: [3] Diberikan dua buah pohon T, T’ ϵ Bn, jarak rotasi antara T dan T’, dinotasikan d(T, T’) adalah banyaknya pemakaian minimum rotasi kiri pada suatu simpul u ( u ) dan minimum rotasi 1

kanan pada suatu simpul v ( v ) yang akan mentransformasi T menjadi T’. Penggunaan rotasi identitas tidak dihitung.

Jadi d adalah sebuah fungsi d: Bn  Bn  R bernilai tak negatif dengan daerah asal Bn  Bn. Untuk selanjutnya cukup digunakan notasi ‘Bn’ untuk merujuk pada himpunan (Bn, d) yang dilengkapi metrik d.

F. BEBERAPA SIFAT JARAK ROTASI Jarak rotasi d, akan mengubah himpunan pohon-pohon biner menjadi sebuah ruang metrik. Seperti yang diberikan pada teorema berikut. Teorema 6.1: [1] (Bn,, d) adalah sebuah ruang metrik untuk setiap n.


34 

ISSN: 2355-3677

Andaikan T dan T’ adalah dua pohon biner dari himpunan pohon biner dengan n simpuldalam. Batas atas dari jarak rotasi antara T dan T’ adalah 2n – 2 seperti yang diberikan pada teorema berikut. Teorema 6.2: [1] Misalkan T, T’ ϵ Bn, dimana n ≥ 1, maka untuk setiap T, T’ ϵ Bn berlaku: 0 ≤ d(T, T’) ≤ 2n – 2

(2)

Lemma 6.3: [4] Jika |T’| ≥ 1 dan |T”| ≥ 1, maka kita dapat menghitung barisan bobot dari perkalian (product)

T =

T’

T”

dengan menggunakan barisan bobot dari pohon T’ dan T”: ~

wT = (wT’(1), wT’(2), ..., wT’(|T’|), T ' , wT”(1), wT”(2), ..., wT”( |T”|) )

(3)

Bukti. Diketahui |T’| ≥ 1 dan |T”| ≥ 1, dengan |T| = |T’| + |T”| + 1. Menurut definisi 2.2, barisan bobot dari pohon T’ dan T” secara berurutan adalah wT’ = (wT’(1), wT’(2), , wT’(|T’|)) dan wT” = (wT”(1), wT”(2), , wT”(|T”|)) Jelas bahwa untuk setiap i  [1, |T’| ]; wT(i) = wT’(i) dan untuk setiap j  [1, |T”| ]; wT(|T’| +1 + j) = wT”(j). Selanjutnya tinggal dihitung wT(|T’| +1), yaitu bobot dari subpohon terbesar dari T yang simpul-luar terakhirnya |T’| +1. Subpohon dari T yang dimaksud adalah T’. Dalam pohon T, bobot simpul ini tidak masuk dalam barisan bobot pohon T’. Menurut definisi, bobot pohon T’ ~

(sebagai subpohon dari T) adalah banyaknya simpul-luar dari pohon T’ yaitu ~

Jadi wT(|T’| +1) =

T ' . Disimpulkan barisan bobot dari pohon T adalah:

wT = (wT(1), wT(2), , wT(|T’|), wT(|T’| + 1), wT(|T’| + 2), wT(|T’| + 3), , wT (|T’| + |T”| + 1)) ~

= (wT’(1), wT’(2), , wT’(|T’|),


T ' , wT”(1), wT”(2), , wT”(|T”|)). 

T ' = |T’| + 1.

JTRISTE

ISSN: 2355-3677

 35

Teorema 6.4: [4] Sebuah barisan bilangan bulat wT = (wT(1), wT(2), ..., wT(|T|)) adalah barisan bobot dari suatu pohon biner T dengan |T| = n simpul-dalam jika dan hanya jika untuk setiap i  [1, n] berlaku: a. 1 ≤ wT(i) ≤ i, dan b. untuk setiap i’ ϵ [i – wT(i) + 1, i] berlaku i – wT(i) ≤ i‘ – wT(i’). Bukti. Syarat perlu (atau bukti ke kanan) diberikan sebagai berikut. Diketahui (wT(1),wT(2), ..., wT(n)) adalah barisan bobot pohon T. Akan dibuktikan untuk setiap i dengan 1  i  n berlaku: a.

1 ≤ wT(i) ≤ i, dan

b.

untuk setiap i’ ϵ [i – wT(i) + 1, i] berlaku i – wT(i) ≤ i‘ – wT(i’).

Kasus |T| = 1 trivial. Kasus |T| = n > 1 Anggap kedua pernyataan a dan b benar untuk setiap pohon T dengan | T | < n. Akan dibuktikan kedua pernyataan a dan b benar untuk | T | = n. Karena |T| > 1, pohon T merupakan hasil kali (product) dua pohon T’ dan T” dengan |T’| = n’  1 atau |T”| = n”  1. Ini berarti n = n’ + n” + 1 sehingga menurut Lemma 6.3. wT = (wT’(1), wT’(2), ..., wT’(n’), n’ + 1, wT”(1), wT”(2), ..., wT”(n”) ) Menurut hipotesis induksi, pernyataan a dan b berlaku untuk kedua pohon T’ dan T”. Akan dibuktikan, pernyataan berlaku pada pohon T dengan membuktikan pernyataan a dan b berlaku untuk setiap i = 1, 2, ..., n’, n’ + 1, ..., n’ + n” + 1. Kedua pernyataan berlaku untuk pohon T’ dengan |T’|  1 artinya untuk setiap i = 1, 2, ..., n’ berlaku: a. 1  wT’(i)  i, dan b. apabila i’ ϵ [i – wT’(i) + 1, i] maka i  wT’(i)  i’  wT’(i’). Tetapi untuk setiap i = 1, 2, ..., n’, wT’(i) = wT(i). Jadi pernyataan a dan b berlaku untuk pohon T apabila i = 1, 2, ..., n’. Mengingat untuk setiap i = 1, 2, ..., n”, wT”(i) = wT(n’ + i + 1), maka berlakunya kedua pernyataan a dan b untuk pohon T” dengan |T”|  1 harus diartikan bahwa untuk setiap i = n’ + 2, n’ + 3, ..., n’ + n” + 1 berlaku: a. 1  n’ + 2  wT(i)  i, dan b. apabila i’ ϵ [i – wT(i) + 1, i] maka i  wT(i)  i’  wT(i’). Ini berarti, kedua pernyataan a dan b untuk i = n’ + 2, n’ + 3, ..., n’ + n” + 1 berlaku pada pohon T. Tinggal dibuktikan kebenaran pernyataan a dan b untuk i = n’ + 1. Karena n’  1, maka wT (i) = wT(n’ + 1) = n’ + 1 = i adalah bobot dari T’ sebagai subpohon kiri dari T (yang merupakan subpohon terbesar dengan i = n’ + 1 merupakan simpulluar terakhir). Otomatis a dan b terbukti secara trivial. Sebaliknya, jika pernyataan a dan b benar maka sebuah pohon biner dengan n simpul-dalam mudah dikonstruksi. Title of manuscript is short and clear, implies research results (First Author)

36 

ISSN: 2355-3677

Lemma 6.5: Jika terdapat simpul-luar i dan j dari suatu pohon T dengan i = j  wT(j) + 1, maka terdapat suatu subpohon dengan simpul-luar pertama i dan simpul-luar terakhir j. Barisan bobot dari pohon biner T tidak akan melebihi barisan bobot dari suatu pohon biner T’ yang merupakan rotasi dari pohon T. Hal tersebut berdasarkan teorema berikut.

Teorema 6.6: [4] Misalkan T, T’  Bn . T

   T’ jika dan hanya jika untuk setiap i  [1, n], berlaku wT(i) 

wT’(i). Bukti. Dengan induksi pada n, dibuktikan syarat perlunya. Jika n = 1, selalu didapat i = 1 sehingga otomatis wT(i) = wT(1) = 1 = wT’(i) = wT’(i). Anggap teorema benar untuk setiap pasang pohon S, S’ ϵ Bn. Akan dibuktikan teorema benar untuk setiap pasang pohon T, T’ ϵ Bn+1. Misalkan T, T’ ϵ Bn+1. Hapus dua simpul-luar ke-k dan ke-(k + 1) dari pohon T yang merupakan cabang kiri dan kanan dari satu simpul-dalam u dari T. Berdasarkan definisi rotasi (Definisi 3.1), bisa disimpulkan simpul-luar ke-k dan ke-(k + 1) dari pohon T’ juga merupakan cabang kiri dan cabang kanan dari sebuah simpul-dalam u’ dari T’. Dengan demikian, terbentuk dua pohon S, S’ ϵ Bn yang simpul-luar ke-knya masing-masing merupakan simpul-dalam u dari T dan u’ dari T’. Jelas jika 0 ≤ i < k, maka wS(i) = wT(i)  wT’(i) = wS’(i). Selanjutnya, wT(k)= 1 = wT’(k) sedangkan wT(k + 1)  1 = wS(k) ≤ wS’(k) = wT’(k + 1)1 sehingga wT(k + 1) ≤ wT’(k + 1). Akhirnya, untuk setiap k + 2 ≤ i < n+1, wT(i) = wS(i  1)  wS’(i  1) = wT’(i) dan untuk i = n + 1, wT(i) = wT’(i). Untuk membuktikan syarat cukupnya, anggap wT  wT’ (wT(i)  wT’(i), untuk setiap i) dan T  T’. Misalkan i bilangan bulat terkecil sedemikian sehingga wT(i) < wT’(i). Menurut definisi 2.2, 1 ≤ wT’(i) ≤ i. Karena wT(i) < wT’(i) maka wT(i) < wT’(i) ≤ i. Akibatnya wT(i) < i. Misalkan j = i – wT(i) +1 dan k = j – wT(j – 1) . Maka menurut lemma 6.5 terdapat di dalam pohon T, yaitu sebuah subpohon T1 yang menerima k sebagai simpul-luar pertama dan j – 1 sebagai simpulluar terakhir, sedangkan subpohon T2 menerima j sebagai simpul-luar pertama dan i sebagai simpul-luar terakhir. T memuat subpohon yang bentuknya seperti pada gambar 4 (a) dimana p ≥ 1, dengan menggunakan pemakaian rotasi kiri tunggal bentuknya seperti pada gambar 4 (b) dari pohon T1.


u menjadi subpohon yang

JTRISTE

 37

ISSN: 2355-3677

v u

u v

T1

T1 p p–1 T2 T2 (a)

(b)

Gambar 3. Subpohon dari pohon T dan T1.

Misalkan l bilangan bulat terbesar sedemikian sehingga j = l - wT(l) +1. Artinya, l adalah simpul-luar terakhir dari subpohon terbesar dari T yang simpul-luar pertamanya adalah j. Karena i adalah simpul-luar suatu subpohon (belum tentu terbesar) yang simpul-luar terakhirnya j, diperoleh i ≤ l. Perhatikan, sebelum rotasi, kedua simpul-luar k dan j  1 berada di luar subpohon terbesar ini. Setelah rotasi, barisan bobot dari T1 sama dengan barisan bobot dari

T kecuali pada simpul-

luar l sebab wT(l) = l – j + 1 < Jadi setelah rotasi

wT 1 (l ) = l – k + 1.

u , ada kenaikan bobot simpul-luar l sebesar j  k. Apabila proses

dilanjutkan sampai terbentuk pohon T’, ada penambahan bobot paling sedikit sebesar j  k. Ini berarti subpohon terbesar dari T yang simpul-luar terakhirnya l setelah dikenai membesar. Setelah dikenakan

  

 , paling sedikit satu simpul-luar j  1 masuk kedalam  

subpohon terbesar yang simpul-luar terakhirnya adalah l. Menurut definisi i, untuk setiap simpul-luar i’ < i berlaku wT(i’) = wT’(i’). Karena, j  1 < i, berlaku wT(j  1) = wT’(j  1) = j  k. Jadi bobot subpohon terbesar dari T ’ yang simpul-luar terakhirnya j  1 adalah j  k. Padahal setelah dikenai

 , simpul-luar j  1 masuk ke dalam  

subpohon terbesar yang simpul-luar terakhirnya l. Artinya, ada penambahan bobot terhadap subpohon dengan simpul-luar terakhir l sebesar j  k. Dari sini disimpulkan bahwa setelah dikenai

 , subpohon terbesar yang simpul-luar terakhirnya l diperbesar oleh subpohon  

terbesar yang simpul-luar terakhirnya j  1. Dalam kasus subpohon ini adalah T1 simpul-luar pertamanya adalah k, tetapi dalam kasus subpohon ini lebih besar dari T1, simpul-luarnya Title of manuscript is short and clear, implies research results (First Author)

38 

ISSN: 2355-3677

terletak sebelum k. Jadi k ≥ l  wT’(l) + 1 atau wT’(l) ≥ l  k + 1. Jadi l – wT’(l) ≤ k – 1. Sehingga l – k+1=

wT 1 (l) ≤ wT’(l). Karena untuk setiap i ≠ l, wT 1 (i) ≤ wT(i), maka wT 1 ≤ wT’. wT 1 ≤ wT’ dan T  T1. Dengan mengulang

Jadi pohon T1 terbentuk sedemikian sehingga wT ≤

proses tersebut, kita dapat menemukan barisan berhingga dari pohon-pohon Ti sedemikian sehingga wT ≤ transitif: T

wT 1 ≤ wT 2 ≤ ... ≤ wT n = wT’ dan T  T1  T2  ...  Tn = T’. Secara

 T’.   

Teorema 6.7: [4]    adalah sebuah relasi urutan parsial dari B.

Bukti. Dengan menggunakan teorema 5.6 yaitu T

   T’ jika dan hanya jika untuk setiap i ϵ

[1, n], wT(i)  wT’(i) dimana T, T’ ϵ Bn. Sebab relasi  merupakan relasi urutan parsial maka dari teorema 5.6 dapat disimpulkan bahwa

 juga merupakan relasi urutan parsial.   

Teorema 6.8: [4] Untuk setiap n, (Bn,

*   ) adalah kisi-kisi (lattice).

Bukti.Ambil T, T’, T”  Bn. Akan ditunjukkan bahwa setiap pasangan dari pohon biner T dan T’ dengan n simpul-dalam mempunyai infimum T  T’. Menurut teorema 5.6 jika T” maka untuk setiap i berlaku wT”(i)  wT(i) dan jika T

 T  

 T” maka untuk setiap i berlaku wT”(i)  

 wT’(i). Selanjutnya karena untuk setiap i berlaku wT”(i)  wT(i) dan wT”(i)  wT’(i) maka berlaku wT”(i)  inf(wT(i), wT’(i)) untuk setiap i. Kita cukup menunjukkan bahwa wP = (inf{wT(i), wT’(i)} ); i  [1, n] adalah barisan bobot, yaitu dengan membuktikan kondisi pada teorema 5.4. Jelas bahwa 1  inf{wT(i), wT’(i)} i. Kemudian jika i’ ϵ [i – inf{wT(i), wT’(i)} + 1, i] maka i  wT(i)  i’  wT(i’) dan i  wT’(i)  i’  wT’(i’). Sehingga i  inf{wT(i), wT’(i)} ≤ sup{i’  wT(i’), i’  wT’(i’)} = i’  inf{wT(i’), wT’(i’)}. Jadi wP = ( inf{wT(i), wT’(i)}); i  [1, n] adalah barisan bobot. Sehingga wT T ' (i) = inf{wT(i), wT’(i)}, untuk setiap i. 

Akibat 6.9 (Meet Dua Pohon): [3] Misalkan T’, T”  Bn.. T adalah meet dari T’ dan T” dinotasikan (T = T’  T”), jika untuk setiap i berlaku wT(i) = wT’T”(i) = inf(wT’(i), wT”(i))


JTRISTE

 39

ISSN: 2355-3677

Bukti. Lihat bukti teorema 6.8  Kecuali pada kasus sup(wT’(i), wT”(i)) = 1 atau sup(wT’(i), wT”(i)) = i, pada umumnya wT’T”(i)  sup(wT’(i), wT”(i)). Sebagai akibatnya, pendefinisian

secara konstruktif wT’T”(i) tidak bisa

langsung, memerlukan langkah-langkah seperti yang dinyatakan oleh Akibat 6.10.

Akibat 6.10 (Join Dua Pohon): [3] Misalkan T’, T”  Bn.. T adalah join dari T’ dan T” dinotasikan (T = T’  T”). Barisan bobot wT = (wT(1), wT(2), ...,wT(n)) dari T didefinisikan pada algoritma berikut: Langkah 1. Untuk setiap i = 1, 2, ..., n didefinisikan vT(i) = sup(wT’(i), wT”(i)). Langkah 2. Jika vT(i) = 1 atau vT(i) = i, definisikan wT(i) = vT(i). Langkah 3. Sebaliknya jika vT(i) ≠ 1 dan vT(i) ≠ i, definisikan wT(i) = i – l + 1, dimana l = min{k – vT(k) + 1 | k  [i – vT(i) + 1, i]}.

KESIMPULAN Pada jurnal ini, kami telah memaparkan struktur khusus dari himpunan pohon biner dengan menerapkan konsep rotasi dan beberapa sifat dapat diberikan pada pohon biner dengan buktibukti berdasarkan teorema dan lemma yang ada. a. (Bn,

*   ) adalah kisi-kisi (lattice), untuk setiap n.

b. Untuk setiap n, (Bn,, d) adalah sebuah ruang metrik dan untuk setiap T, T’ ϵ Bn berlaku: 0 ≤ d(T, T’) ≤ 2n – 2. c. Untuk setiap struktur pohon biner dapat diwakili oleh sebuah barisan bobot. d. Barisan bobot pohon biner yang diurutkan menggunakan preorder traversal dapat pula dibentuk

menggunakan

inorder

traversal.

(Barisan

bobot

dapat

pula

diurutkan

menggunakan postorder traversal namun akan menghasilkan barisan bobot yang sama dengan preorder traversal).


40 

ISSN: 2355-3677

Daftar pustaka [1]

Culik II. K., dan Wood, D., 1982, A Note On Some Tree Similarity Measures, Information Processing Letters 15, pp. 39-42.

[2]

Kreyszig, Erwin, 1978, Introductory Functional Analysis With Applications, New York, John Wiley and Sons, Inc.

[3]

Pallo, J. M., 1987, On The Rotation Distance In The Lattice Of Binary Trees, NorthHolland, Information Processing Letters 25, pp. 369-373.

[4]

Pallo, J. M., 1986, Enumerating, Ranking, and Unranking Binary Trees, The Computer Journal, vol. 29, no. 2, pp. 171-175.

[5]

Rosen, H. Kenneth, 1998, Discrete Mathematics and Its Applications Fourth Edition, The McGraw-Hill Companies, Inc

[6]

Sleator, D.D.,dkk, 1986, Rotation Distance, Triangulations, and Hyperbolic Geometry,


BEBERAPA SIFAT JARAK ROTASI PADA POHON BINER TERURUT DAN TERORIENTASI

Recommend Documents