Metode Untuk Menyimpan Pohon Biner
Pohon biner dapat dikonstruksi dari bahasa
pemrograman primitif dengan beberapa cara. Pada suatu bahasa dengan record dan
referensi, pohon biner secara tipikal dikonstruksi dengan sebuah struktur pohon
node yang terdiri dari beberapa data dan referensi pada node anak sisi kiri dan node
anak sisi kanan. Kadang-kadang juga terdiri atas sebuah referensi pada parent-nya yang unik. Jika suatu node
mempunyai lebih dari dua anak, beberapa pointer dari anak mungkin diset ke
suatu nilai null khusus, atau ke node sentinel
khusus.
Pohon
biner juga dapat disimpan dengan array,
dan jika pohon merupakan suatu pohon biner lengkap, metode ini tidak memborosokan
ruang penyimpanan. Dengan pengaturan kompak tersebut, jika suatu node yang mempunyai indeks i, anak-anaknya dapat ditemukan pada
indeks (2i + 1) ke sisi kiri dan (2i
+ 2) ke sisi kanan, sementara parent-nya
ditemukan pada indeks floor ((i-1)/2) dengan asumsi akar mempunyai indeks
nol. Metode ini menguntungkan sebab lebih kompak dari segi penyimpanan dan
referensi lokasi yang lebih baik, terutama selama pemindahan pada urutan awal.
Bagaimanapun juga, ini memerlukan memori yang saling berdampingan, sulit
bertambah, dan menghabiskan ruang proporsional sebesar 2h - n
untuk sebuah pohon dengan height (h) dan node (n).
Array disusun atau ditempatkan secara level order traversal seperti terlihat
pada Gambar 2.10 berikut ini.
Gambar 2.10 Penyimpanan Pohon Biner Dengan Array
Jadi untuk menentukan Parent dari node 3 maka dapat dicara dengan
persamaan:
Parent (i) = Floor ( (i -1) / 2)
Parent (1) = Floor ((1 -1) / 2) = 0
Parent (3) = Floor ( (3 - 1) / 2 ) = 1
