Pohon Biner (Binary Tree) Matakuliah Struktur Data PDF

Preview

Summary

Pohon Biner (Binary Tree) Matakuliah Struktur Data Annisa Puspa Kirana Jurusan Teknik Elektro Universitas Negeri Malang 1 Overview – Tree – Contoh Penggunaan Tree – Terminologi – Sifat Utama Tree – Pohon Biner (Binary Tree) – Definsi , Deklarasi, Pembentukan Binary Tree, Langkah pembentukan – Operas...

Description

Pohon Biner (Binary Tree)

Matakuliah Struktur Data Annisa Puspa Kirana Jurusan Teknik Elektro Universitas Negeri Malang

1

Overview – Tree – Contoh Penggunaan Tree – Terminologi – Sifat Utama Tree

– Pohon Biner (Binary Tree) – Definsi , Deklarasi, Pembentukan Binary Tree, Langkah pembentukan

– Operasi Pohon BIner – Kunjungan : Metode Traversal –

Pre order, In order, Post order

– Binary Search Tree (BST)

2

– Definisi, algoritma, operasi, contoh

Pendahuluan Tree  Implementasi dari banyak liked list yang biasanya digunakan untuk menggambarkan hubungan yang berifat hirarkis antara elemen yang ada

 Struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan.  Node-node dihubungkan oleh sebuah vektor.  Setiap node dapat memiliki 0 atau lebih node anak (child).  Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk

3

 Tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya

Contoh Penggunaan Tree

4

Terminologi dalam Tree

5

Sifat Utama Tree  Jika simpul mempunyai simpul sebanyak n maka banyaknya ruas/edge sebanyak (n-1)

 Mempunyai simpul khusus yang disebut root. Simpul tersebut memiliki derajat keluar sebesar ≥ 0 dan derajat masuk = 0  Mempunyai simpul yang disebut leaf (daun) jika simpul tersebut berderajat masuk = 1 dan berderajat keluar = 0  Setiap simpul mempunyai tingkatan/level yang diulai dari root yang levelnya 1 sampai dengan level ke - n pada daun paling bawah. Simpul yang mempunyai level sama disebut bersaudara/brother/sibling.

6

Tingkat (Level) dan Kedalaman (Depth) Pohon  

Tingkat dimulai dari 0, 1, 2 dst Kedalaman dimulai dari 1, 2, 3, dst (tingkat + 1) TINGKAT 0 TINGKAT 1

TINGKAT 2 TINGKAT 3

7

Node Internal dan Eksternal Node Internal = node yang memiliki anak Node eksternal = node yang tidak memiliki anak (daun)

Node Internal Node Internal Node Eksternal

8

Diskusi Kelompok I Diketahui tree sebagai berikut.

9

– Ditanyakan a) b) c) d) e) f) g) h) i) j) k) l)

Ancestor (F)? Predesesor (F) ? Descendant (B)? Succesor (B)? Parent (I)? Child (C)? Sibling (G)? Size? Height? Root? Leaf? Degree (C)?

Pohon Biner (Binary Tree) – Sebuah pengorganisasian secara hirarki dari beberapa buah node, dimana masing-masing node tidak memiliki child lebih dari 2

– Implementasi binary tree bisa dilakukan menggunakan struktur data linked list. Masing-masing node terdiri dari tiga bagian yaitu sebuah data/info dan dua buah pointer yang dinamakan pointer kiri kanan

10

Balanced and Unbalanced Binary Tree – Balanced Binary Tree → Setiap level diatas level yang paling rendah terisi penuh – Unbalanced Binary Tree → Jika tree tidak memenuhi kaidah balanced – Kebanyakan aplikasi menginginkan suatu tree yang seimbang

11

Jumlah Maksimal Node Jumlah maksimum node pada setiap tingkat adalah 2n

12

Pembentukan Binary Tree – Perlu memperhatikan kapan suatu node perlu dipasang sebagai node kiri atau node kanan – Misalnya : – Ditentukan, node yang berisi info nilai lebih besar dari parent ditaruh disebelah kanan dan yang lebih kecil ditaruh disebelah kiri

13

Langkah – Langkah Pembentukan Binary Tree

14

Algoritma Pembentukan Binary Tree 1. Buat node baru (new)

15

Operasi pada Pohon Biner 1. Deklarasi 2. Pengecekkan kosong (isEmpty) 3. Penambahan node 4. Traversal (penelusuran node/kunjungan)

16

Deklarasi Binary Tree – Node sebuah binary tree di deklarasikan sebagai berikut – Contoh script deklarasi sebagai berikut

17

isEmpty – Digunakan untuk mengecek binary tree dalam kondisi kosong atau tidak. – Pengecekan dilakukan pada variabel root. – Jika root menunjuk null, kondisi kosong dan mengembalikan nilai true. Sebaliknya, jika root tidak menunjuk null berarti kondisi binary tree tidak kosong dan mengembalikan nilai false. – Contoh deklarasi program → pengecekan kosong static boolean isEmpty() { return (root==null); }

18

Penambahan Node – Untuk melakukan penambahan node, terlebih dahulu harus di-create node baru.

Node x = new Node(data); – Ketika ada penambahan node terjadi increment nilai pada variabel size. static void addNode(Node2P baru, Node2P kiri, Node2P kanan) { baru.next = kanan; baru.previous = kiri; size++; }

19

setRoot – Digunakan untuk menandai node mana yang dijadikan sebagai root.

static void setRoot(Node2P r) { root = r; }

20

