MODUL 9

MODUL 9
TREE

Tree
Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :
a) Prodecessor : node yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh :












Beberapa jenis Tree yang memiliki sifat khusus :
1) Binary Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.














Jenis-jenis Binary Tree :
a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.








b) Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.






c) Skewed Binary Tree
akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.





Implementasi Binary Tree
Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :
Type Tree = ^node;
Node = record
Isi : TipeData;
Left,Right : Tree;
end;
Contoh ilustrasi Tree yang disusun dengan double linked list :





(Ket: LC=Left Child; RC=Right Child)
Operasi-operasi pada Binary Tree :
 Create : Membentuk binary tree baru yang masih kosong.
 Clear : Mengosongkan binary tree yang sudah ada.
 Empty : Function untuk memeriksa apakah binary tree masih kosong.
 Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
 Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
 Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
 Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
 DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
 Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
 Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.


Langkah-Langkahnya Traverse :
 PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
 InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
 PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :


Memasukkan sebuah node ke dalam Tree yang masih kosong (Sebagai Tree)



Menambahkan sebuah node sebagai right child dari Root.




Menambahkan sebuah node sebagai left child dari node yang sebelunya di-insert.





Memindahkan pointer ke Root kemudian menambhakan sebuah node sebagai left child dari root.





Menambhakan sebuah node sebagai left child dari node yang sebelumnya di-insert.




Memindahkan pointer ke Root, kemudian pindahkan lagi pointer ke right child dari Root, kemudian masukkan sebuah node sebagai right child dari node yang sedang ditunjuk oleh pointer.



2) Binary search Tree
Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :








Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.
1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).


Memasukkan sebuah node yang berisi angka 12. Karena tree masih kosong, maka secara otomatis node tersebut menjadi root.



Karena 15 lebih besar dari 12, maka sesuai dengan peraturan harus berada disebelah kanan parent (right child)




Karena 13 lebih besar dari 12, maka sesuai dengan peraturan harus berada di sebelah kanan parent (12), lalu bandingkan lagi dengan 15. karena lebih kecil maka 13 menempati left child dari 15.








Proses yang sama seperti sebelumnya berlaku untuk selanjutnya.


















2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.
3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.
(Keadaan awal merupakan lanjutan gambar sebelumnya)

Karena node yang berisi 5 adalah leaf, maka ia dapat langsung dihapus.





Karena node yang berisi 20 adalah leaf, maka ia dapat langsung dihapus.







Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.




Pada operasi di samping, delete dilakukan terhadap node dengan 1 child. Maka child tersebut (11) akan menggantikan posisi dari node yang didelete (9).

MODUL 8

MODUL 8

FIFO (First In First Out)

FIFO adalah suatu metoda pembuatan Linked List dimana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) misalkan saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket.

Jika Linked List dibuat dengan metode FIFO, maka terjadi penambahan/Insert simpul di depan.

Procedure INSERT(elemen:TipeData); Var Now:Point; Begin New(Now); If head = nil then Head:=now else Tail^.next:=now; Tail:=Now; Tail^.next:=nil; Now^.isi:=elemen; End;

PROCEDURE INSERT

Head

Penggalan procedure INSERT untuk FIFO

{head mula-mula selalu diidentifikasikan sebagai nil}

Now Head Tail

Now

Head Tail

Now

Head Tail

Head Tail Now

Head Now Tail

Head Now Tail

Head Now Tail

Procedure dan Function Linked List Lainnya

Selain procedure insert di atas, pada linked list juhga terdapat procedure serta function lainnya.

Di bawah ini diberikan procedure-procedure serta function umum dalam aplikasi Linked List.

v Create : Membuat sebuah linked list yang baru dan masih kososng. (ket: procedure ini wajib dilakukan sebelum menggunakan linked list)

Head Tail

v Empty : Function untuk menentukan apakah linked list kosong atau tidak.

	Function Empty : Boolean; Begin If head = nil then Empty:= true else empty:= false; end;

v Find First : Mencari elemen pertama dari linked list

Head Now Tail

v Find Next : Mencari elemen sesudah elemen yang ditunjuk now.

	Procedure Find_Next; Begin If Now^.next <> nil then Now:= Now^.next; End;

