pengertian tree pada struktur data

Assalamualaikum sobat

pada pembahasan kali ini, admin bocah ngoding akan berbagi pelajaran tenntang materi struktur data tree. dimana Tree adalah seperti pohon terbalik yang memiliki daun atau leaf, akar atau root dan lain-lain. dan biasanya tree juga dimanfaatkan oleh programmer untuk membuat sebuah data program yang berbentuk hirarki ataupun pencarian sebuah data. oke simak langsung yah sobat dan semoga bermanfaat..

Tree

Tree atau pohon merupakan struktur data yang tidak linear yang digunakan untuk mempresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root (akar) dan elemen yang lain disebut simpul ( node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu sama lain yang disebut sub-tree atau cabang.^[1]

Gambar 4.1 Ilustrasi tree

Tabel berikut menjelaskan beberapa istilah yang terdapat pada tree ^[7]:

Tabel 4 .1 Istilah-istilah pada treea. Jenis-jenis Tree

jenis jenis tree

1) Binary Tree

pengertian binary tree dalam struktur data

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. contoh implementasi binary tree.^[10]

Gambar 4.2 Ilustrasi binary tree

Jenis-jenis binary tree :

• Full Binary Tree

Full binary tree adalah binary tree yang tiap node-nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.^[7]

Gambar 4.3 Ilustrasi full binary tree

• Complete Binary Tree

Complete binary t ree adalah binary tree yang mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.^[7]

Gambar 4.4 Ilustrasi complete binary tree

• Skewed Binary Tree

Skewed binary t ree adalah binary tree yang semua node nya (kecuali leaf) hanya memiliki satu child.^[7]

Gambar 4.5 Ilustrasi skewed binary tree

• Binary search tree (BST)

Binary search t ree (BST) adalah jenis pohon terurut yang digunakan untuk menyimpan data sehingga memudahkan pencarian kembali data tersebut.^[10]

Gambar 4.6 Ilustrasi binary search tree

b. Operasi pada Tree^[1]

• Create

Create digunakan untuk membentuk binary tree baru yang masih kosong.

• Clear

Clear digunakan untuk mengosongkan binary tree yang sudah ada.

• Empty

Empty digunakan untuk memeriksa apakah binary tree masih kosong.

• Insert

Insert digunakan untuk memasukkan sebuah node ke dalam tree.

• Find

Find digunakan untuk mencari root, parent, left child , atau right child dari suatu node dengan syarat tree tidak boleh kosong.

•  Update

Update digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer current dengan syarat tree tidak boleh kosong.

• Retrieve

Retrieve digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

• Delete Sub

DeleteSub digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

• Characteristic

Characteristic digunakan untuk mengetahui karakteristik dari suatu tree, yakni size, height, serta average length-nya.

• Traverse

Traverse digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.

Tree Traversal

Tree traversal merupakan sebuah kunjungan yang berawal dari root, mengunjungi setiap node dalam tree masing-masing sekali. Kunjungan atau traversing dapat dilakukan dengan 3 cara yaitupre order, in order dan post order. ^[10]

a. Preorder

Algoritma preorder :

1. Mencetak info pada node yang dikunjungi.
2. Mengunjungi cabang kiri.
3. Mengunjungi cabang kanan.

b. Inorder

Algoritma inorder :

1. Mengunjungi cabang kiri.
2. Mencetak info pada node yang dikunjungi.
3. Mengunjungi cabang kanan.

c. Postorder

Algoritma postorder :

1.  Mengunjungi cabang kiri.
2. Mengunjungi cabang kanan.
3. Mencetak info pada node yang dikunjungi.
4. Breadth-first search (BFS) dan Depth-First-Search (DFS)

• Breadth-first search (BFS)

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hierarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.^[1]

Gambar 4.7 Ilustrasi breadth-first search

• Depth-First-Search (DFS)

Depth-First-Search (DFS) adalah salah satu algoritma penelusuran struktur tree berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya (misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri]), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam. Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya. ^[1]

Gambar 4.7 Ilustrasi deapth-first search (DFS)

algoritma & struktur dataMateri ITsemua

Share This :