Metode Traversal – Salah satu operasi yang paling umum dilakukan pada sebuah tree adalah kunjungan – Sebuah kunjungan berawal dari root, mengunjungi setiap node tree tersebut tepat hanya sekali – Mengunjungi artinya memproses data/info pada node yang bersangkutan – Penelusuran (traversal) digunakan untuk menelusuri node pada binary tree satu per-satu.

21

Metode Tranversal Cont… – Terdiri dari 3 metode traversal : – 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. – Ketiga macam kunjungan diatas dilakukan secara rekursif

22

PreOrder (SLR) Traversal –

Preorder traversal

/

1. Cetak data pada root

2. Secara rekursif mencetak seluruh data pada subpohon kiri 3. Secara rekursif mencetak seluruh data pada subpohon kanan a

+

* e +

f

b

c

d

/ * + a b - c d + e f

23

Gives prefix form of expression!

Preorder Traversal (visit = print) a

a b

b

c

g

f

e

d a b c

c

h

i

a b d g h e i c f j

24

j

Algoritma Pre Order Traversal

25

InOrder (LSR) Traversal 1. Secara rekursif mencetak seluruh data pada subpohon kiri 2. Cetak data pada root 3. Secara rekursif mencetak seluruh data pada subpohon kanan

Algoritma

26

Inorder Traversal (visit = print) a

a b

b c g

f

e

d

b a c

c

h

i g d h b e i a j f c

27

j

Implementasi InOrder Traversal

28

Postorder (LRS) Traversal 1. Secara rekursif mencetak seluruh data pada subpohon kiri 2. Secara rekursif mencetak seluruh data pada subpohon kanan 3. Cetak data pada root

Algoritma

29

Postorder Traversal (visit = print) a a b b

b c a

c

c e

d g

f

h

i g h d i e b j f c a

30

j

Postorder of Expression Tree /

+

* e + a

b

c

d

a b + c d - * e f + /

31

Gives postfix form of expression!

f

Implementasi Postorder Traversal

32

Traversal Overview Dari hasil di atas dapat disimpulkan bahwa : – Kunjungan secara PreOrder akan menghasilkan notasi Prefix – Kunjungan secara InOrder akan menghasilkan notasi Infix – Kunjungan secara PostOrder akan menghasilkan notasi Postfix

33

Infix, Prefix, Postfix

34

Diskusi Kelompok II 1. PreOrder ? 2. InOrder

?

3. PostOrder ?

35

Diskusi Kelompok III * -

+

a

d

/

* e

b

36

c

1. PreOrder ? 2. InOrder ? 3. PostOrder ? f

Binary Search Tree (BST) – Pemakaian tree terstruktur dalam proses pencarian – Disebut juga Ordered Binary tree yaitu binary tree yang seluruh children dari tiap node terurut. – Sifat Binary Tree: Pada sebuah node x, – Elemen yang berada di LEFT sub-tree selalu lebih KECIL daripada x – Elemen yang berada di RIGHT sub-tree selalu lebih BESAR atau SAMA DENGAN daripada x

- Binary Search Tree: proses pencarian (SEARCHING) berbasis binary tree

37

Operasi Binary Search Tree (BST) 1. Traversal 2. Search (Pencarian) 3. Insertion (Penambahan) 4. Deletion (Penghapusan)

38

Contoh Binary Search Tree (BST)

39

Traversal BST SLR

LRS LSR

40

Searches BST Contoh Sukses

41

Contoh Gagal

Algoritma Search BST

42

Mencari Nilai Terkecil BST

43

Mencari Nilai Terbesar BST

44

Insertion BST – Penambahan node pada BST harus mengikuti aturan minMax, dimana node yang bernilai lebih kecil dari root diletakkan pada subtree sebelah kiri sedangkan node yang bernilai lebih besar diletakkan pada subtree sebelah kanan.

– Jika ada nilai yang sama maka node tersebut di-overwrite.

45

Contoh Insertion BST

46

Contoh Insertion BST Cont…

47

Algoritma Insertion BST

48

Deletion BST – Proses penghapusan data pada binary search tree lebih rumit daripada proses searching maupun proses insertion – Tahapan: 1. Carilah node yang akan dihapus 2. Apabila node tersebut leaf (tidak mempunyai anak), hapuslah node tersebut

49

Deletion BST Cont… – Bila node tersebut memiliki 1 anak, setelah node dihapus, anaknya menggantikan posisi orangtuanya (node yang dihapus)

50

Penhapusan Node Daun (Node 35) 20

10

6

2

15

8

7

40

30

18

25

35

Remove a leaf element. key = 35

Penghapusan Node Ber-degree 1 (Node 40) 20

10

6

2

52

15

8

7

40

30

18

25

35

Remove from a degree 1 node. key = 40

Deletion BST Cont… – Bila node tersebut memiliki 2 anak – Setelah node dihapus, gantikan node tersebut dengan elemen terkecil dari right sub-tree ATAU elemen terbesar dari left sub-tree

53

Deletion BST Cont…

54

Diskusi Kelompok IV – Delete 32? – Delete 34? – Delete 50?

55

Diskusi Kelompok V (BST) Diketahui data tersusun 6, 4, 3, 2, 1, 9, 10, 12, 15. Bangunlah tree dengan BST

56

Daftar Pustaka – Kadir, Abdul. 2013. Teori dan Aplikasi Struktur Data menggunakan C++. Yogyakarta : Penerbit ANDI

– Sartaj Sahni. Data Structures & Algorithms. Presentation L20-24. – Mitchell Waite. 2001. Data Structures & Algorithms in Java. SAMS.

57...