Head Now Tail

(ket: gambar lanjutan dari sebelumnya)

v Retrieve : Mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu ditampung pada suatu variabel (di bawah dicontohkan variabel r).

	Procedure Retrieve(var r: TipeData ); Begin R:= Now^.isi; End;

v Update : Mengubah elemen yang ditunjuk oleh now dengan isi dari suatu variabel (di bawah dicontohkan variabel u).

Head Now Tail

v Delete Now : Menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list(head), maka head akan berpindah ke elemen berikut.

	Procedure DeleteNow; Var x : point; Begin If now<>head then Begin x:=head; while x^.next<>now do x:=x^.next; x^.next:=now^.next; end else head:= head^.next; dispose(Now); Now:= head; End;

Head x Now Tail

Head x Now Tail

v Delete Head : Menghapus elemen yang ditunjuj head. Head berpindah ke elemen sesudahnya.

	Procedure DeleteHead; Begin If head<>nil then Begin Now:=head; Head:=Head^.next; Dispose(Now); Now:=Head; End; End;

Now Head Tail

Head Now Tail

v Clear : Untuk menghapus linked list yang sudah ada.wajib dilakukan bila ingin mengakhiri program yang menggunakan linked list. Jika tidak data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

	Procedure Clear; Begin While head <> nil do Begin Now:=head; Head:=head^.next; Dispose(Now); End; End;

Latihan Soal beserta jawaban (Listing Program) dan penjelasan

Buatlah sebuah program untuk mendeteksi password/ kata sandi. Gunakan metode single linked list. Jika passwordnya benar, program akan selesai, jika salah maka user akan diminta memasukkan password kembali. (passw.pas)

	Enter Your Password:

Jawaban :

Uses crt;

Type

Point = ^Rec;

Rec = record

Isi : char;

Next : point;

End;

Const

Password = ‘pascal’; {password yang harus dimasukkan}

Var

i : byte;

Tekan : char;

Passwd : Boolean;

Head, Tail, Now : Point;

Procedure Create;

Begin

Head:=nil;

Tail:=nil;

End;

Procedure Push(isi:char);

Var Now:point;

Begin

New(now); {membuat simpul baru}

If Head=Nil then {mendeteksi simpul awal}

Begin

Head:=Now;

Tail:=Head;

end else

begin {menyambung simpul yang baru pada simpul yang sudah ada}

Tail^.next:=Now;

Tail:=Tail^.Next;

end;

Now^.isi:=isi; {mengisi simpul yang baru}

Now^.next:=Nil;

end;

Function Check:Boolean; {function untuk mencheck input}

Var Temp : string[15];

Begin

Temp:=’ ‘; Now:=Head;

While Now <> nil do

Begin

Temp:=temp + Now^.isi;

Now:=Now^.next;

End;

If temp <> Password then check:=False;

End;

Procedure BuatBingkai(x1,y1,x2,y2:byte); {tampilan aplikasi}

Var i : byte;

Begin

GotoXY (x1,y1); write(‘ ’); GotoXY (x2,y1); write (‘ ‘);

GotoXY (x1,y2); write(‘ ’); GotoXY (x2,y2); write (‘ ’);

For i := x1+1 to x2-1 do

Begin

GotoXY (i,y1); write (‘-‘);

GotoXY (i,y2); write (‘-’);

End;

For i := y1+1 to y2-1 do

Begin

GotoXY(x1, i); write(‘ ‘);

GotoXY(x2, i); write (‘ ‘);

End;

End;

Procedure Pop; {procedure penghapus simpul}

Begin

Now:=head;

head:=head^.next;

While Now <> nil do

Begin

Dispose(Now);

Now:=head;

Head:=head^.next;

End;

End;

Begin {program utama}

Repeat

Create; I:=0;

Repeat

Tekan:=ReadKey;

Write(Tekan);

If Tekan <>#13 then Push(Tekan); inc(i);

Until (Tekan= #13) or (I=10); {enter ditekan atau panjang = 10}

Passwd:=check; Pop;

Until Passwd;

End.