Pohon biner: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
baru |
Tidak ada ringkasan suntingan |
||
Baris 1:
[[Image:binary tree.svg|right|192|thumb|Sebuah pohon biner sederhana dengan
Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] [[struktur data]] dimana 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 ==
* Sebuah '''panah langsunng''' mengacu pada penghubung dari [[simpul ayah|ayah]] ke [[simpul anak|anak]] nya (panah di gambar dalam pohon).
* [[Pohon (struktur data)#Akar (Root nodes)|Akar]] dari pohon adalah [[Pohon (struktur data)#Simpul (nodes)|simpul]] tanpa ayah. Terdapat paling banyak satu akar dalam pohon berakar.
* Sebuah [[Pohon (struktur data)#Daun (Leaf nodes)|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 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 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 sebuah '''pohon 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.
* 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.
== Definisi dalam teori graf ==
Sebuah pohon biner adalah grafik asiklis yang terhubung dimana 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]]
Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi [[rekursif]] pada grafik langsung. Sebuah pohon biner dapat berarti:
* Sebuah sudut tunggal
* Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar daris setiap pohon biner.
Ini juga tidak menentujan susunan anak, tetapi memperbaiki akar tertentu.
[[Kategori:Struktur data]]
| |||