Pohon biner: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Aliboy1234 (bicara | kontrib) Fitur saranan suntingan: 1 pranala ditambahkan. Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
|||
(16 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:binary tree.svg|
Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] [[struktur data]]
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.
== Definisi ==
=== Definisi rekursif ===
Cara lain untuk mendefinisikan pohon biner penuh adalah definisi rekursif. Sebuah pohon biner penuh adalah baik:<span class="cx-segment" data-segmentid="70"></span>
* Sebuah titik tunggal.
* Sebuah grafik yang dibentuk dengan mengambil dua (penuh) pohon biner, menambahkan sebuah sudut, dan menambahkan tepi diarahkan dari titik baru ke akar setiap pohon biner.
Ini juga tidak menetapkan urutan anak-anak, tetapi tidak memperbaiki akar tertentu.
Untuk benar-benar mendefinisikan pohon biner secara umum, kita harus memungkinkan untuk kemungkinan bahwa hanya satu dari anak-anak mungkin kosong. Artefak, yang dalam beberapa buku teks disebut pohon biner diperpanjang diperlukan untuk tujuan itu. Sebuah pohon biner diperpanjang demikian rekursif didefinisikan sebagai:<span class="cx-segment" data-segmentid="81"></span>
* Himpunan kosong adalah pohon biner diperpanjang
* ika T1 dan T2 yang diperpanjang pohon biner, kemudian dilambangkan dengan T1 • T2 pohon biner diperpanjang diperoleh dengan menambahkan r akar terhubung ke kiri untuk T1 dan ke kanan untuk T2 dengan menambahkan tepi ketika sub-pohon yang tidak kosong.
== Definisi untuk pohon berakar ==
Baris 9 ⟶ 27:
* '''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''',
* '''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
* Sebuah '''pohon biner penuh''' ''('''full binary tree''')'', atau '''pohon biner asli''' ''('''proper binary tree''')'', adalah sebuah pohon
* Sebuah '''pohon biner sempurna''' ''('''perfect binary tree''')'' (atau kadang-kadang '''pohon biner lengkap''' ''('''complete binary tree''')'' adalah sebuah '''pohon biner penuh'''
* Sebuah '''pohon biner lengkap''' ''('''complete binary tree''')'' dapat didefinisikan juga sebagai sebuah '''pohon biner penuh'''
* 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
* Jumlah simpul '''n''' dalam pohon biner lengkap dapat dihitung dengan menggunakan rumus: '''n = 2^(h+1)-1'''
* Jumlah daun '''n''' dalam sebuah pohon biner lengkap dapat dihitung dengan menggunakan rumus: '''n = 2^h'''
== Definisi dalam teori graf ==
Sebuah pohon biner adalah grafik asiklis yang terhubung
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]].
Baris 33 ⟶ 51:
== 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
Diketahui ''n+1'' simpul, jumlah seluruh jalan
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]].
Baris 48 ⟶ 66:
<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
== Metode iterasi pohon biner ==
Seringkali, seseorang berkeinginan untuk mengunjungi simpul dalam pohon dan menjalankan perintahnya disana. Terdapat beberapa penyusunan umum
=== 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]],
=== Depth-first order ===
Baris 80 ⟶ 98:
}
''String'' ''structure'' hanya memiliki <math>2n + 1</math> bit pada bagian akhir,
'''function''' DecodeSuccinct(''bitstring'' structure, ''array'' data) {
Baris 99 ⟶ 117:
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.
Baris 115 ⟶ 133:
== Lihat pula ==
* [[Pohon (struktur data)]]
* [[Pohon biner terurut]]
== Referensi ==
Baris 121 ⟶ 139:
[[Kategori:Pohon (struktur data)]]
|