Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.
Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.
Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.
Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.
Istilah
a. Pohon :susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul khusus yang disebut akat (root) sedang sisanya membentuk subtree dari akar.
b. Simpul/Vertex/Node : A, B,…, N
c. Busur/Edge/Arc : garis yang menghubungkan antar simpul
d. Superordinat/Father/Parent dan Subordinat/Son/Children.
i. Simpul A merupakan superordinat bagi simpul B, C, D
ii. Simpul B, C,D merupakan subordinat bagi simpul A
e. Root/Akar : simpul yang tidak mempunyai superordinat. Pada gambar diatas : A.
f. Leaf/Daun : simpul yang tidak mempunyai subordinat. Pada gambar diatas : C, E, G, I, J, K, L, M, N.
g. Level/Tingkat : Simpul A berada pada level 0, simpul B, C, D berada pada level 1, dst.
h. Depth/kedalaman : Level tertinggi dari suatu pohon. Pada gambar 1, depth = 3.
i. Derajat/Degree sebuah simpul jumlah simpul subordinat dari simpul tersebut.
j. Derajat/degree sebuah pohon adalah derajat tertinggi dari derajat simpul yang ada pada pohon tersebut.
Aturan Penyajian Binary Tree
- Tree dapat dibuat dengan menggunakan linked list secara rekursif.
- Linked list yang digunakan adalah double linked list non circular
- Data yang pertama kali masuk akan menjadi node root.
- Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.
Karakteristik Binary Tree
- Setiap Simpul paling banyak hanya memiliki dua buah anak
- Derajat Tertinggi dari setiap Simpul adalah dua.
- Dibedakan antara Cabang Kiri dan Cabang Kanan.
- Dimungkinkan tidak mempunyai Simpul
Istilah Pada Binary Tree
- Pohon Biner Penuh (Full Binary Tree)
Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama - 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 - Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda - Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang sama - Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun
Tidak ada komentar:
Posting Komentar