Pohon biner
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 " " dan " ". Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner. 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 atau. Jika kita membuang keperluan yang 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: Ini juga tidak menentujan susunan anak, tetapi memperbaiki akar tertentu.
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 formula_1. Sebagai contoh, formula_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 dan kadang-kadang mengacu sebagai CAR dan CDR.
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 dan anak. 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-2"i"+1 dan 2"i"+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 2- "n" untuk sebuah pohon dengan tinggi "h" dengan "n"simpul.
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, dan anak, dan yang lain dimana 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 dimana simpul-simpuk tersebut dapat dikunjungi, dan setiap simpul memiliki sifat-sifat yang berguna yang dimanfaatkan dalam algoritme 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 dan 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.
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.
Dibandingkan dengan "depth-first order", "breadth-first order", yang selalu berusaha untuk mengnjungi simpul terdekat dengan akar yang belum dikunjunginya.
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 formula_3 simpul adalah formula_4, Bilangan Catalan ke-formula_3 (asumsikan kita melihat pohon dengan "struktur" yang identik sebagai sebuah kesamaan). Untuk besarnya formula_3, ini berkisar kira-kira
formula_7; sehingga kita membutuhkan setidaknya kira-kira formula_8 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. Jika pohon ini memuat data, kita dapat menyimpanya secara serempak dalam sebuah array yang berurutan dengan "preoder". Fungsi ini memenuhi:
"String" "structure" hanya memiliki formula_9 bit pada bagian akhir, dimana formula_3 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:
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.
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 dari "N" merupakan simpul yang terhubung ke anak pertama dari "N", dan anak 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 " " mereka, dan simpul yang hanya memiliki sebuah petunjuk ke awalnya atau kepala dari daftar ini, melalui bidang " " 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.