Kamis, 03 Maret 2011

TREE (POHON)

Struktur pada tree (pohon) tidak linear seperti pada struktur linked list, stack,
dan queue. Setiap node pada tree mempunyai tingkatan, yaitu orang tua
(parent) dan anak (child). Struktur ini sebenarnya merupakan bentuk khusus
dari struktur tree yang lebih umum, setiap orang tua hanya memiliki dua anak
sehingga disebut pohon biner (binary tree), yaitu anak kiri dan anak kanan.
ISTILAH DASAR
Tree merupakan salah satu bentuk struktur data tidak linear yang
menggambarkan hubungan yang bersifat hirarkis (hubungan one to many)
antara elemen-elemen. Tree dapat didefinisikan sebagai kumpulan simpul/node
dengan satu elemen khusus yang disebut root dan node, disebut sub tree/sub
pohon atau cabang.
Sehingga secara sederhana pohon bisa didefinisikan sebagai kumpulan elemen
yang salah satu elemennya disebut dengan akar (root) dan elemen yang lainnya
(simpul), terpecah menjadi sejumlah himpunan yang saling tidak berhubungan
satu dengan yang lainnya.
• Predecessor : node yang berada di atas node tertentu
• Successor : node yang dibawah node tertentu
• Ancestor : seluruh node yang terletak sebelum node tertentu dan
terletak sesudah pada jalur yang sama
• Descendant : seluruh node yang terletak sesudah node tertentu dan
terletak sesudah pada jalur yang sama
• Parent : predecessor satu level diatas suatu node
• Child : successor satu level dibawah 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 tidak
mempunyai predecessor
• Leaf : node-node dalam tree yang tidak memiliki successor
• Degree : banyaknya child yang dimiliki suatu node
Contoh :
A
B C
D E F G
Modul 9 Struktur Data (Arie) - 2
Keterangan :
• Ancestor : C, A
• Descendant : C, G
• Parent : B
• Child : B, C
• Sibling : F, G
• Size : 7
• Height : 3
• Root : A
• Leaf : D, E, F, G
• Degree : 2
JENIS TREE
1. Binary Tree
adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua
subtree dan kedua subtree tersebut harus terpisah. Maka tiap node dalam
binary tree hanya boleh memiliki paling banyak dua child.
Leaf
Keterangan :
• Left Child : B, D, H, ...
• Right Child : C, G, J, ...
Jenis Binary Tree
􀂾 Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap sub
tree harus mempunyai panjang path yang sama.
A
B C
D E F G
H I J
Modul 9 Struktur Data (Arie) - 3
􀂾 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.
􀂾 Skewed Binary Tree
Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
Operasi 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 3 pilihan
insert, yaitu : 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 tidak boleh kosong.
• Update : mengubah isi dari node yang ditunjuk oleh pointer
current. Tree tidak boleh kosong.
A
B C
D E F G
A
B C
D E
A
B
D
Modul 9 Struktur Data (Arie) - 4
• Retrive : mengetahui isi dari node yang ditunjuk oleh pointer
current. Tree tidak boleh kosong.
• DeleteSub : menghapus sebuah subtree (node beserta seluruh
descedantnya) yang ditunjuk current. Tree tidak 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.
• Traverse : mengunjungi seluruh node pada tree, masing-masing
sekali. Hasilnya adalah urutan informasi secara linear
yang tersimpan dalam tree. Ada tiga cara traverse : Pre
Order, InOrder, dan PostOrder.
Langkah 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.
2. Binary Search Tree
Adalah binary tree dengan sifat bahwa semua left child harus lebih kecil
daripada right child dan parentnya. Semua right child harus lebih besar dari left
child serta parentnya. Binary Search Tree dibuat untuk mengatasi kelemahan
pada binary tree biasa, yaitu kesulitan dalam searching/pencarian node
tertentu dalam binary tree.
Contoh :
Operasi Binary Tree
Pada dasarnya sama dengan operasi pada binary tree, kecuali pada operasi
insert, update, dan delete.
• Insert : dilakukan setelah ditemukan lokasi yang tepat, lokasi
tidak ditentukan oleh user sendiri.
• Update : update akan berpengaruh pada posisi node tersebut
selanjutnya. Setelah diupdate mengakibatkan tree
tersebut bukan binary search tree lagi, maka harus
dilakukan perubahan pada tree dengan melakukan rotasi
supaya tetap menjadi binary search tree.
• Delete : akan mempengaruhi struktur dari tree.
18
10 23
5 14 21 25
Modul 9 Struktur Data (Arie) - 5
3. AVL Tree
Adalah binary search tree yang memiliki perbedaan tingkat tinggi/level antara
subtree kiri dan subtree kanan maksimal adalah 1. Dengan AVL Tree, waktu
pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Selain AVL Tree terdapat juga Height Balanced n tree, yaitu binary search tree
yang memiliki perbedaan level antara subtree kiri dan subtree kanan maksimal
adalah n. Sehingga AVL Tree adalah Height Balanced 1 Tree.
Simbol Bantu
Untuk mempermudah menyeimbangkan tree, maka digunakan simbol-simbol
bantu.
• Minus ( - ) : digunakan apabila subtree kiri lebih panjang dari
subtree kanan.
• Plus ( + ) : digunakan apabila subtree kanan lebih panjang dari
subtree kiri.
• Nol ( 0 ) : digunakan apabila subtree kiri dan subtree kanan
mempunyai height yang sama.
CONTOH SOAL :
Soal 1
Buatlah program untuk menampilkan node baru ke dalam pohon dengan
menggunakan prosedur preorder, inorder, dan postorder.
//Program :tree.cpp
#include
#include
struct nod {
struct nod *left;
char data;
struct nod *right;
};
typedef struct nod NOD;
typedef NOD POKOK;
NOD *NodBaru(char item) {
NOD *n;
n = (NOD*) malloc(sizeof(NOD));
if(n != NULL) {
n->data = item;
n->left = NULL;
n->right = NULL;
}
return n;
}
void BinaPokok(POKOK **T) {
*T = NULL;
}
Modul 9 Struktur Data (Arie) - 6
typedef enum { FALSE = 0, TRUE = 1} BOOL;
BOOL PokokKosong(POKOK *T) {
return((BOOL)(T == NULL));
}
void TambahNod(NOD **p, char item) {
NOD *n;
n = NodBaru(item);
*p = n;
}
void preOrder(POKOK *T) {
if(!PokokKosong(T)) {
printf("%c ", T->data);
preOrder(T->left);
preOrder(T->right);
}
}
void inOrder(POKOK *T) {
if(!PokokKosong(T)) {
inOrder(T->left);
printf("%c ", T->data);
inOrder(T->right);
}
}
void postOrder(POKOK *T) {
if(!PokokKosong(T)) {
postOrder(T->left);
postOrder(T->right);
printf("%c ", T->data);
}
}
int main()
{
POKOK *kelapa;
char buah;
BinaPokok(&kelapa);
TambahNod(&kelapa, buah = 'M');
TambahNod(&kelapa->left, buah = 'E');
TambahNod(&kelapa->left->right, buah = 'I');
TambahNod(&kelapa->right, buah = 'L');
TambahNod(&kelapa->right->right, buah = 'O');
TambahNod(&kelapa->right->right->left, buah = 'D');
printf("Tampilan secara PreOrder: ");
preOrder(kelapa);
printf("\nTampilan secara InOrder: ");
inOrder(kelapa);
printf("\nTampilan secara PreOrder: ");
postOrder(kelapa);
printf("\n\n");
return 0;
}
Modul 9 Struktur Data (Arie) - 7
SOAL LATIHAN :
Buatlah program untuk menampilkan node baru ke dalam pohon dengan
menggunakan prosedur preorder, inorder, dan postorder.
Sehingga akan didapatkan hasil :
Tampilan secara PreOrder : R A S I T E
Tampilan secara InOrder : I S T A R E
Tampilan secara PostOrder : I T S A E R
Contoh ada di file : tree2.exe
Save dengan nama file : tre_nim (4 digit nim terakhir)

2 komentar:

  1. untuk contoh soal no1 bagaimana caranya untuk di buat gambar pohonya

    BalasHapus
  2. Itu contoh data yang diinput berupa Char ( M, E, I, dsb) klo yang diinput berupa integer ( bilangan bulat) gmna codingnya???

    BalasHapus