tree

Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 1
TREE
Definisi
Merupakan salah satu bentuk struktur data non-linear yang menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen. Tree dapat juga didefinisi-kan 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 descendant-nya 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 2
Contoh :
Subtree Root Keterangan :
Ancestor (H) = F,C,A
Descendant (F) = H,I
Father (D) = B
Son (A) = B,C
Sibling (D) = E
Size = 9
Height = 4
Root = A
Leaf = D,G,H,I
Degree (E) = 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
A
D E F
C
I
G H
B
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 3
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.
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 :
A
B
C
D
E
F
G
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 4

     
d
j
d j tn
0
0 1 2 2 2 2 ...... 2 2
dimana, tn mewakili total jumlah node, d mewakili depth suatu binary tree.
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.
A
B
D E
H I J K
C
F G
L M N O
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 5
 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;
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
value
left
right
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 6
 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 7
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
PreOrder
A
B
D
G
C
E
H
I
F
InOrder
D
G
B
A
H
E
I
C
F
Gambar 4, Binary tree dan cara melakukan kunjungan
PostOrder
G
D
B
H
I
E
F
C
A
Contoh 2 : jika diketahui InOrder dan PreOrder
InOrder
10
20
30
40
50
60
70
80
90
PreOrder
50
20
10
40
30
60
80
70
90
Gambar 5, Binary tree dan cara melakukan kunjungan
PostOrder
10
30
40
20
70
90
80
60
50
A
B
D
G
C
E
I
F
H
50
20
60
80
40
10
90
70
30
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 8
Contoh 3 : jika diketahui InOrder dan PostOrder
InOrder
R
A
T
B
U
S
P
PostOrder
A
R
T
U
S
P
B
Gambar 6, Binary tree dan cara melakukan kunjungan
PreOrder
B
T
R
A
P
S
U
Contoh 4 : jika diketahui InOrder dan PostOrder
InOrder
B
F
H
D
A
E
I
G
C
PostOrder
H
F
D
B
I
G
E
C
A
Gambar 7, Binary tree dan cara melakukan kunjungan
PreOrder
A
B
D
F
H
C
E
G
I
Jika diketahui secara PreOrder dan PostOrder ternyata binary tree tidak tunggal, sehingga sulit ditentukan .
B
T
R
A
P
S
U
A
B
C
D
E
G
F
H
I
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 9
 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 10
 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 11
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.