pohon biner · penelusuran pohon biner preorder untuk penelusuran preorder, urutannya adalah :...

Pohon Biner

Membaca Pohon

Membaca pohon biner dapat dilakukan dengan dua cara :

1. Membaca pohon biner level per level urut nomor simpul.

2. Membaca atau mencari sebuah simpul dengan nomor tertentu.

Membaca pohon biner level per level urut nomor simpul

Perhatikan Pohon biner berikut :

Membaca pohon biner level per level urut nomor simpul

Pohon biner tersebut bila dibaca dan dicetak simpul persimpul, dengan pembacaan level per level urutnomor simpul, maka :

A B C D E F G H I J K L M N O P Q

Membaca pohon biner level per level urut nomor simpul

Perhatikan Pohon biner berikut :

Membaca pohon biner level per level urut nomor simpul

Pohon biner tersebut bila dibaca dan dicetaksimpul per simpul, dengan pembacaan levelper level urut nomor simpul, maka :

A B C D E G I J K N

Membaca pohon biner level per level urut nomor simpul

• Perhatikan Pohon biner berikut :

Membaca pohon biner level per level urut nomor simpul

Pohon biner tersebut bila dibaca dan dicetaksimpul per simpul, dengan pembacaan levelper level urut nomor simpul, maka :

A B C E F G J K M N

Membaca pohon biner level per level urut nomor simpul

• Perhatikan Pohon biner berikut :

Membaca pohon biner level per level urut nomor simpul

Pohon biner tersebut bila dibaca dan dicetaksimpul per simpul, dengan pembacaan levelper level urut nomor simpul, maka :

A B C E J K

Membaca atau mencari sebuah simpul dengan nomor tertentu

Contoh :

Jika ada sebuah pohon biner, jumlah simpul dan kedalaman pohon tidak diketahui.

Penelusuran Pohon Biner

Penelusuran (traverse atau traserval) pohonbiner, maksudnya membaca atau mengunjungi(visit) simpul – simpul pohon biner denganurutan tertentu. Ada tiga macam penelusuranyang apabila ditambah dengan kebalikannyamenjadi enam penelusuran sebagai berikut :

Penelusuran Pohon Biner

1. Preorder (atau depth – first order)

2. Inorder

3. Postorder

4. Inverse Preorder

5. Inverse Inorder

6. Inverse Postorder

Penelusuran Pohon Biner Preorder

Untuk penelusuran Preorder, urutannya adalah :ambil akar, kemudian telusuri secara preordersubpohon kiri, dan setelah selesaipenelusuran ke subpohon kiri, kemudiandilanjutkan dengan penelusuran secarapreorder ke subpohon kanan. Jadipenelusuran sendiri bersifat recursive.

Penelusuran Pohon

Agar mudah diingat, prosesnya ketiganya dapat disingkat sebagai berikut :

Untuk Preorder AKAR, KIRI, KANAN

Untuk Inorder KIRI, AKAR, KANAN

Untuk Postorder KIRI, KANAN, AKAR

Penelusuran Pohon Biner Preorder

• Perhatikan Pohon biner berikut :

Penelusuran Preorder A B C

Penelusuran Pohon Biner Inorder

• Perhatikan Pohon biner berikut :

Penelusuran Inorder B A C

Penelusuran Pohon Biner Postorder

• Perhatikan Pohon biner berikut :

Penelusuran Postorder B C A

Penelusuran Pohon Biner

• Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.

Penelusuran Pohon Biner

Untuk Pre AKAR, KIRI, KANAN

Untuk In KIRI, AKAR, KANAN

Untuk Post KIRI, KANAN, AKAR

• Pre : A B D E C F

• In : D B E A F C

• Post : D E B F C A

Latihan Penelusuran1

1. Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.

Jawab

Untuk Pre AKAR, KIRI, KANAN

Untuk In KIRI, AKAR, KANAN

Untuk Post KIRI, KANAN, AKAR

• Pre : A B D H E J K C F M G

• In : H D B J E K A F M C G

• Post : H D J K E B M F G C A

Latihan Penelusuran2

1. Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.

Jawab :

Untuk Pre AKAR, KIRI, KANAN

Untuk In KIRI, AKAR, KANAN

Untuk Post KIRI, KANAN, AKAR

• Pre : A B D H E J K V W C F M G

• In : H D B J E V K W A F M C G

• Post : H D J V W K E B M F G C A

Pohon Pencarian – Biner (Binary Search Tree)

• Dari definisi pohon binary search terlihatbahwa pada setiap simpul, maka simpulcabang kiri (left) nilainya lebih kecil dari akar,sedangkan simpul cabang kanan (right)nilainya lebih besar atau sama dengan simpulakar.

Pohon Pencarian – Biner (Binary Search Tree)

• Sama dengan pohon pada umumnya, makasimpul pertama yang dibuat adalah simpulakar. Untuk data yang sama, maka bentukpohon binary search akan berbeda bila urutanpemasukan data berbeda.

Pohon Pencarian – Biner (Binary Search Tree)

Bila urutan data yang diinput :

60 44 75 20 55 66 84

75 60 84 44 66 20 55

44 20 60 55 75 66 84

Pohon Pencarian – Biner (Binary Search Tree)

a. Bila urutan data yang diinput :

60 44 75 20 55 66 84

Maka gambar Binary Search Tree – nya adalah

Hasil Penelusuran Inorder : 20 44 55 60 66 75 84

