Pohon biner: Perbedaan revisi

5 bita dihapus ,  11 tahun yang lalu
k
Robot: Cosmetic changes
k (Robot-assisted disambiguation: Aksara - Changed link(s) to huruf)
k (Robot: Cosmetic changes)
[[ImageBerkas:binary tree.svg|right|192|thumb|Sebuah pohon biner sederhana dengan lebar 9 dan tinggi 3, dengan sebuah [[Pohon (struktur data)#Akar (Root nodes)|akar]] yang memiliki nilai 2]]
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<sup>''h''</sup> - ''n'' untuk sebuah pohon dengan tinggi ''h'' dengan ''n''simpul.
 
<center>[[ImageBerkas:Binary tree in array.svg|300px|Sebuah pohon biner lengkap kecil disimpan dalam array]]</center>
 
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>
[[ImageBerkas:nary to binary tree conversion.png|Sebuah contoh mengubah sebuah pohon n-er menjadi sebuah pohon biner]]
</center>
 
 
== 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&ndash;21–2.3.2 (hal.318&ndash;348318–348).
 
[[Kategori:Pohon (struktur data)]]
[[bg:Двоично дърво]]
[[cs:Binární strom]]
[[da:binærtBinært søgetræ]]
[[de:Binärbaum]]
[[en:Binary tree]]
[[es:Árbol binario]]
[[fi:Binääripuu]]
[[fr:Arbre binaire]]
[[ko:이진 트리]]
[[he:עץ בינארי]]
[[ja:二分木]]
[[ko:이진 트리]]
[[pl:Drzewo binarne]]
[[pt:árvoreÁrvore binária]]
[[ru:Двоичное дерево]]
[[sk:Binárny strom]]
[[sl:dvojiškoDvojiško drevo]]
[[sr:Бинарно стабло]]
[[fi:Binääripuu]]
[[sv:Binärträd]]
[[uk:Бінарне дерево]]
259.487

suntingan