POHON BERAKAR

-




  • Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.
  • Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu.
  • Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol.
  • Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol.

Terminologi pada Pohon Berakar

  • Child atau children (Anak) dan parent (orangtua)
  • Path (lintasan)
  • Descendant (Keturunan) dan ancestor (leluhur)
  • Sibling (saudara kandung)
  • Subtree (subpohon)
  • Degree (derajat)
  • Leaf (daun)
  • Internal nodes (simpul dalam)
  • Level (tingkat)
  • Height (tinggi) atau depth (kedalaman)

Child atau children (Anak) dan parent (orangtua)


Simpul y dikatakan anak simpul x jika ada sisi dari simpul x ke y dan Orangtua dari simpul y adalah simpul x.
Pada gambar G1 : 
  • Simpul b, c dan d --> anak dari simpul a 
  • Simpul e dan f --> anak dari simpul b 
  • Simpul a --> orangtua dari simpul b, c dan d 
  • Simpul b --> orangtua dari simpul e dan f  

Path (lintasan)

Lintasan dari simpul vi ke simpul vk adalah runtunan simpul-simpul v1, v2 ,…, vk sedemikian hingga vi adalah orangtua dari vi+1 untuk 1 <= i <= K.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1. 
Pada gambar G1 : 
  • Lintasan dari a ke j adalah a, b, e dan j 
  • Panjang lintasan dari a ke j adalah 3

Descendant (Keturunan) dan ancestor (leluhur)

x adalah leluhur dari simpul y jika terdapat lintasan dari simpul x ke simpul y di dalam pohon dan keturunan dari simpul x adalah simpul y.
Pada gambar G1 :
  • Simpul b adalah leluhur dari simpul h
  • Simpul h adalah keturunan dari simpul b

Sibling (saudara kandung)

Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :
  • Simpul f saudara kandung dari e
  • Simpul g bukan saudara kandung dari e karena orangtua berbeda 

Subtree (subpohon) 

Subtree dengan x sebagai akarnya adalah subgraf T’ = (V’,E’) sedemikian hingga V’ mengandung x dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari x
Pada gambar G2 :
  • V’ = {b, e, f, h, i, j}
  • E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
  • b adalah simpul akar 

Degree (derajat) 

Derajat sebuah simpul pohon berakar adalah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :
  • Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1
  • Derajat tertinggi (maksimum) : 3 

Leaf (daun)

Adalah simpul yang berderajat nol (tidak mempunyai anak) 
Pada gambar G1 :
  • Merupakan daun : simpul c, f, h, i, j, l dan m.

Internal nodes (simpul dalam) 

Adalah simpul yang mempunyai anak
Pada gambar di samping :
  • Merupakan simpul dalam : simpul b, d, e, g dan k

Level (tingkat) 

Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).

Height (tinggi) atau depth (kedalaman)

Adalah level maksimum dari suatu pohon
Nama lain : panjang maksimum lintasan dari akar ke daun
Pada gambar di samping :
  • Pohon mempunyai tinggi atau kedalaman : 4

Ordered Tree (Pohon Berakar Terurut)


Adalah pohon berakar yang urutan anak-anaknya penting. Sistem universal dalam pengalamatan simpul-simpul pada pohon terurut adalah dengan memberi nomor setiap simpulnya seperti penomoran bab (beserta subbab) di dalam sebuah buku

Pohon m-ary

Adalah pohon berakar yang setiap simpul cabangnya mempunyai banyak n buah anak. Jika m = 2 --> Pohon biner (binary tree).
Pohon m-ary dikatakan pohon penuh (full) atau pohon teratur jika setiap simpul cabangnya mempunyai tepat m buah anak.

Penggunaan pohon m-ary

  • Penurunan kalimat (dalam bidang bahasa)
  • Direktori arsip di dalam komputer
  • Struktur organisasi
  • Silsilah keluarga (dalam bidang genetika)
  • Struktur bab atau daftar isi di dalam buku
    Bagan pertandingan antara beberapa tim sepak bola
    Dll
Struktur direktori arsip di dalam sistem operasi Windows

Jumlah Daun pada Pohon m-ary Penuh

