POHON BINAR

Pohon atau tree adalah salah satu bentuk graph terhubung yang tidak mengandung sirkuit. Karena merupakan graph terhubung, maka pada pohon selalu terdapat path atau jalur yang menghubungkan setiap dua simpul dalam pohon. Pohon yang dilengkap dengan apa yang disebut akar disebut pohon berakar atau rooted tree. 

Pohon Binar (Binary Tree)

Dalam struktur data, pohon memegang peranan penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hirarkikal antara elemen-elemen mereka. Misalnya, data pada record keluarga dari pohon ataupun isi dari tabel. Mereka mempunyai hubungan hirarkikal. 

Bentuk pohon yang berakar khusus , yang lebih mudah kita kelola dalam computer adalah pohon binary. Bentuk pohon yang berakar umum, dikenal sebagai “pohon umum” atau “general tree”.

Sebuah pohon binar T didefinisikan terdiri atas sebuah himpunan hingga elemen yang disebut simpul(node), sedemikian sehingga :

a.T adalah hampa (disebut pohon null) atau;

b.T mengandung simpul R yang dipilih(dibedakan dari yang lain), disebut “akar: atau “roof” dari T, dan simpul sisanya membentuk 2 pohon binary (subpohon kiri dan subpohon kanan dari akar R).

Terminologi Pada Pohon Binar

Terminologi hubungan keluarga banyak digunakan dalam terminology pada pohon binary. Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan suksesor kanan , serta istilah ayah untuk pengganti prodesesor. Selain itu juga istilah saudara (brother) yang diberikan kepada kedua simpul yang mempunyai ayah yang sama. Jelas bahwa setiap simoul kecuali akar mempunyai ayah yang tunggal.

Pohon Binar Lengkap

Setiap simpul dari pohon binary paling banyak mempunyai dua anak. Suatu pohon binar T dikatakan lengkap atau complete, bila  setiap tingkatnya kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin yakni 21 simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul dibagian kiri pohon. Jadi, pohon binary lengkap dengan simpul, T adalah tunggal(dalam hal ini mengabaikan label simpul).

Pohon-2

Pohon Binar T dikatakan pohon-2 atau pohon binar yang dikembangkan(extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini, simpul dengan dua anak disebut simpul internal, sedanglan simpul tanpa anak disebut simpul eksternal. Dalam diagramnya, seringkali diadakan perbedaan antara simpul internal dan eksternal. Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.

Penyajian Pohon Binar Dalam Memori

Kita dapat menyajikan suatu pohon binary T dalam memori dengan dua cara. Cara pertama adalah penyajian kait (link).  Cara ini biasa digunakan. Ia analaog dengan cara list berkaitan (linked list) ketika disajikan dalam memori. Cara kedua adalah dengan menggunakan sebuah array tunggal disebut penyajian sekuensial T.

 

Kebutuhan utama yang harus dipenuhi pada setiap penyajian T bahwa seseorang dapat mempunyai akses langsung ke akar R dan T, bila diberikan sembarang simpul N, seseorang harus dapat akses langsung ke anak dari N.

Sumber : Pengantar Struktur Data, Dr.Suyadi H.S, Universitas Gunadarma