pohon pencarian biner

POHON PENCARIAN BINER (BINARY SEARCH TREE, BST)

Pohon pencarian biner, selanjutnya disebut BST adalah struktur data yang elemen-elemennya terdiri dari informasi, alamat elemen sebelumnya dan alamat elemen sesudahnya. BST dikenali melalui akarnya. Pada BST berlaku prinsip bahwa info elemen sebelah kiri lebih kecil dari info elemen sebelah kanan. Elemen pada BST disebut simpul. .

Gambar 1. List dengan 10 elemen

Gambar 2.BST dengan 10 simpul

Pada Gambar 1, untuk mengakses 10, harus dilakukan 10 kali pemeriksaan, sedangkan pada Gambar 2, hanya perlu dilakukan 5 kali pemeriksaan.

Istilah-istilah pada BST

Akar: simpul pertama pada BST

Daun: simpul yang tidak mempunyai anak, contoh simpul 1, 4, 7, 10

Anak kiri: simpul kiri dari sebuah simpul, anak kiri dari 5 adalah 3, anak kiri dari 3 adalah 2

Anak kanan: simpul kanan dari sebuah simpul, anak kanan dari 5 adalah 8, anak kanan dari 8 adalah 9

Ancestor: induk dari simpul, ancestor dari 2 dan 4 adalah 3 dan 5, akar adalah ancestor dari semua simpul

Descendant: anak simpul, descendant dari 3 adalah 2, 4 dan 1

Sub pohon kiri: descendant kiri dari sebuah simpul

Sub pohon kanan: descendant kanan dari sebuah simpul

Level: jarak dari simpul Akar. Level simpul Akar adalah 0. Jumlah maksimum simpul pada suatu level adalah 2N

Tinggi pohon: Level + 1

Representasi Lojik BST

Deklarasi global :

type TInfo = {tipe terdefinisi}

type Address = pointer to Elemen

type Elemen: <Info: TInfo, Kiri: Address, Kanan: Address>

type BST = record <Akar: Address>

T: BST

procedure Create(output T: BST)

{membuat sebuah BST kosong}

{IS. sembarang}

{FS. T kosong terdefinisi}

procedure Traversal(input T: BST)

