BAB XI Manipulasi Binary Tree

www.hansmichael.com - Bab XI. Manipulasi Binary Tree

BAB XI Manipulasi Binary Tree 11.1 11.2 11.3 11.4 11.5

Insert Node Search Node Delete Node Copy Tree Latihan Soal

Binary tree seringkali diterapkan dalam proses searching, sehingga binary tree juga disebut sebagai binary search tree. Konsep dasar binary search tree yaitu bahwa child kiri lebih kecil dari root dan child kanan lebih besar dari root. Agar dapat melaksanakan konsep ini, maka perlu dipahami proses manipulasi binary tree sebagai binary search tree, yaitu insert node, delete node, search node dan copy node.

11.1 Insert Node Proses manipulasi pada binary tree yang pertama kali perlu diketahui adalah proses insert node. Sebelum menginsertkan sebuah node, node yang akan diinsertkan perlu dibuat terlebih dahulu. Proses pembuatan sebuah node baru adalah sebagai berikut: mengalokasikan memori untuk node tersebut dengan fungsi New, dan selanjutnya menginisialisasi node tersebut dengan memasukkan data atau info pada NewNode^.Info dan nilai nil pada NewNode^.LPtr serta NewNode^.RPtr. Berikut ini diberikan sebuah function Create_Node yang berfungsi membuat node baru sesuai dengan langkah-langkah yang telah diberikan. 1:

FUNCTION Create_Node(X: BinInfoType): BinTreeType; {Membuat node baru dan mengembalikan pointer dari node baru tersebut} 2: VAR 3: NewNode: BinTreeType; 4: BEGIN 5: New(NewNode); 6: WITH NewNode^ DO 7: BEGIN 8: LPtr := NIL; Program 11.1 Function untuk Membuat Sebuah Node Baru 99


9: 10: 11: 12: 13:

100

Info := X; RPtr := NIL; END; CreateNode := NewNode; END; Program 11.1 Function untuk Membuat Sebuah Node Baru (Lanjutan)

Untuk menginsertkan sebuah node baru ke dalam binary tree dapat dilakukan dengan dua cara, yaitu secara iteratif dan rekursif. Algoritma umum proses insert node secara iteratif adalah sebagai berikut: 1. Jika tree masih kosong (tidak mengandung node) maka arahkan root ke node tersebut dan keluar. 2. Mengarahkan pointer ke alamat node root. 3. Ulangi langkah 4 selama lokasi yang diproses belum kosong. 4. Jika X atau Info yang baru lebih kecil dari node yang diproses maka: a) Jika subtree kiri dari node yang diproses tidak kosong maka arahkan pointer pada node sebelah kiri dari node yang diproses. b) Jika tidak, maka insertkan node baru pada subtree kiri dari node yang diproses dan keluar. 5. Jika X atau Info yang baru lebih besar dari node yang diproses maka: a) Jika subtree kanan dari node yang diproses tidak kosong maka arahkan pointer pada node sebelah kanan dari node yang diproses. b) Jika tidak, maka insertkan node baru pada subtree kanan dari node yang diproses dan keluar. 6. Jika X atau Info yang baru sama dengan node yang diproses maka terjadi duplikasi data. Untuk lebih jelasnya, berikut ini diberikan procedure lengkap untuk proses insert node secara iteratif. 1:

2: 3:

PROCEDURE Insert(VAR Found:Boolean);

Root:BinTreeType;X:BinInfoType;VAR

{Proses insert node pada binary tree} VAR T,NewNode: BinTreeType; Program 11.2 Procedure Insert Secara Iteratif

101


4: 5: 6: 7:

Finish : Boolean; BEGIN Found := False; NewNode := Create_Node(X); {membuat node baru}

8:

IF Root = NIL THEN

9:

Root := NewNode

{jika empty tree} { maka head = newnode} 10:

ELSE

11:

BEGIN

{jika bukan empty tree} {inisialisasi} 12: 13: 14: 15:

T := Root; Finish := False; WHILE NOT Finish DO BEGIN {kasus 1: insert di subtree kiri}

16: 17: 18: 19: 20: 21: 22: 23:

IF X < T^.Info THEN IF T^.LPtr <> NIL THEN T := T^.LPtr ELSE BEGIN T^.LPtr := NewNode; Finish := True; END

24: 25: 26: 27: 28: 29: 30: 31: 32: 33:

ELSE IF X > T^.Info THEN IF T^.RPtr <> NIL THEN T := T^.RPtr ELSE BEGIN T^.RPtr := NewNode; Finish := True; END ELSE

{kasus 2: insert di subtree kanan}

{kasus 3: duplikasi data} 34: 35: 36: 37: 38: 39: 40:

BEGIN Finish := True; Found := True; END; END; END; END; Program 11.2 Procedure Insert Secara Iteratif (Lanjutan)

