Struktur Data – Tree [pohon]



Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung.

7.1         Node (simpul)

Sebuah Simpul dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data terpisah atau sebuah bagian pohon itu sendiri. Setiap simpul dalam sebuah pohon memiliki nol atau lebih simpul anak (child nodes), yang berada dibawahnya dalam pohon (menurut perjanjian, pohon berkembang ke bawah, tidak seperti yang dilakukannya di alam). Sebuah simpul yang memiliki anak dinamakan simpul ayah (parent node) atau simpul leluhur (ancestor node) atau superior. Sebuah simpul paling banyak memiliki satu ayah. Tinggi dari pohon adalah panjang maksimal jalan ke sebuah daun dari simpul tersebut. Tinggi dari akar adalah tinggi dari pohon. Kedalaman dari sebuah simpul adalah panjang jalan ke akarnya dari simpul tersebut.

7.2         Akar (Root nodes)

Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.

7.3         Daun (Leaf nodes)

Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.

Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.

7.4         Simpul dalam (Internal nodes)

Sebuah simpul dalam adalah semua simpul dari pohon yang memiliki anak dan bukan merupakan daun. Beberapa pohon hanya menyimpan data didalam simpul dalam, meskipun ini mempengaruhi dinamika penyimpanan data dalam pohon. Sebegai contoh, dengan daun yang kosong, seseorang dapat menyimpan sebuah pohon kosong dengan satu daun. Bagaimanapun juga dengan daun yang dapat menyimpan data, tidak dimungkinkan untuk menyimpan pohon kosong kecuali jika seseorang memberikan beberapa jenis penanda data di daun yang menandakan bahwa daun tersebut seharusnya kosong (dengan demikian pohon itu seharusnya kosong juga).

Sebaliknya, beberapa pohon hanya menyimpan data dalam daun, dan menggunakan simpul dalam untuk menampung metadata yang lain, seperti jarak nilai dalam sub pohon yang berakar pada simpul tersebut. Jenis pohon ini berguna untuk jarak yang meragukan.

7.5         Sub pohon (Subtrees)

Sebuah sub pohon adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri. Simpul apapun dalam pohon P, bersama dengan seluruh simpul dibawahnya, membentuk sebuah sub pohon dari P. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang terhubung dengan simpul lain manapun dinamakan sub pohon asli(proper subtree).

7.6         Penyusunan pohon

Terdapat dua jenis pohon. Sebuah pohon tidak terurut (unordered tree) adalah sebuah pohon dalam arti struktural semata-mata, yang dapat dikatakan memberikan sebuah simpul yang tidak memiliki susunan untuk anak dari simpul tersebut. Sebuah pohon dengan suatu susunan ditentukan, sebagai contoh dengan mengisi bilangan asli berbeda ke setiap anak dari simpul tersebut, dinamakan sebuah pohon terurut(ordered tree), dan struktur data yang dibangun didalamnya dinamakan pohon terurut struktur data (ordered tree data structures). Sejauh ini pohon terurut merupakan bentuk umum dari pohon struktur data. Pohon biner terurut merupakan suatu jenis dari pohon terurut.

7.7         Hutan

Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.

7.7.1        Inorder

  1. lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  2. kunjungi akar dari pohon pertama.
  3. lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.

7.7.2        Preorder

  1. kunjungi akar dari pohon pertama.
  2. lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  3. lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.

7.7.3         Postorder

  1. lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  2. lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
  3. kunjungi akar dari pohon pertama.

7.8         Penggambaran pohon

Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada heap(bedakan dengan heap struktur data) yang mengacu pada anaknya, ayahnya, atau keduanya, atau seperti data materi dalam array, dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh binary heap).

7.9         Pohon sebagai grafik

Dalam teori grafik, sebuah pohon adalah sebuah grafik asiklis yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal diluar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil hutan.

7.10     Metode traversal

Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orang tua dan anak, dinamakan menelusuri pohon, dan tindakannya adalah sebuah jalan dari pohon. Seringkali, sebuah operasi mungkin dapat dilakukan sebagai penunjuk ysng mengacu pada simpul khusus. Sebuah penelusuran dimana setiap simpul ayah dikunjungi sebelum anaknya dinamakan pre-order walk; sebuah penelusuran dimana anaknya dikunjungi sebelum ayahnya masing-masing dinamakan post-order walk.

