tree binary tree

  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.

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  simpul adalah , Bilangan Catalan ke (asumsikan kita melihat pohon dengan struktur yang identik sebagai sebuah kesamaan). Untuk besarnya , ini berkisar kira-kira sehingga kita membutuhkan setidaknya kira-kira  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:

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  bit pada bagian akhir, dimana 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.

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.