apa yang
di maksud dengan tree dan binary treeapa yang di maksud dengan tree dan binary
tree
Pengertian
Tree dalam Struktur Data
Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkanhubungan Yang bersifat hirarkis (hubungan one
to
many) antara elemen-elemen.Tree Bisa didefinisikan sebagai kumpulan Simpul /
node dengan Satu elemenKHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untukjelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam
tree
}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.
Pengertian
Binaary Tree dalam Struktur Data
Pohon
biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal duasubtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap nodedalam binary
tree hanya boleh memiliki paling banyak dua anak/child
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).
istilah-istilah umum dalam tree
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.
contoh
program tree
uses crt;
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;
pengertian
AVL tree
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.
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)
gambar 2.
Sebutkan
beberapa jenis tree yang memiliki sifat khusus
v Create :
Membentuk binary tree baru yang masih kosong.
v Clear : Mengosongkan binary tree yang sudah ada.
v Empty : Function untuk memeriksa apakah binary tree masih kosong.
v 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.
v Find : Mencari root, parent, left child, atau right child dari
suatu node. (Tree tak boleh kosong)
v Update : Mengubah isi dari node yang ditunjuk oleh pointer current.
(Tree tidak boleh kosong)
v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current.
(Tree tidak boleh kosong)
v 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.
v 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)
v Traverse :
Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah
urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara
traverse : Pre Order, In Order, dan Post Order.
Tidak ada komentar:
Posting Komentar