Setelah mengerti proses insert node secara iteratif, berikut ini akan dijelaskan mengenai proses rekursifnya. Prinsip rekursif diterapkan untuk melakukan proses insert node pada subtree kiri atau kanan dengan sebuah


102

pandangan bahwa subtree juga merupakan sebuah tree. Dengan menggunakan prinsip rekursif, maka algoritma umum insert node adalah sebagai berikut 1. Jika tree masih kosong maka arahkan root ke node tersebut dan keluar. 2. Jika X atau Info yang baru lebih kecil dari info dari node yang diproses maka insertkan node baru tersebut ke subtree kiri dari node yang diproses (secara rekursif). 3. Jika X atau Info yang baru lebih besar dari info dari node yang diproses maka insertkan node baru tersebut ke subtree kanan dari node yang diproses (secara rekursif). 4. Jika X atau Info yang baru sama dengan info dari node yang diproses maka terjadi duplikasi data. Berdasarkan algoritma tersebut, maka dapat disusun procedure Insert secara rekursif pada program 11.3. 1:

2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:

PROCEDURE Insert(VAR Root: BinTreeType; X: BinInfoType; VAR Found: Boolean); {Insert node pada binary tree secara rekursif} BEGIN {kasus 1: create node pada root -> pemberhenti rekursif} IF Root = NIL THEN BEGIN Root := Create_Node(X); Found := False; END ELSE {kasus 2: insert di subtree kiri -> rekursif} IF X < Root^.LPtr THEN Insert(Root^.LPtr,X,Found) ELSE {kasus 3: insert di subtree kanan -> rekursif} IF X > Root^.RPtr THEN Insert(Root^.RPtr,X,Found) ELSE {kasus 4: duplikasi data} Found := True; END; Program 11.3 Procedure Insert Secara Rekursif

Dengan melihat proses rekursif dari insert node pada binary tree, ternyata rekursif lebih mudah dibandingkan iteratif, namun mempunyai kelemahan yaitu membutuhkan stack yang cukup besar untuk melakukan proses rekursif.


103

11.2 Search Node Operasi selanjutnya yang perlu dipelajari adalah operasi search node pada binary tree. Proses searching ini dapat dilakukan secara iteratif dan dapat pula secara rekursif, seperti halnya pada proses insert node. Pada bagian ini hanya dijelaskan proses rekursifnya saja. Prinsip rekursif dari proses searching adalah sebagai berikut: jika informasi root tidak sama dengan yang diinginkan maka carilah (secara rekursif) pada subtree kiri jika informasi yang diinginkan lebih kecil dari root, dan carilah (secara rekursif) pada subtree kanan jika informasi yang diinginkan lebih besar dari root. Dengan prinsip tersebut, dapat dibuat sebuah procedure Search_Node (program 11.4). 1:

2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:

PROCEDURE Search_Node(Root: BinTreeType; X: BinInfoType; VAR Location: BinTreeType; VAR Found: Boolean); {Mencari node dengan info X dan menghasilkan Location jika ditemukan. Jika ditemukan maka Found berisi True dan jika tidak maka Found berisi False.} BEGIN {kasus 1: data tidak ketemu} IF Root = NIL THEN Found := False ELSE {kasus 2: data ketemu} IF X = Root^.Info THEN BEGIN Location := Root; Found := True; END ELSE {kasus 3: pencarian pada subtree kiri} IF X < Root^.Info THEN Search_Node(Root^.LPtr,X,Location,Found) ELSE {kasus 4: pencarian pada subtree kanan} Search_Node(Root^.RPtr,X,Location,Found); END; Program 11.4 Procedure Search Suatu Node

11.3 Delete Node Operasi lainnya yang dapat diterapkan pada binary tree adalah proses penghapusan (delete) sebuah node. Proses delete ini dapat dilakukan untuk setiap node dalam binary tree, termasuk root.


104

Algoritma umum delete node secara rekursif adalah sebagai berikut: 1. Jika Root = nil maka node tersebut tidak ditemukan. 2. Jika X atau Info yang akan dihapus lebih kecil dari Root^.Info maka lakukan penghapusan Info pada subtree kiri dari Root. 3. Jika X atau Info yang akan dihapus lebih besar dari Root^.Info maka lakukan penghapusan Info pada subtree kanan dari Root. 4. Jika X atau Info yang akan dihapus sama dengan Root^.Info maka: a) Jika Root tersebut merupakan leaf, maka hapuslah Root tersebut dan jadikan Root = NIL. b) Jika Root tersebut tidak mempunyai subtree kanan maka: P = Root, Root = Root^.RPtr, dan hapuslah P. c) Jika Root tersebut mempunyai subtree kanan maka: i)

Carilah inorder successor dari node Root. Inorder successor dari node x adalah node setelah node x menurut traversal inorder.

ii)

