Pohon biner: Perbedaan antara revisi

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]].

* 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'''.

* 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 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.

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.

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.

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)''

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 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.

''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:

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.