Pohon biner: Perbedaan revisi

15 bita ditambahkan ,  4 tahun yang lalu
k
Bot: Penggantian teks otomatis (-dimana +di mana); perubahan kosmetik
(hilangkan 'yoppie ratna ariyanto')
k (Bot: Penggantian teks otomatis (-dimana +di mana); perubahan kosmetik)
[[Berkas:binary tree.svg|right|192|thumb|Sebuah pohon biner sederhana dengan lebar 9 dan tinggi 3, dengan sebuah [[Pohon (struktur data)#Akar (Root nodes)|akar]] yang memiliki nilai 2]]
Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] [[struktur data]] dimanadi mana setiap [[Pohon (struktur data)#Simpul (node)|simpul]] memiliki paling banyak dua [[Pohon (struktur data)|anak]]. Secara khusus anaknya dinamakan ''kiri'' dan ''kanan''. Penggunaan secara umum pohon biner adalah [[Pohon biner terurut]], yang lainnnya adalah [[heap biner]].
 
== Definisi untuk pohon berakar ==
* '''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''', dimanadi mana simpul '''p''' lebih dekat ke akar daripada '''q''', maka '''p''' adalah '''leluhur''' dari '''q''' dan '''q''' adalah '''keturunan''' '''p'''.
* '''Lebar''' daris sebuah simpul adalah jumlah keturunan termasuk simpul itu sendiri.
 
== Jenis pohon biner ==
* Sebuah '''pohon biner berakar''' ''('''rooted binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] berakar dimanadi mana setiap simpul paling banyak mempunyai dua anak
* Sebuah '''pohon biner penuh''' ''('''full binary tree''')'', atau '''pohon biner asli''' ''('''proper binary tree''')'', adalah sebuah pohon dimanadi mana setiap simpul mempunyai nol atau dua anak.
* Sebuah '''pohon biner sempurna''' ''('''perfect binary tree''')'' (atau kadang-kadang '''pohon biner lengkap''' ''('''complete binary tree''')'' adalah sebuah '''pohon biner penuh''' dimanadi mana semua ''daun'' memiliki ''kedalaman'' yang sama.
* Sebuah '''pohon biner lengkap''' ''('''complete binary tree''')'' dapat didefinisikan juga sebagai sebuah '''pohon biner penuh''' dimanadi mana semua daunnya memiliki kedalaman ''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 di antara keduanya. Sebagai contoh, jika dua simpul pada tingkat terbawah masing-masing menempati sebuah titik dengan suatu titik kosong di antara keduanya, tetapi sisa simpul anaknya terhimpit tanpa titik di antaranya, maka pohon tersebut tidak dapat membentuk sebuah pohon biner lengkap karena titik kosong tersebut.
* 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 dimanadi mana 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''' dimanadi mana '''h''' adalah tinggi dari pohon.
* Jumlah daun '''n''' dalam sebuah pohon biner lengkap dapat dihitung dengan menggunakan rumus: '''n = 2^h''' dimanadi mana '''h''' adalah tinggi dari pohon.
 
== Definisi dalam teori graf ==
Sebuah pohon biner adalah grafik asiklis yang terhubung dimanadi mana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat ditunjukan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah '''pohon biner berakar''' merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar.
 
Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak; bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yg tak terkoneksi, membolehkan bermacam koneksi dalam komponen di gafik, kita memanggil struktur sebuah [[Pohon (struktur data)#Hutan|hutan]].
 
== Kombinatorik ==
Kelompok dari sepasang simpul dalam sebuah pohon dapat digambarkan sebagai pasangan dari [[huruf|aksara]] dalam tanda kurung. Oleh sebab itu, ''(a,b)'' menunjukan pohon biner dimanadi mana sub pohon kirinya adalah ''a'' sedangkan sub pohon kanannya adalah ''b''. Benang dari tanda kurung yang seimbang mungkin dapat digunakan untuk menunjukan pohon biner pada umumnya. Himpunan dari semua benang yang mungkin yang terdiri dari keseluruhan tanda kurung yang seimbang dikenal sebagal [[bahasa Dyck]].
 
Diketahui ''n+1'' simpul, jumlah seluruh jalan dimanadi mana simpul tersebut dapat disusun kedalam sebuah pohon biner dengan sebuah [[bilangan Catalan]] <math>C_n</math>. Sebagai contoh, <math>C_2=2</math> adalah pernyataan bahwa ''(ab)c'' dan ''a(bc)'' merupakan dua pohon biner yang mungkin, yang memiliki 3 simpul.
 
Kemampuan untuk menggambarkan pohon biner sebagai benang dari simbol-simbol dan tanda kurung secara tidak langsung menyatakan bahwa pohon biner dapat mewakili elemen dari [[magma (algebra)|magma]]. Sebaliknya, himpunan dari semua pohon biner yang mungkin, bersama-sama dengan operasi natural memasangkan pohon dari satu ke yang lain, dari sebuah magma, [[magma bebas]].
<center>[[Berkas:Binary tree in array.svg|300px|Sebuah pohon biner lengkap kecil disimpan dalam array]]</center>
 
Dalam bahasa dengan ''[[tagged union]]'' seperti [[Bahasa pemrograman ML|ML]], sebuah simpul pohon seringkali sebuah ''tagged union'' dari dua jenis simpul, dimanadi mana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain dimanadi mana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan ''penunjuk (pointers)''
 
== Metode iterasi pohon biner ==
Seringkali, seseorang berkeinginan untuk mengunjungi simpul dalam pohon dan menjalankan perintahnya disana. Terdapat beberapa penyusunan umum dimanadi mana simpul-simpuk tersebut dapat dikunjungi, dan setiap simpul memiliki sifat-sifat yang berguna yang dimanfaatkan dalam algoritma yang berdasarkan pada pohon biner.
 
=== Pre-order, in-order, dan post-order traversal ===
 
Pre-order, in-order, dan post-order traversal mengunjungi setiap simpul dalam sebuah pohon dengan pengunjungan secara berulang-ulang pada sub pohon kiri dan kanan dari akarnya. Jika akarnya dikunjungi sebelum sub pohonnya, ini merupakan preoder. Jika akarnya dikunjungi sesudah sub pohonnya, ini dinamakan postorder dan jika akarnya dikunjungi di antara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam [[pohon biner terurut]], dimanadi mana ''traversal'' ini mengunjungi simpul dalam urutan yang meningkat.
 
=== Depth-first order ===
}
 
''String'' ''structure'' hanya memiliki <math>2n + 1</math> bit pada bagian akhir, dimanadi mana <math>n</math> adalah angka dari simpul dalam; kita bahkan tidak memerlukan untuk menyimpan panjangnya. Untuk menunjukkan bahwa tidak ada informasi yang hilang, kita dapat mengubah hasilnya kembali seperti pohon aslinya seperti ini:
 
'''function''' DecodeSuccinct(''bitstring'' structure, ''array'' data) {
Terdapat sebuah pemetaan satu-satu antara pohon terurut general dan pohon biner, yang biasanya digunakan oleh [[Lisp (bahasa pemrograman)|Lisp]] untuk menggambarkan pohon terurut general sebagai pohon biner. Setiap simpul ''N'' dalam pohon terurut terhubung ke sebuah simpul ''N'' dalam pohon biner; anak kiri dari ''N'' merupakan simpul yang terhubung ke anak pertama dari ''N'', dan anak kanan dari ''N'' merupakan simpul yang terhubung ke saudara selanjutnya dari ''N'' yang merupakan simpul selanjutnya dalam urutan di antara anak-anaknya dari ayahnya ''N''
 
Suatu cara untuk menyelesaikan ini adalah bahwa setiap anak simpul berada dalam sebuah [[linked list]], dihubungkan bersama dengan bidang ''kanan'' mereka, dan simpul yang hanya memiliki sebuah petunjuk ke awalnya atau kepala dari daftar ini, melalui bidang ''kiri'' nya.
 
Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.
110.443

suntingan