De ce contează?
Într-un bloc turn nu ai nevoie de o hartă cu săgeți ca să găsești un apartament: știi numărul lui și calculezi direct etajul și ușa. Reprezentarea secvențială face exact asta cu un arbore binar complet: îl scrii pe o singură linie, ca un șir de numere de apartament, iar legăturile dintre noduri nu le mai ții cu pointeri — le calculezi din indici.
Ce este
Numerotează nodurile unui arbore binar complet nivel cu nivel, de sus în jos
și de la stânga la dreapta: rădăcina e 1, copiii ei sunt 2 și 3, copiii
lui 2 sunt 4 și 5, și tot așa. Observi un tipar: poziția fiecărui copil e
mereu aceeași față de părinte. Reprezentarea secvențială exploatează exact
acest tipar — stochează arborele într-un vector, în care indicele este
identitatea nodului. Cu indexare de la 1, regula e fixă:
- nodul de pe poziția
iare copilul stâng pe poziția2*i; - același nod are copilul drept pe poziția
2*i + 1; - părintele nodului
ise află pe pozițiai / 2(împărțire întreagă).
Rădăcina stă mereu pe poziția 1, iar poziția 0 rămâne nefolosită. Există și
varianta indexată de la 0: acolo formulele devin 2*i + 1, 2*i + 2 și
(i - 1) / 2 — alege o convenție și păstreaz-o peste tot.
Declicul: aritmetica înlocuiește pointerii. Fiul stâng e dublul, părintele
e jumătatea — o înmulțire sau o împărțire și ai sărit la orice rudă a nodului,
în O(1), fără să aloci nimic și fără să stochezi nicio adresă. Legăturile nu
mai ocupă memorie deloc: sunt calculate, nu memorate.
Prețul acestei elegențe: formulele presupun că nodul i chiar stă pe poziția
i. La un arbore complet (sau aproape complet — ultimul nivel umplut de la
stânga), pozițiile 1..n sunt ocupate compact și nu se pierde nimic. La un
arbore degenerat, golurile explodează exponențial — vezi capcanele de mai jos.
Reprezentarea aceasta e fundația heap-ului: structura din spatele cozii de
priorități se bazează exact pe salturile 2*i și i/2.