{mengunjungi simpul pada T

{IS. pohon T terdefinisi, mungkin kosong }

{FS. semua elemen pohon T terkunjungi }

procedure SearchTree(input T: BST, Val: TInfo, output P: Address}

{menentukan keberadaan Val di dalam BST}

{IS. T terdefinisi, mungkin kosong }

{FS. P adalah alamat dimana Val ditemukan, P = Nil jika Val tidak ditemukan}

procedure InsertBST(input/output T: BST, input P: Address)

{menyisipkan simpul dengan alamat P ke dalam T}

{IS. T terdefinisi, mungkin kosong }

{ P terdefinisi, Kiri(P) = Nil dan Kanan(P) = Nil}

{FS. P menjadi simpul pohon sesuai dengan harga Info(P), jika pohon kosong

maka T.Akar = P }

procedure DeleteBST(input/output T: Pohon, input P: Address)

{IS. Pohon T terdefinisi, tidak kosong }

{FS. Simpul yang alamatnya P dihapus dari pohon dan alamat P ditempati oleh

elemen paling kanan yang terdekat }

Membuat BST kosong

procedure Create(output T: BST)

{membuat sebuah BST kosong}

{IS. sembarang}

{FS. T kosong terdefinisi}

Deklarasi:

Deskripsi:

T.Akar Nil

Melakukan pencarian simpul BST

procedure SearchTree(input T: BST, Val: TInfo, output P: Address}

{menentukan keberadaan Val di dalam BST}

{IS. T terdefinisi, Val terdefinisi, yaitu info yang akan dicari }

{FS. P adalah alamat dimana Val ditemukan, P = Nil jika Val tidak ditemukan}

Deklarasi:

Found: boolean

Deskripsi :

P T.Akar

Found false

while P Nil and not Found do

if Info(P) = Val then

Found true

else

if Info(P) < Val then

P Kanan(P)

else

P Kiri(P)

endif

endif

endwhile {P = Nil atau Found}

Melakukan penyisipan simpul pada BST

procedure InsertBST(input/output T: BST, input PIns: Address)

{menyisipkan simpul dengan alamat P ke dalam T}

{IS. T terdefinisi, mungkin kosong }

{ P terdefinisi, Kiri(P) = Nil dan Kanan(P) = Nil}

{FS. P menjadi simpul pohon sesuai dengan harga Info(P), jika pohon kosong

maka T.Akar = P }

Deklarasi:

P: Address

Deskripsi :

P T.Akar

Prev Nil

while P Nil do

Prev P

if Info(P) > Info(PIns) then

P Kiri(P)

else

P Kanan(P)

endif

endwhile { P = Nil}

if Prev = Nil then {pohon kosong}

T.Akar PIns

else

if Info(Prev) > Info(PIns) then

Kiri(Prev) PIns

else

Kanan(Prev) PIns

endif

endif

Melakukan penghapusan simpul BST

Secara garis besar kita membagi kasus penghapusan menjadi 3 yaitu :

  1. Menghapus elemen daun (elemen yang tidak punya anak), dapat dilakukan dengan me-Nil-kan Kiri atau Kanan induk elemen tersebut. Perhatikan gambar berikut :

induk

X

ex-induk

X

X

X

Dihapus

Gambar 3. Menghapus simpul daun

  1. Menghapus elemen yang memiliki satu anak, tidak dapat dilakukan hanya dengan me-Nil-kan Kanan atau Kiri dari induk seperti pada penghapusan elemen daun, karena kita tidak mau kehilangan descendant dari pohon tersebut. Cara yang dilakukan adalah dengan membuat Kiri atau Kanan dari induk meloncati elemen yang dihapus dan menunjuk ke anak dari elemen yang dihapus. Perhatikan gambar berikut :

induk

X

ex-induk

X

X

X

Dihapus

anak

X

ex-anak

X

Gambar 4. Menghapus simpul dengan satu anak

3. Menghapus simpul yang memiliki dua anak. Kasus ini paling sulit. Metode yang paling umum adalah menukar elemen yang akan kita hapus dengan nilai elemen yang terdekat. Elemen dapat berasal dari subpohon kiri maupun dari subpohon kanan. Pada kuliah ini kita akan mengganti elemen yang dihapus dengan elemen terdekat yang berasal dari subpohon kiri. Jadi elemen pengganti adalah elemen yang nilainya lebih kecil (predesesor) terdekat dari elemen yang akan dihapus. Jika kita memilih elemen pengganti dari subpohon kanan berarti elemen pengganti adalah elemen yang nilainya lebih besar (suksesor) terdekat dari elemen yang dihapus.

Untuk menemukan predesesor, kita berjalan ke kiri sekali kemudian terus ke kanan sampai elemen daun. Jika anak kiri tidak punya anak kanan maka anak kiri itu sendiri yang menjadi elemen pengganti. Berikutnya, kita mengganti info dari elemen yang akan dihapus dengan info dari elemen pengganti, kemudian menghapus elemen pengganti (kasus 1 atau kasus 2). Perhatikan gambar berikut :

Gambar 5. Menghapus simpul dengan dua anak

Algoritma penghapusan elemen pada pohon adalah sebagai berikut :

procedure DeleteBST(input/output T: Pohon, input P: Address)

{IS. Pohon T terdefinisi, tidak kosong }

{FS. Simpul yang alamatnya P dihapus dari pohon dan alamat P ditempati oleh

elemen paling kanan yang terdekat }

Deklarasi:

Temp: Address

Deskripsi :

if (Kanan(P) = Nil) and (Kiri(P) = Nil) then

if Prev = Nil then

Akar Nil

else

if Kanan(Prev) = P then

Kanan(Prev) Nil

else

Kiri(Prev) Nil

endif

endif

else {elemen dengan 2 anak}

if Kanan(P) Nil and Kiri(P) Nil then

Prev P

Temp Kiri(P)

while Kanan(Temp) Nil do

Prev Temp

Temp Kanan(Temp)

endwhile

Info(P) Info(Temp)

if Prev = P then

Kiri(Prev) Kiri(Temp)

else

Kanan(Prev) Kiri(Temp)

endif

Kiri(Temp) Nil

else {elemen dengan 1 anak}

if Kanan(P) Nil then {anak kanan }

if Prev = Nil then {P adalah akar}

T.Akar Kanan(P)

else

if Kanan(Prev) = P then

Kanan(Prev) Kanan(P)

else

Kiri(Prev) Kanan(P)

endif

Kanan(P) Nil

endif

else {anak kiri}

if Prev = Nil then

T.Akar Kiri(P)

else

if Kanan(Prev) = P then

Kanan(Prev) Kiri(P)

else

Kiri(Prev) Kiri(P)

endif

Kiri(P) Nil

endif

endif

endif

endif

Algoritma penghapusan simpul dibuat menjadi lebih sederhana seperti berikut:

procedure Search_and_Delete(input/output T: BST, input Val: TInfo)

{mencari simpul yang info-nya = Val, kemudian menghapusnya}

{IS. T terdefinisi, tidak kosong, Val terdefinisi, yaitu info yang akan

dihapus, Val ada di dalam BST}

{FS. simpul yang info-nya = Val dihapus}

Deklarasi:

Prev, P: Address

Deskripsi:

P T.Akar

Prev Nil

while Info(P) Val do

Prev P

if Info(P) > Val then

P Kiri(P)

else

P Kanan(P)

endif

endwhile

DeleteBST(T, P, Prev)

Penelusuran pada BST

Gambar 6. BST dengan 10 elemen

Penelusuran (traversal) pada BST artinya mengunjungi semua simpul BST dan melakukan pemrosesan terhadap simpul yang dikunjungi. Ada 3 cara penelusuran, yaitu:

  1. Penelusuran inorder, yaitu mulai dari sub pohon kiri, Akar dan sub pohon kanan.

  2. Penelusuran preorder dimulai dari Akar, sub pohon kiri dan sub pohon kanan,

  3. Penelusuran postorder dimulai dari sub pohon kiri, sub pohon kanan dan Akar.

Perhatikan kembali pohon pada Gambar 6. Jika kita menelusuri (traversal) pada pohon tersebut maka urutan informasi yang akan diperoleh adalah sebagai berikut :

  • Traversal preorder : J, D, B, A, G, Q, M, N, T, U

  • Traversal inorder : A, B, D, G, J, M, N, Q, T, U

  • Traversal postorder : A, B, G, D, N, M, U, T, Q, J

Penelusuran BST akan lebih “elegan” jika menggunakan algoritma rekursif. Pada kuliah ini akan dibahas lebih dulu penelusuran secara inorder, tanpa menggunakan teknik rekursif.

Untuk traversal pada list linier kita menggunakan sebuah pointer temporer yang diberi harga awal sama dengan alamat elemen pertama list, kemudian kita mengikuti keterkaitan satu elemen ke elemen lainnya sampai ke elemen dimana pointer kita berharga Nil. Hal yang sama berlaku juga pada traversal pohon, kita memulai traversal dari Akar (sebuah pohon dikenal melalui Akarnya). Pada traversal inorder, berarti dari Akar, pointer menunjuk ke sub pohon kiri. Persoalannya pada saat pointer menunjuk ke sub pohon kiri, kita akan kehilangan akses ke Akar, sehingga kita tidak dapat balik ke Akar. Untuk mengatasi hal ini akan digunakan struktur data stack untuk menyimpan alamat yang telah dikunjungi, supaya tidak kehilangan akses.

Algoritma traversal pohon adalah :

procedure InOrder(input T: BST)

{IS. pohon T terdefinisi, mungkin kosong }

{FS. semua elemen pohon T terkunjungi }

Deklarasi :

P: Address

S: Stack

Deskripsi :

P T.Akar

repeat

while P Nil do

Push(S, P)

P Kiri(P)

endwhile { P = Nil}

if not EmptyStack(S) then

Pop(Stack, P)

Proses(P)

P Kanan(P)

endif

until P = Nil and EmptyStack(S)

Published in: on October 23, 2009 at 12:54 pm  Comments (1)  

The URI to TrackBack this entry is: https://awaninsky.wordpress.com/2009/10/23/biner/trackback/

RSS feed for comments on this post.

One CommentLeave a comment

  1. Hi, this is a comment.
    To delete a comment, just log in, and view the posts’ comments, there you will have the option to edit or delete them.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: