Pengenalan Pohon

Semester ini saya mendapatkan matakuliah baru dan kebetulan saya tidak pernah mendapatkan ilmunya ketika saya kuliah. Alhasil saya harus benar-benar menguasai sebelum saya mengajar dikelas. Matakuliahnya sangat menarik penuh dengan logika saya sangat suka tapi cukup kewalahan mencari materi. Ok mari kita mulai..

Pohon adalah struktur data yang secara bentuk menyerupai pohon. Hanya saja berbeda dengan dunia nyata pohon tumbuh ke atas tapi di struktur dari pohonnya tumbuh ke bawah. Pohon terdiri dari serangkaian simpul (node) yang saling terhubung. Sebuah pohon merepresentasikan sebuah hirarki atau tingkatan. Contoh pohon:

  1. Pohon Struktur Organisasi

mdp

2. Daftar isi sebuah bukudaspro

Banyak istilah-istilah umum yang perlu anda ketahui:

p1

Gambar 3. Contoh Pohon

  1. Induk (Parent)
    Node yang berada di atas node lain secara langsung. Contoh dari Gambar 3, 1 merupakan parent dari 2, 3 dan 4. Contoh lain 4 merupakan parent dari 7, 8 dan 9.
  2. Anak (Child)
    Node anak adalah node yang merupakan cabang langsung dari sebuah node. Contoh 2 adalah anak dari 1.
  3. Akar (root)
    Akar adalah node yang tidak memiliki induk atau node yang paling tinggi. Jika dilihat pada Gambar 3, maka rootnya adalah 1.
  4. Daun (leaf)
    Daun adalah node yang tidak memiliki anak. Seperti : 5, 6, 3, 7, 8, dan 9.
  5. Simpul dalam (internal node)
    Simpul dalam adalah simpul yang memiliki anak minimal 1. Seperti node 1, 2 dan 4.
  6. Simpul luar (external node)
    Simpul luar adalah simpul yang paling luar atau sama saja dengan daun. Seperti: 5, 6,3,7, 8 dan 9.
  7. Level
    Level adalah tingkatan yang ditinjau dari posisi akar. akar memiliki level 0. Untuk contoh pohon dapat dilihat pada Gambar 4.
  8. Tinggi (Height)
    Ketinggian adalah level tertinggi dari suatu pohon di tambah dengan 1. Maka ketinggian pohon pada Gambar 4 adalah 4 (level tertinggi+1).

    picture1

    Gambar 4. Contoh Pohon 2

  9. Derajat
    Derajat adalah jumlah anak maksimal yang boleh dimiliki oleh node. Dari Gambar 4 node T memiliki anak terbanyak yaitu 3. Maka derajat dari pohon tersebut adalah 3.
Advertisements

Binary Tree

Pohon biner adalah jenis pohon yang memiliki ke khasan, yaitu jumlah anak setiap simpul maksimal dibatasi dua buah saja.

1. Node

Pada dasarnya pohon biner sama saja dengan list hanya saja koneksinya lebih dari 1. Biasanya node  tree terdiri dari 2 bagian, data dan koneksi. Pada pohon biner terdapat koneksinya adalah koneksi kiri (anak kiri) dan koneksi kanan (anak kanan).

node

   Gambar 1. Representasi Node

  • Data adalah nilai yang disimpan didalam node dan biasanya tipe datanya adalah tipe data primitif.
  • Sedangkan L adalah koneksi yang menghubungkan dengan Node sebelah kiri.
  • dan R adalah koneksi yang menghubungkan dengan Node sebelah kanan.

Ada juga Node yang memiliki 3 koneksi, yaitu kanan, kiri dan parent.

Picture1

Gambar 2. Node dengan 3 koneksi

Parent adalah koneksi yang menghubungkan Node dengan Node orang tuanya. Sehingga anaknya bisa mengetahui data orang tuanya. Berbeda dengan Gambar 1, hanya orang tua yang mengenali anak tetapi tidak sebaliknya.

2. Pohon

Sebuah pohon harus memiliki akar atau root. Root dari sebuah pohon tidak boleh lepas karena root adalah pangkal dari sebuah pohon. Jika kita mengetahui pangkal sebuah pohon maka otomatis kita bisa menngunjungi semua node pada pohon tersebut.

Jenis-Jenis Binary Tree

  1. Full Binary Tree
    Pohon biner yang semua nodenya (kecuali leaf) pasti memiliki 2 anak dan tiap subtree memiliki tinggi pohon yang sama.
    Picture2
  2. Complete Binary Tree
    Pohon biner yang mirip dengan full binary tree tetapi tiap subtree memiliki selisih ketinggian minimal 1. Contoh tinggi pohon kiri 2 dan pohon kanan 1. maka selisihnya adalah 1. Jika selisih 1 maka pohon di bawah ini dapat diseput pohon complete.
    Picture3
  3. Skewed Binary Tree
    Pohon biner yang semua nodenya hanya memiliki 1 anak dan pohonnya condong. Misal condongnya ke kiri maka semua node hanya memiliki anak kiri semua begitu juga sebaliknya.
    Picture4

 

%d bloggers like this: