Terakhir disunting 12 bulan yang lalu oleh
seorang pengguna anonim
Pohon biner
Pantau halaman ini
Sebuah pohon biner sederhana dengan lebar 9
dan tinggi 3, dengan sebuah akar yang memiliki nilai 2
Dalam ilmu komputer, sebuah pohon biner
(binary tree) adalah sebuah pohon struktur data dimana 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.
Definisi untuk pohon berakarSunting
Sebuah panah langsung 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 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 binerSunting
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
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 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 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 grafSunting
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 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.
KombinatorikSunting
Kelompok dari sepasang simpul dalam sebuah
pohon dapat digambarkan sebagai pasangan dari aksara dalam tanda kurung. Oleh
sebab itu, (a,b) menunjukan pohon biner dimana 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
dimana simpul tersebut dapat disusun kedalam sebuah pohon biner dengan sebuah
bilangan Catalan C_n. Sebagai contoh, C_2=2 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. 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.
Memberikan benang yang menggambarkan sebuah
pohon biner, operator untuk mendapatkan sub pohon kiri dan kanan kadang-kadang
mengacu sebagai CAR dan CDR.
Metode untuk menyimpan pohon binerSunting
Pohon biner dapat dikonstruksi dari bahasa
pemrograman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records
dan referensi, pohon biner secara khas dikonstruksi dengan mengambil sebuah
struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan
anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang
khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak
dapat diatur kedalam nilai nol khusus, atau ke sebuah simpul sentinel.
Pohon biner dapat juga disimpan sebagai
struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah
pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat
ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks
ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks
lantai((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini
menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal
yang lebih baik, tersitimewa selama sebuah preorder traversal. Bagaimanapun
juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan
2h - n untuk sebuah pohon dengan tinggi h dengan nsimpul.
Sebuah pohon biner lengkap kecil disimpan
dalam array
Dalam bahasa dengan tagged union seperti
ML, sebuah simpul pohon seringkali sebuah tagged union dari dua jenis simpul,
dimana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan
yang lain dimana sebuah daun, yang tidak memuat data dan fungsi seperti nilai
nol dalam bahasa dengan penunjuk (pointers)
Metode iterasi pohon binerSunting
Seringkali, seseorang berkeinginan untuk
mengunjungi simpul dalam pohon dan menjalankan perintahnya disana. Terdapat
beberapa penyusunan umum dimana 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, dimana traversal ini mengunjungi simpul dalam urutan yang
meningkat.
Depth-first order
Dalam Depth-first order, kita selalu
berusaha sebisa mungkin untuk mengunjungi simpul terjauh dari akar, tetapi
dengan peringatan bahwa itu haruslah sebuah simpul anak yang telah dikunjungi.
Tidak seperti pencarian depth-first order dalam graf, tidak diperlukan untuk
mengingat seluruh simpul yang telah dikunjungi, karena sebuah pohon tidak dapat
memuat siklus. Pre-order merupakan kasus khusus untuk ini.
Breadth-first order
Dibandingkan dengan depth-first order,
breadth-first order, yang selalu berusaha untuk mengnjungi simpul terdekat
dengan akar yang belum dikunjunginya.
PenyandianSunting
Penyandian ringkas
Sebuah struktur data ringkas adalah sesuatu
yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai teori
informasi bawah. Jumlah dari pohon biner yang berbeda pada n simpul adalah
\mathrm{C}_{n}, Bilangan Catalan ke-n (asumsikan kita melihat pohon dengan
struktur yang identik sebagai sebuah kesamaan). Untuk besarnya n, ini berkisar
kira-kira 4^{n}; sehingga kita membutuhkan setidaknya kira-kira \log_{2}4^{n} =
2n bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya
membutuhkan 2 bit setiap simpul.
Salah satu penggambaran sederhana yang
masih berhubungan dengan ini adalah mengunjungi simpul dari pohon dengan
preoder, meletakkan "1" untuk sebuah simpul dalan dan "0"
untuk sebuah daun. [1] Jika pohon ini memuat data, kita dapat menyimpanya
secara serempak dalam sebuah array yang berurutan dengan preoder. Fungsi ini
memenuhi:
function EncodeSuccinct(node n, bitstring
structure, array data) {
if n = nil then
append 0 to structure;
else
append 1 to structure;
append n.data to data;
EncodeSuccinct(n.left, structure, data);
EncodeSuccinct(n.right, structure, data);
}
String structure hanya memiliki 2n + 1 bit
pada bagian akhir, dimana n 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) {
remove first bit of structure and put it in b
if b = 1 then
create a new node n
remove first element of data and put it in n.data
n.left = DecodeSuccinct(structure, data)
n.right = DecodeSuccinct(structure, data)
return n
else
return nil
}
Penggambaran secara ringkas dan rumit
memungkinkan tidak hanya penyimpanan yang rapi pada pohon tetapi bahkan operasi
yang berguna secara langsung pada pohon tersebut, meskipun mereka masih dalam
bentuk yang ringkas.
Penyandian pohon n-er sebagai pohon biner
Terdapat sebuah pemetaan satu-satu antara
pohon terurut general dan pohon biner, yang biasanya digunakan oleh 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.
Sebuah contoh mengubah sebuah pohon n-er
menjadi sebuah pohon biner
Pohon biner dapat dianggap sebagai pohon
asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam
menggambarkan anak pertama dan tepi kanannya yang berwarna biru menggambarkan
saudara selanjutnya. Daun dari bagian kiri pohon ini dapat dituliskan dalam
Lips sebagai:
(((M N) H I) C D ((O) (P)) F (L))
yang akan diimplementasikan ke memori
sebagai pohon biner kanan, tanpa huruf apapun pada simpul itu yang telah
memiliki anak.
Lihat pula
Referensi
Baca dalam bahasa lain
Wikipedia ™ Tampilan kecil (''mobile'')Tampilan
besar (''desktop'')
Konten tersedia di bawah CC BY-SA 3.0
kecuali apabila disebutkan lisensi yang lain.
Terms of UsePrivasi