Pada pohon m-ary penuh dengan tinggi (height) h, jumlah daun (leaf) adalah : mh 
Jika T bukan pohon m-ary penuh  ? jumlah daun ? mh 
Jumlah seluruh simpul pohon m-ary pada pohon m-ary penuh dengan tinggi h :
    level 0    --> jumlah simpul = m0 = 1
    level 1    --> jumlah simpul = m1 
    level 2    --> jumlah simpul = m2 
            …
    level h    --> jumlah simpul = mh 
    sehingga jumlah seluruh simpul adalah :




Sehingga jumlah seluruh simpul untuk T bukan pohon m-ary penuh :

  


Hubungan Jumlah Daun dan Simpul Dalam pada Pohon m-ary Penuh

Misalkan : 
i = banyaknya simpul dalam
t = banyaknya simpul daun di dalam pohon biner penuh
m = banyaknya simpul child 
    Sehingga : (m – 1) i = t – 1



TERIMAKASIH, SEMOGA BERMANFAAT.

Komentar

Posting Komentar

Postingan populer dari blog ini

RELASI PENGURUTAN PARSIAL DAN KESETARAAN

-
Gambar
RELASI PENGURUTAN PARSIAL     Secara intuitif, di dalam relasi pengurutan parsial, istilah pengurutan berarti dua buah benda saling berhubungan jika salah satunya lebih kecil (lebih besar), daripada, atau lebih rendah (lebih tinggi) daripada lainnya menurut sifat atau kriteria tertentu. Istilah pengurutan itu sendiri memang menyatakan bahwa benda-benda di dalam himpunan tersebut diurutkan berdasarkan sifat atau criteria tersebut. Akan tetapi, ada juga kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat mmbandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil. Oleh karena itulah digunakan istilah pengurutan parsial atau pengurutan tidak-lengkap. Secara formal didefinisikan sebagai berikut. Definisi Jika R relasi pada A dan R memenuhi sifat : Reflektif, yaitu   berlaku  Antisimetri, yaitu  ,   dan   be...
Baca selengkapnya

GERBANG LOGIKA

-
Gambar
Pengertian Gerbang Logika Dasar   dan Jenis-jenisnya – Gerbang Logika atau dalam bahasa Inggris disebut dengan  Logic Gate  adalah dasar pembentuk Sistem Elektronika Digital yang berfungsi untuk mengubah satu atau beberapa Input (masukan) menjadi sebuah sinyal Output (Keluaran) Logis. Gerbang Logika beroperasi berdasarkan sistem bilangan biner yaitu bilangan yang hanya memiliki 2 kode simbol yakni  0  dan  1  dengan menggunakan Teori Aljabar Boolean. Jenis-jenis Gerbang Logika Dasar dan Simbolnya Terdapat 7 jenis Gerbang Logika Dasar yang membentuk sebuah Sistem Elektronika Digital, yaitu : Gerbang AND Gerbang OR Gerbang NOT Gerbang NAND Gerbang NOR Gerbang X-OR (Exclusive OR) Gerbang X-NOR (Exlusive NOR) Tabel yang berisikan kombinasi-kombinasi Variabel Input (Masukan) yang menghasilkan Output (Keluaran) Logis disebut dengan  “Tabel Kebenaran”  atau  “Truth Table”. Input dan Output pada Gerbang Logika hanya memi...
Baca selengkapnya

HIMPUNAN

-
Gambar
Pengertian Himpunan Himpunan adalah kumpulan benda atau objek yang dapat didefinisikan dengan jelas. Benda atau objek dalam himpunan disebut elemen atau anggota himpunan. Dari defi nisi tersebut, dapat diketahui objek yang termasuk anggota himpunan atau bukan. Contoh himpunan: • Himpunan warna lampu lalu lintas, anggota himpunannya adalah merah, kuning, dan hijau. • Himpunan bilangan prima kurang dari 10, anggota himpunannya adalah 2, 3, 5, dan 7. Contoh bukan himpunan: • Kumpulan baju-baju bagus. • Kumpulan makanan enak.   Notasi Himpunan Sebuah himpunan biasanya dinyatakan dengan simbol simbol tertentu, biasanya sebuah himpunan dinyatakan dengan menggunakan huruf besar/kapital seperti A, B, C, D, E, dst. atau bisa juga ditandai dengan adanya kurung kurawal, {…} sedangkan anggota dari himpunan tersebut biasanya ditandai dengan menggunakan huruf alfabet kecil seperti a,b,c,d,e, dst.  Untuk menyatakan sebuah himpunan, ada 4 buah cara yang bisa dilaku...
Baca selengkapnya