Pohon biner: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k ~kat |
Tidak ada ringkasan suntingan |
||
Baris 54:
=== 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 diantara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam [[pohon biner terurut]], dimana ''traversal'' ini mengunjungi simpul dalam urutan yang meningkat.
Baris 64 ⟶ 63:
Dibandingkan dengan ''depth-first order'', ''breadth-first order'', yang selalu berusaha untuk mengnjungi simpul terdekat dengan akar yang belum dikunjunginya.
== Penyandian ==
=== 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 <math>n</math> simpul adalah <math>\mathrm{C}_{n}</math>, [[Bilangan Catalan]] ke-<math>n</math> (asumsikan kita melihat pohon dengan ''struktur'' yang identik sebagai sebuah kesamaan). Untuk besarnya <math>n</math>, ini berkisar kira-kira <math>4^{n}</math>; sehingga kita membutuhkan setidaknya kira-kira <math>\log_{2}4^{n} = 2n</math> 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. [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf] 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 <math>2n + 1</math> bit pada bagian akhir, dimana <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) {
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.
== Penyalinan pohon ''n''-er sebagai pohon biner ===
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 diantara 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.
<center>
[[Image:nary to binary tree conversion.png|Sebuah contoh mengubah sebuah pohon n-er menjadi sebuah pohon biner]]
</center>
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 ==
* [[Pohon (struktur data)]]
* [[Pohon biner terurut]]
== Referensi ==
* [[Donald Knuth]]. ''The art of computer programming vol 1. Fundamental Algorithms'', Edisi Ketiga. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, khususnya subsections 2.3.1–2.3.2 (hal.318–348).
[[Kategori:Pohon (struktur data)]]
| |||