TREE Definisi Merupakan salah satu bentuk struktur data non-linear yang menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen. Tree dapat juga didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node lainnya yang terbagi lagi menjadi himpunan-himpunan yang disebut subtree.
Istilah-istilah Umum dalam Tree a. Predecessor
: node yang berada di atas 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. Father
: predecessor satu level di atas suatu node.
f. Son
: successor satu level di bawah suatu node.
g. Sibling
: node-node yang memiliki father 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 predecessor.
l. Leaf
: Node-node dalam tree yang tak memiliki successor.
m. Degree
: Banyaknya son yang dimiliki suatu node.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 1
Contoh : Subtree
A B
D
Root C
E
G
F
H
I
Keterangan : Ancestor (H) Descendant (F) Father (D) Son (A) Sibling (D) Size Height Root Leaf Degree (E)
= F,C,A = H,I =B = B,C =E =9 =4 =A = D,G,H,I =1
Gambar 1, Binary Tree
Beberapa Jenis Tree 1.
Binary Tree Binary Tree adalah tree dengan syarat bahwa setiap node hanya boleh
memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Dengan demikian, maka setiap node dalam binary tree hanya boleh memiliki paling banyak dua son (perhatikan gambar 1). Jika A adalah root dari suatu binary tree, maka B dikatakan left son dari A dan C dikatakan right son dari A. Kemudian A dikatakan father dari B dan C. Sebuah node yang tidak memiliki son (seperti D, G, H, atau I pada gambar 1) dinamakan leaf. Node n1 adalah ancestor dari node n2 (dan n2 adalah descendant dari n1) jika n1 adalah father dari n2 atau father dari beberapa ancestor n2. Seperti contoh pada gambar 1, A adalah ancestor dari G, dan H adalah descendant dari C, tapi E bukan ancestor maupun descendant dari C. Node n2 adalah left descendant dari node n1 jika n2 juga left son dari n1 atau descendant dari left son n1, begitu sebaliknya untuk right descendant. Dua node dikatakan brothers jika masing-masing node adalah left dan right son dari father yang sama. Meskipun sebuah tree (pohon) yang sesungguhnya tumbuh dengan root (akar) di dalam tanah dan dengan leaf (daun) di udara, namun dalam ilmu komputer secara umum melukiskan struktur data tree dengan root di atas dan leaf
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 2
di bagian bawah. Arah dari root menuju leaf disebut “down” dan sebaliknya disebut “up”. Perpindahan dari leaf menuju root dinamakan “climbing”, sedangkan perpindahan dari root menuju leaf dinamakan “descending”. Jika setiap node dalam binary tree selalu terdapat left dan right subtree, maka tree yang demikian dikatakan sebagai strictly binary tree seperti contoh pada gambar 2, sementara gambar 1 tidak dapat dikatakan sebagai strictly binary tree karena node C dan E masing-masing hanya memiliki satu son. A B
C D
F
E
G
Gambar 2, Strictly Binary Tree. Sebuah strictly binary tree dengan n leaf selalu terdapat 2n – 1 node. Perhatikan gambar 2, terdapat n = 4 leaf. Sehingga terdapat sebanyak (2 * 4) - 1 = 7 node. Level dari suatu node dalam binary tree didefinisikan dengan mengikuti suatu aturan bahwa : root dari sebuah tree berada pada level 0, kemudian level dibawahnya adalah level 1, dan seterusnya. Sebagai contoh, pada binary tree yang terdapat dalam gambar 2, A adalah root dan berada pada level 0, B dan C berada pada level 1, D dan E berada pada level 2, F dan G berada pada level 2. Depth (kedalaman) dari binary tree adalah level maksimum dari beberapa leaf di dalam tree. Jika suatu binary tree pada setiap nodenya (kecuali leaf) memiliki dua son, dan setiap subtree memiliki panjang path yang sama, maka yang demikian dikatakan sebagai complete binary tree (perhatikan gambar 3). Jika pada complete binary tree terdapat n node pada level l, kemudian depth binary tree adalah d, secara matematis dapat dirumuskan sebagai berikut :
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 3
d
tn 2 0 21 2 2 ...... 2 d 2 j j 0
dimana, tn mewakili total jumlah node, d mewakili depth suatu binary tree. A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
Gambar 3, Complete Binary Tree.
2.
Binary Search Tree Binary Search Tree adalah binary tree dengan sifat bahwa semua left son
harus lebih kecil daripada right son dan fathernya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching/pencarian node tertentu dalam binary tree.
2.1.
Operasi-operasi pada Binary Search Tree a. Melakukan setup sebuah tree yang kosong. b. Melakukan pengujian apakah sebuah tree kosong. c. Menambahkan node baru. d. Traverse, yaitu mengunjungi seluruh node pada tree, masing-masing sekali. Ada tiga cara traverse, yaitu : PreOrder, InOrder dan PostOrder e. Melakukan pencarian node dengan kunci pencarian node yang spesifik. f. Menghapus node yang telah dibuat. g. Melakukan akses pada node yang ditunjuk secara spesifik.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 4
Melakukan setup sebuah tree yang kosong, melakukan pengujian apakah sebuah tree kosong, dan menambahkan/menyisipkan node baru.
{ Deklarasi Binary Tree } type NodePtr = ^NodeRec; NodeRec = record value : integer; left, right : NodePtr; end; var root : NodePtr;
value
left
right
Program 1, Deklarasi Binary Tree
{ Insert Tree } procedure InsertTree(X:integer; Var StartNode : NodePtr); var NewEntry : NodePtr; begin if (StartNode=nil) then begin new(NewEntry); NewEntry^.value := X; NewEntry^.left := nil; NewEntry^.right := nil; StartNode := NewEntry; end else if (X < StartNode^.value) then InsertTree(X, StartNode^.left) else InsertTree(X, StartNode^.right); end;
Program 2, Procedure untuk menambah item/node kedalam binary tree.
{ Print Tree } procedure PrintTree(StartNode : NodePtr); begin if (StartNode<>nil) then begin PrintTree(StartNode^.left); writeln(StartNode^.value); PrintTree(StartNode^.right); end end;
Program 3, Procedure untuk mencetak binary tree
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 5
Traverse, yaitu mengunjungi seluruh node pada tree, secara PreOrder, InOrder dan PostOrder. PreOrder
:
cetak isi node yang dikunjungi, kunjungi left son, kunjungi right son.
InOrder
:
kunjungi left son, cetak isi node yang dikunjungi, kunjungi right son.
PostOrder
:
kunjungi left son, kunjungi right son, cetak isi node yang dikunjungi.
{ PreOrder } procedure PreOrder(Tree : NodePtr); begin if Tree<>nil then begin write(Tree^.value); PreOrder(Tree^.left); PreOrder(Tree^.right); end; end;
Program 4, Procedure untuk melakukan kunjungan secara PreOrder.
{ InOrder } procedure InOrder(Tree : NodePtr); begin if Tree<>nil then begin InOrder(Tree^.left); write(Tree^.value); InOrder(Tree^.right); end; end;
Program 5, Procedure untuk melakukan kunjungan secara InOrder.
{ PostOrder } procedure PostOrder(Tree : NodePtr; begin if Tree<>nil then begin PostOrder(Tree^.left); PostOrder(Tree^.right); write(Tree^.value); end; end;
Program 6, Procedure untuk melakukan kunjungan secara PostOrder. Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 6
Jika pelaksanaan InOrder dan PreOrder diketahui, maka binary tree bisa ditentukan, sehingga kunjungan secara PostOrder juga bisa ditentukan. Contoh 1 : jika diketahui PreOrder dan InOrder A B D G C PreOrder D G B A H InOrder
E E
H I
I C
F F
A B
C
D
E G
F
H
I
Gambar 4, Binary tree dan cara melakukan kunjungan PostOrder
G
D
B
H
I
Contoh 2 : jika diketahui InOrder dan PreOrder 10 20 30 40 50 InOrder 20 10 40 30 PreOrder 50
E
F
C
A
60 60
70 80
80 70
90 90
60
50
50 20
60
10
40
80
30
70
90
Gambar 5, Binary tree dan cara melakukan kunjungan PostOrder
10
30
40
20
70
90
80
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 7
Contoh 3 : jika diketahui InOrder dan PostOrder R A T B InOrder A R T U PostOrder
U S
S P
P B
B T
P
R
S A
U
Gambar 6, Binary tree dan cara melakukan kunjungan B
PreOrder
T
R
A
Contoh 4 : jika diketahui InOrder dan PostOrder B F H D A InOrder H F D B I PostOrder
P
E G
S
I E
U
G C
C A
G
I
A
B
C D
E
F
G H
I
Gambar 7, Binary tree dan cara melakukan kunjungan PreOrder
A
B
D
F
H
C
E
Jika diketahui secara PreOrder dan PostOrder ternyata binary tree tidak tunggal, sehingga sulit ditentukan . Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 8
Melakukan pencarian node dengan kunci pencarian node yang spesifik.
{ Search Tree } procedure SearchTree(x : integer; var Entry : NodePtr; var Found : boolean); begin Found := false; Entry := Root; while (not Found) and (Entry<>nil) do begin if (Entry^.value=x) then Found := true else begin if (x<Entry^.value) then Entry := Entry^.left else Entry := Entry^.right end end end;
Program 7, Searching pada Binary Tree
{ Find Position } procedure FindPosition(x: integer; var Entry : NodePtr; var Father : NodePtr; var Found : boolean); begin Found := false; Entry := Root; Father := nil; while (not Found) and (Entry <> nil) do begin if (Entry^.value=x) then Found := true else begin Father := Entry; If (x<Entry^.value) then Entry := Entry^.left else Entry := Entry^.right end end; end;
Program 8, Searching pada Binary Tree untuk menentukan posisi father.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 9
Menghapus node yang telah dibuat. Menghapus node merupakan operasi yang sangat kompleks, karena ketika node dihapus dari sebuah tree, descendant harus melakukan link kembali pada tree dengan posisi yang tepat. Untuk menghapus node, terlebih dahulu harus mengetahui father dari node.
{ Delete Tree } procedure DeleteEntry(var Entry, Father : NodePtr); var NewChild : NodePtr; begin if (Entry^.left=nil) then begin NewChild := Entry^.right; AlterParent(Father, Entry, NewChild) end else begin NewChild := Entry^.left; AlterParent(Father, Entry, NewChild) end else PromoteSuccessor(Entry) end; (a)
procedure AlterParent(var Father : NodePtr; Entry, NewChild : NodePtr); begin if (Father=nil) then Root := NewChild else if (Father^.left=Entry) then Father^.left := NewChild else Father^.right := NewChild end; (b)
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 10
procedure PromoteSuccessor (var Entry : NodePtr); var Successor, SuccParent : NodePtr; begin Successor := Entry^.right; SuccParent := Entry; while (Successor^.left <> nil) do begin SuccParent := Successor; Successor := Successor^.left; end; if (SuccParent=Entry) then Entry^.right := Successor^.right else Successor^.left := Successor^.right; Entry^.value := Successor^.value; end; (c)
Program 9, (a) menghapus node pada binary tree, (b) memindahkan kedudukan father/parent (c) procedure untuk mendapatkan successor pengganti.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 11
