Pohon biner: Perbedaan antara revisi

Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] [[struktur data]] dimana 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]].

 

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 ''[[Fungsi lantai|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^''h'' - ''n'' untuk sebuah pohon dengan tinggi ''h'' dengan ''n''simpul.

 

 

Dalam bahasa dengan ''[[tagged union]]'' seperti [[Bahasa pemrograman ML|ML]], sebuah simpul pohon seringkali sebuah ''tagged union'' dari dua jenis simpul, dimana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain dimana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan ''penunjuk (pointers)''

 

<center>

</center>

 

 

== Referensi ==

 

[[Kategori:Pohon (struktur data)]]

[[bg:Двоично дърво]]

[[cs:Binární strom]]

[[de:Binärbaum]]

[[en:Binary tree]]

[[es:Árbol binario]]

[[fr:Arbre binaire]]

[[he:עץ בינארי]]

[[ja:二分木]]

[[pl:Drzewo binarne]]

[[ru:Двоичное дерево]]

[[sk:Binárny strom]]

[[sr:Бинарно стабло]]

[[sv:Binärträd]]

[[uk:Бінарне дерево]]