7.10.1    Operasi umum

–        Menghitung seluruh materi (item)

–        Pencarian untuk sebuah materi

–        Menambahkan sebuah materi pada sebuah posisi tertentu dalam pohon

–        Menghapus sebuah materi

–        Mengeluarkan seluruh bagian dari sebuah pohon pruning

–        Menambahkan seluruh bagian ke sebuah pohon grafting

–        Menemukan akar untuk simpul apapun

7.10.2    Penggunaan umum

–        Memanipulasi data secara hierarki

–        Membuat informasi mudah untuk dicari

–        Memanipulasi data sorted lists

7.10.3    Definisi untuk pohon berakar

–        Sebuah panah langsunng mengacu pada penghubung dari ayah ke anak nya (panah di gambar dalam pohon).

–        Akar dari pohon adalah simpul tanpa ayah. Terdapat paling banyak satu akar dalam pohon berakar.

–        Sebuah daun adalah simpul yang tidak memiliki anak.

–        Kedalaman sebuah simpul n adalah panjang jalan dari akar ke simpul. Himpunan semua simpul pada kedalaman yang diberikan kadang-kadang dinamai dengan Tingkat (Level) dari pohon. Akar memiliki kedalaman kosong.

–        Tinggi sebuah pohon adalah panjang jalan dari akar ke daun-daunnya.

–        Saudara adalah simpul yang memiliki ayah yang sama

–        Jika terdapat sebuah jalan dari simpul p ke simpul q, dimana simpul p lebih dekat ke akar dari pada q, maka p adalah leluhur dari q dan qadalah keturunan p.

–        Lebar daris sebuah simpul adalah jumlah keturunan termasuk simpul itu sendiri.

7.10.4    Jenis pohon biner

–        Sebuah pohon biner berakar (rooted binary tree) adalah sebuah pohon berakar dimana setiap simpul paling banyak mempunyai dua anak

–        Sebuah pohon biner penuh (full binary tree), atau pohon biner asli (proper binary tree), adalah sebuah pohon dimana setiap simpul mempunyai nol atau dua anak.

–        Sebuah pohon biner sempurna (perfect binary tree) (atau kadang-kadang pohon biner lengkap (complete binary tree) adalah sebuahpohon biner penuh dimana semua daun memiliki kedalaman yang sama.

–        Sebuah pohon biner lengkap (complete binary tree) dapat didefinisikan juga sebagai sebuah pohon biner penuh dimana semua daunnya memiliki kedalanam n atau n-1 untuk beberapa n. Agar sebuah pohon dapat menjadi sebuah pohon biner lengkap, semua anak pada tingkat terakhir harus menempati titik terkiri secara teratur, dengan tidak ada titik yang menganggur diantara keduanya. Sebagai contoh, jika dua simpul pada tingkat terbawah masing-masing menempati sebuah titik dengan suatu titik kosong diantara keduanya, tetapi sisa simpul anaknya terhimpit tanpa titik diantaranya, maka pohon tersebut tidak dapat membentuk sebuah pohon biner lengkap karena titik kosong tersebut.

–        Pohon biner Ekuvalen, yakni dua pohon mempunyai struktur data yang sama tetapi mempunyai informasi yang berbeda.

–        Pohon biner Similer, yakni dua pohon yang mempunyai struktur dan informasi yang sama.

–        Sebuah pohon biner lengkap berakar (rooted complete binary tree) dapat dikenali dengan magma bebas.

–        Sebuah pohon biner hampir lengkap (almost complete binary tree) adalah sebuah pohon diaman setiap simpul yang mempunyai anak kanan juga memiliki anak kiri. Memiliki anak kiri tidak memerlukan sebuah simpul untuk mempunyai anak kanan. Penjelasan lainnya, sebuah pohon biner hampir lengkap adalah sebuah pohon dimana untuk sebuah anak kanan, selalu terdapat anak kiri, tetapi untuk sebuah anak kiri, tidak selalu terdapat sebuah anak kanan.

–        Jumlah simpul n dalam pohon biner lengkap dapat dihitung dengan menggunakan rumus: n = 2^(h+1)-1 dimana h adalah tinggi dari pohon.

–        Jumlah daun n dalam sebuah pohon biner lengkap dapat dihitung dengan menggunakan rumus: n = 2^h dimana h adalah tinggi dari pohon.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s