SOAL
1)
Jelaskan apa yang di maksud dengan tree dan binary tree
2)
Uraikan istilah-istilah umum dalam tree
3)
Buatlah 1 contoh program tree
4)
Sebutkan pengertian AVL tree
5)
Sebutkan beberapa jenis tree yang memiliki sifat khusus
Pengertian
Tree Dan Binary Tree
v
Pengertian Tree
Tree
merupakan salah satu bentuk struktur data tidak linear yang menggambarkan
hubungan yang bersifat hirarki (hubungan one to many) antara elemen-elemen.
Bentuk tree menyerupai sebuah pohon, yang terdiri dari serangkaian node
(simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah
vektor. Sehingga tree bisa didefinisikan sebagai kumpulan simpul atau node
dengan elemen khusus yang disebut root atau akar.
Contoh
data yang dapat direpresentasikan dengan menggunakan tree adalah silsilah
keluarga, hasil pertandingan yang berbentuk turnamen, atau struktur organisasi
dari sebuah perusahaanDalam pemrograman, sebuah tree terdiri dari elemen-elemen
yang dinamakan node (simpul) yang mana hubungan antar simpul bersifat
hirarki. Simpul yang berada di bawah root secara langsung,
dinamakan anak dari root, yang mana biasanya juga mempunyai anak di bawahnya.
Sehingga bisa disimpulkan, kecuali root, masing-masing simpul dalam hirarki
mempunyai satu induk (parent). Jumlah anak sebuah simpul induk sangat
bergantung pada jenis dari pohon.
Setiap
node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang
memiliki
node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu
node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak
seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak
akan digambarkan berada di bawah node induknya. Node yang berada di pangkal
tree disebut node root (akar), sedangkan node yang berada paling ujung tree
disebut node leaf (daun).
v
Pengertian 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.
Istilah –
Istilah Umum Dalam Tree
- Prodecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Ancestor : seluruh node yang terletak sebelum node
tertentu dan terletak pada jalur yang sama.
- Descendant : seluruh node yang terletak sesudah node
tertentu dan terletak pada jalur yang sama.
- Parent :
predecssor satu level di atas suatu node.
- Child :
successor satu level di bawah suatu node.
- Sibling :
node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node
beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root :
satu-satunya node khusus dalam tree yang tak punya predecssor.
- Leaf : node-node dalam tree yang tak memiliki
seccessor.
- Degree : banyaknya child yang dimiliki suatu node.
Contoh Program Tree
uses wincrt;
Type
Tree = ^Simpul;
Simpul = Record
Info : char;
Kiri : Tree;
Kanan : Tree;
End;
Function
BARU(Hrf : Char) : Tree;
Var Temp : Tree;
Begin
New(Temp);
Temp^.Info :=
Hrf;
Temp^.Kiri :=
NIL; Temp^.Kanan := NIL;
BARU := Temp;
End;
Procedure
MASUK(Var Pohon : Tree; Hrf : Char);
Begin
If Pohon = NIL
Then
Pohon :=
BARU(Hrf)
Else
Begin
If Pohon^.Info
> Hrf then
MASUK(Pohon^.Kiri,Hrf)
Else If
Pohon^.Info < Hrf then
MASUK(Pohon^.Kanan,Hrf)
Else
Writeln('Karakter',
Hrf, 'Sudah ada di Tree');
End;
End;
Procedure PREORDER(Temp
: Tree);
Begin
If Temp <>
NIL Then
Begin
Write(Temp^.Info,'
');
PREORDER(Temp^.Kiri);
PREORDER(Temp^.Kanan);
End;
End;
Procedure
INORDER(Temp : Tree);
Begin
If Temp <>
NIL Then
Begin
INORDER(Temp^.Kiri);
Write(Temp^.Info,'
');
INORDER(Temp^.Kanan);
End;
End;
Procedure
POSTORDER(Temp : Tree);
Begin
If Temp <>
NIL Then
Begin
POSTORDER(Temp^.Kiri);
{Kunjungi cabang kiri}
POSTORDER(Temp^.Kanan);
{Kunjungi cabang kanan}
Write(Temp^.Info,'
'); {Cetak isi simpul}
End;
End;
var
poon:tree;
Begin
clrscr;
MASUK(poon,'b');
MASUK(poon,'c');
MASUK(poon,'u');
MASUK(poon,'e');
MASUK(poon,'a');
writeln('PERORDER:');
PREORDER(poon);
writeln;
writeln('INORDER:');
INORDER(poon);
writeln;
writeln('POSTORDER:');
POSTORDER(poon);
readln;
end.
Preoder
Ini adalah contoh Program Binary Tree
PreOrder, InOrder dan PostOrder pada Pascal.
Program
tree_dinamis;
uses crt;
type
pohon=^node;
node=record
data:integer;
kiri,kanan:pohon
end;
var
T:pohon;
info:integer;
procedure Buat_Bst(info:integer;var
T:pohon);
var
b:pohon;
begin
if T=nil then
begin
new (b);
b^.data:=info;
b^.kiri:=nil;
b^.kanan:=nil;
T:=b;
end
else
begin
if
T^.data>info then
buat_Bst(info,T^.kiri)
else
buat_bst(info,T^.kanan);
end;end;
Procedure Baca_bst_pre(b:pohon);
begin
if b <>
nil then
begin
write(b^.data, '
');
baca_bst_pre(b^.kiri);
baca_bst_pre(b^.kanan);
end;end;
Procedure
Baca_bst_in(b:pohon);
begin
if
(b<>nil)then
begin
baca_bst_in(b^.kiri);
write(b^.data);
baca_bst_in(b^.kanan);
end;end;
Procedure
Baca_bst_post(b:pohon);
begin
if b <>
nil then
begin
baca_bst_post(b^.kiri);
baca_bst_post(b^.kanan);
write(b^.data, '
');
end;end;
{Program utama}
begin
clrscr;
new(T);
T^.kiri:=nil;
T^.kanan:=nil;
writeln('masukkan
data kedalam tree');
repeat
write('nilai
data= ');
readln(info);
if info
<>0 then buat_bst(info,T);
until info=0;
writeln;
readln;
writeln('Pembacaan
secara pre order');
baca_bst_pre(T);
writeln;
readln;
writeln('pembacaan
secara in order');
baca_bst_in (T);
writeln;
readln;
writeln('pembacaan
secara post order');
baca_bst_post
(T);
writeln;
readln;
end
AVL TREE
Pengertian AVL
Tree dalam Struktur Data
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Penambahan node
di AVL Tree
Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation
Single Rotation
Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).
Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation
Single Rotation
Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).
Menghapus node
di AVL Tree
Proses menghapus
sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat
menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan
dari node yang dihapus → root. Gunakan single atau double rotation untuk
menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan
sampai root.
Beberapa
Jenis Tree Yang Bersifat Khusus
v 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;
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. 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.
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).
2.
(Keadaan awal merupakan lanjutan gambar sebelumnya)
3.
Pada operasi di samping, delete dilakukan terhadap Node
dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right
SubTree yaitu 13.
Tidak ada komentar:
Posting Komentar