Bab 13 tree tujuan



Download 200.11 Kb.
Page1/2
Date23.05.2020
Size200.11 Kb.
  1   2
BAB 13

TREE

    1. Tujuan

  1. Menjelaskan tentang pengertian Tree

  2. Menjelaskan istilah dalam Tree

  3. Menjelaskan sifat utama Tree



    1. Pengertian Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

Sebuah Binary Search Tree (BST) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. Value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree.

Struktur data BST sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita menggunakan list contigue dan melakukan pencarian biner, akan tetapi jika kita ingin melakukan perubahan isi list (insert atau delete), menggunakan list contigue akan sangat lambat, karena proses insert dan delete dalam list contigue butuh memindahkan linked-list, yang untuk operasi insert atau delete tinggal mengatur-atur pointer, akan tetapi pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata lain hanya secara squential.


    1. Binary Tree

Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya ( disebut subtree).

Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree. Binary tree adalah suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.



Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.

Gambar 13.1. Binary Tree

Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar.

Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan di atas dua anak bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yang tidak terkoneksi, membolehkan bermacam koneksi dalam komponen di grafik, kita memanggil struktur sebuah hutan.

Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti :


  1. Sebuah sudut tunggal.

  2. Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar dai setiap pohon biner.

Pohon biner dapat dikontruksi dari bahasa pemrograman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records dan referensi. Pohon biner secara khas dikontruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan.

Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak diaatur ke dalam nilai nol khusus atau kesebuah simpul sentinel.



Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, teristimewa selama sebuah preordeer traversal.

    1. Istilah Dalam Tree

Di bawah ini beberapa istilah dalam tree yang biasa digunakan:

      1. Predesesor

Node yang berada diatas node tertentu. (contoh : B predesesor dari E dan F)

  1. Succesor

Node yang berada dibawah node tertentu. (contoh : E dan F merupakan succesor dari B)

  1. Ancestor

Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. (contoh : A dan B merupakan ancestor dari F)

  1. Descendant

Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama. (contoh : F dan B merupakan ancestor dari A)

  1. Parent

Predesesor satu level diatas satu node. (contoh : B merupakan parent dari F)

  1. Child

Succesor satu level dibawah satu node. (contoh : F merupakan child dari B)

  1. Sibling

Node yang memiliki parent yang sama dengan satu node. (contoh : E dan F adalah sibling)

  1. Subtree

Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh : Subtree B, E, F dan Subtree D, G, H)

  1. Size

Banyaknya node dalam suatu tree. (contoh : gambar tree diatas memiliki size = 8)

  1. Height

Banyaknya tingkat/level dalam suatu tree. (contoh : gambar tree diatas memiliki height = 3)

  1. Root (Akar)

Node khusus dalam tree yang tidak memiliki predesesor (Contoh : A)

  1. Leaf (Daun)

Node-node dalam tree yang tidak memiliki daun. (contoh : Node E,F,C,G,H)

  1. Degree (Derajat)

Banyaknya child yang dimiliki oleh suatu node. (contoh : Node A memiliki derajat 3, node B memiliki derajat 2)

    1. Istilah pada Pohon Biner

  1. Pohon Biner Penuh (Full Binary Tree)

Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.



  1. Pohon Biner Lengkap (Complete Binary Tree)

Hampir sama dengan Pohon Biner Penuh, semua simpul (kecuali daun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.




  1. Share with your friends:
  1   2


The database is protected by copyright ©sckool.org 2019
send message

    Main page