Gantilah informasi pada Root dengan informasi dari inorder successornya.

iii) Hapuslah node inorder successor Root dengan rootnya adalah Root^.RPtr. Untuk lebih jelasnya dapat dilihat pada procedure Delete (program 11.5) dalam bahasa pemrograman Pascal. 1:

2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

PROCEDURE Delete(VAR Root: BinTreeType; X: BinInfoType; VAR Found: Boolean); {Delete node X pada binary tree} VAR P: BinTreeType; BEGIN {kasus 1: empty tree} IF Root = NIL THEN Found := False ELSE {kasus 2: pencarian pada subtree kiri} IF X < Root^.Info THEN Delete(Root^.LPtr,X,Found) ELSE {kasus 3: pencarian pada subtree kanan} IF X > Root^.Info THEN Program 11.5 Procedure Delete Suatu Node


12: 13: 14:

15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37:

105

Delete(Root^.RPtr,X,Found) ELSE BEGIN {kasus 4: pencarian ketemu, melakukan delete node} Found := True; {kasus 4a: merupakan leaf} IF (Root^.LPtr = NIL) AND (Root^.RPtr = NIL) THEN BEGIN Root := NIL; Dispose(Root); END ELSE {kasus 4b: tidak mempunyai subtree kanan} IF Root^.RPtr = NIL THEN BEGIN P := Root; Root := Root^.LPtr; Dispose(P); END ELSE {kasus 4c: mempunyai subtree kanan} BEGIN {mencari inorder successor} P := Root^.RPtr; WHILE P^.LPtr <> NIL DO P := P^.LPtr; Root^.Info := P^.Info; {menghapus inorder successor} Delete(Root^.RPtr,P,Found); END; END; END; Program 11.5 Procedure Delete Suatu Node (Lanjutan)

11.4 Copy Tree Operasi terakhir yang dibahas adalah operasi penggandaan (copy) sebuah binary tree. Operasi copy ini terutama berguna bila akan dilakukan suatu operasi yang akan menghancurkan atau mengubah tree tersebut, sehingga perlu dibuat duplikatnya. Berikut ini diberikan algoritma umum yang menjalankan proses penggandaan sebuah binary tree secara rekursif. 1. Jika tree kosong, maka kembalikanlah nilai nil. 2. Membuat node baru dan menyalin informasi dari node yang akan digandakan.


106

3. Menyalinkan subtree kiri dan kanan dari node yang akan digandakan ke subtree kiri dan kanan dari node baru (secara rekursif). 4. Mengembalikan alamat dari node baru. 1:

2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:

FUNCTION Copy_BinTree(T: BinTreeType): BinTreeType; {Menyalinkan binary tree T ke binary tree baru dan mengembalikan alamatnya} VAR NewNode: BinTreeType; BEGIN {langkah 1: check apakah empty tree} IF T = NIL THEN Copy_BinTree := NIL ELSE BEGIN {langkah 2: membuat node baru dan menyalin informasi node} New(NewNode); NewNode^.Info := T^.Info; {langkah 3: menyalinkan subtree kiri dan kanan} NewNode^.LPtr := Copy_BinTree(T^.LPtr); NewNode^.RPtr := Copy_BinTree(T^.RPtr); {langkah 4: mengembalikan alamat node baru} Copy_BinTree := NewNode; END; END; Program 11.6 Procedure Untuk Menggandakan Suatu Binary Tree

11.5 Latihan Soal 1. Buatlah sebuah function untuk membandingkan dua buah binary tree yang akan mengembalikan nilai true jika sama dan false jika tidak sama. 2. Buatlah sebuah procedure yang melakukan searching node pada binary tree secara iteratif. 3. Buatlah sebuah procedure untuk mencari node predecessor secara inorder dari sebuah node pada binary tree. 4. Buatlah sebuah procedure untuk membalik sebuah binary tree, child kiri menjadi child kanan dan sebaliknya. 5. Buatlah sebuah procedure untuk menghapus semua node pada level tertentu dari sebuah binary tree. Catatan: Nomor level merupakan parameter input. 6. Ada sebuah metode lain untuk menghapus sebuah node pada suatu binary tree. Pada setiap node mempunyai sebuah flag yang akan diset true jika dinyatakan


107

dihapus. Jadi, proses menghapus sebuah node yaitu mengganti flag dari node tersebut menjadi true. Jika ternyata jumlah node yang flagnya diset true lebih dari 50%, maka perlu diorganisasi ulang. a) Buatlah sebuah function Test untuk menguji apakah binary tree tersebut telah melampaui batas maksimum dari jumlah node yang flagnya diset true. b) Buatlah sebuah procedure Reorganize untuk melakukan organisasi ulang yang akan menghapus secara fisik semua node yang flagnya diset true. Catatan: tidak boleh membentuk node baru.

BAB XI Manipulasi Binary Tree

Recommend Documents