Pohon Pencarian – Biner (Binary Search Tree)

b. Bila urutan data yang diinput :

75 60 84 44 66 20 55

Maka gambar Binary Search Tree – nya adalah

Hasil Penelusuran Inorder : 20 44 55 60 66 75 84

Pohon Pencarian – Biner (Binary Search Tree)

c. Bila urutan data yang diinput :

44 20 60 55 75 66 84

Maka gambar Binary Search Tree – nya adalah

Hasil Penelusuran Inorder : 20 44 55 60 66 75 84

Pohon Pencarian – Biner (Binary Search Tree)

• Bila urutan data yang diinput :

60 44 75 66 20 55 84

Maka gambar Binary Search Tree – nya adalah

Hasil penelusuran Inorder : 20 44 66 60 55 75 84

Penelusuran / Pencarian Biner

• Kekhususan Binary Search Tree (BST) adalah kalau ditelusuri secara inorder, maka hasilnya berupa nilai urut menaik (ascending).

Penelusuran / Pencarian Biner

• Penelusuran secara Inorder : 20 44 50 55 60

Penelusuran / Pencarian Biner

• Penelusuran secara Inorder : 20 44 50 52 55 58 60 66 75 80 84

Penelusuran / Pencarian Biner

• Penelusuran secara Inorder : 60 66 75 80 84 86 90 96

Penelusuran / Pencarian Biner

• Penelusuran secara Inorder : 60 75 84 90 96

Penelusuran / Pencarian Biner

• Binary Search Tree dibuat dengan tujuan agar dalam pencarian data, atau penelusuran dapat dilakukan pencarian secara biner.

• Pencarian atau penelusuran secara binermaksudnya seluruh data yang akan ditelusuri,dikelompokkan menjadi dua kelompok.Kemudian data dicari hanya pada salah satukelompok yang diperkirakan data tersebutada.

Menghapus sebuah simpul pada BST

Simpul sebuah pohon biner dapat dihapus.

Menghapus sebuah simpul memang dapatmembuat pohon tersebut tidak seimbang.

Terlepas dari kondisi tersebut, prosesmenghapus sebuah simpul dalam pohon bineradalah :

Menghapus sebuah simpul pada BST

a. Apabila yang dihapus adalah simpul daun, takperlu dilakukan penyesuaian

b. Bila simpul yang dihapus mempunyai hanya satucabang, baik kiri maupun kanan, hanya anaksimpul tersebut diangkat keatas menggantikansimpul yang dihapus.

c. Bila simpul yang dihapus mempunyai cabang kiridan cabang kanan, maka simpul sucessor dalamurutan inorder yang akan menggantikan simpulyang dihapus.

Menghapus sebuah simpul pada BST

• Perhatikan Pohon Biner berikut

Menghapus sebuah simpul pada BST

• Bila simpul 50 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 50 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 20 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 20 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 71 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 71 yang dihapus tak perlupenyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 75 yang dihapus perlu penyesuaian

Menghapus sebuah simpul pada BST

• Bila simpul 75 yang dihapus perlu penyesuaian

Menghapus sebuah simpul pada BST

• Simpul 80, yang menggantikan 75, karenasecara inorder, 80 adalah successor dari 75(sesudah 75 adalah 80)

Menghapus sebuah simpul pada BST

• Bila simpul 60 yang dihapus.

Menghapus sebuah simpul pada BST

• Bila simpul 60 yang dihapus.

Menghapus sebuah simpul pada BST

• Simpul 71 yang akan menggantikan 60 karenasecara inorder, 71 adalah successor darisimpul 60

Menghapus sebuah simpul pada BST

• Bila simpul 84 yang dihapus

Menghapus sebuah simpul pada BST

• Bila simpul 84 yang dihapus

Menghapus sebuah simpul pada BST

• Simpul 90 yang akan menggantikan 84 karenasecara inorder, 90 adalah successor darisimpul 84

Ada Pertanyaan???

Tugas

Perhatikan Pohon Biner Berikut :

Tugas

1. Bacalah pohon biner tersebut simpul persimpul, dengan pembacaan level per levelurut nomor simpul.

2. Buatlah penelusuran Preorder, Inorder, danPostorder.

Jawab

1. Membaca Pohon Biner Secara Urut Level Per Level :

A B C D E F G H J K M V W

2. Penelusuran

a. Pre : A B D H E J K V W C F M G

b. In : H D B J E V K W A F M C G

c. Post : H D J V W K E B M F G C A

Tugas

Perhatikan Pohon binary search berikut :

Tugas

3. Buatlah penelusuran BST tersebut secara :

a. Preorder

b. Inorder

c. Post Order

Jawab

3. Buatlah penelusuran BST tersebut secara :

a. Preorder

66 54 50 62 55 84 75 95

b. Inorder

50 54 55 62 66 75 84 95

c. PostOrder

50 55 62 54 75 95 84 66

Tugas

Perhatikan Pohon binary search berikut :

Tugas

4. Berdasarkan BST tersebut, maka andadiminta untuk membuat BST penyesuaianjika :

a. Simpul 84 dihapus

b. Simpul 50 dihapus

c. Simpul 66 dihapus

Jawab

4. Menghapus simpul di BST

a. Hapus simpul 84

Jawab

4. Menghapus simpul di BST

b. Hapus simpul 50

Jawab

4. Menghapus simpul di BST

c. Hapus simpul 66