A számítástechnikában nagyon fontos szerepet töltenek be a hierarchikus adatszerkezetek, melyeknek egyik talán legismertebb reprezentációja a könyvtárszerkezet. Az STL-ben többféle hierarchikus adatszerkezet található, ezek közül ismertet néhányat ez a cikk.

Bevezetés

A számítástechnikában nagyon fontos szerepet töltenek be a hierarchikus adatszerkezetek. Egyik talán legismertebb reprezentációja a könyvtárszerkezet, amely a tároló eszközökön található erőforrások elérését könnyíti meg. Vagy például az adatbázis-kezelők működésében is kitüntetett szerepe van a B-fa néven ismert indexszerkezetnek, amelyik szintén egy hierarchikus adatszerkezet. Ebben a cikkben csak a rendezett bináris fával fogunk találkozni, amelynek az a jellemzője, hogy egy elemnek maximum kettő "gyereke" lehet, és valamilyen összefüggés fent áll a "szülő" és a "gyereke"-i között. A bináris fák nagyon jól használhatók keresésre és rendezésre, mivel a legtöbb művelet futási idejének felső korlátja arányos a fa mélységével, ami ideális esetben lg(n), ahol n a fában található elemek száma.

priority_queue

A priority_queue egy speciális adatszerkezeten, a kupacon (heap) alapuló template. A kupac egy olyan bináris fa, amelyik egy tömbben van ábrázolva. Egy lehetséges állapotot a következő táblázat illetve ábra szemlélteti. A kupac rendező elve az, hogy a szülő elem kisebb-egyenlő (vagy nagyobb-egyenlő) a gyerekeinél. Egy elem indexéből a gyerekeinek indexe, illetve a szülejének az indexe egyszerűen és gyorsan számolható:

#define LEFTCHILD(i) ((i)*2+1)
#define RIGHTCHILD(i) (((i)+1)*2)
#define PARENT(i) (((i)-1)/2)

A tömb mindig teljesen kitöltött, azaz üres hely nincs benne, ebből adódóan a fa mélysége n elem esetén lg(n). Előnye ennek a szerkezetnek, hogy bármely tömb lineáris időben kupaccá rendezhető, illetve a beszúrás és törlés művelet időigénye a fa mélységével arányos, ami lg(n).
A priority_queue a beszúrás során a beszúrandó elemet elhelyezi a tömb végén, majd "felutaztatja" a helyére, törlés során, a törölt elem helyére rakja legutolsót, és a tömb méretének csökkentése után, "leutaztatja" az elemet a helyére. A "fel-" illetve "leutazás" során az aktuális elem illetve gyerekei közül kiválasztja a minimális elemet (maximális elemet), és ha ez nem a szülő, akkor cserét hajt végre, és folytatja tovább ezt az algoritmust a cserében részt vevő ágon.
Az implementáláshoz használható alap struktúrák, a vector és a deque. A metódusai megegyeznek a stack metódusaival. A jellemző felhasználási területe a prioritás alapú ütemezés, azaz egy általános programban nem túl gyakori a használata :-).

vörös-fekete fa (red-black tree)

A bináris fák egy nagy csoportját alkotják a bináris keresőfák. A bináris keresőfa rendező elve, hogy a szülőnél kisebb (vagy nem nagyobb, vagy nem kisebb, vagy nagyobb) elemek mind a baloldali részfában találhatók, így elég egyszerű - maximum a fa mélységének megfelelő lépésszámú - feladat egy elem megkeresése. Egy új elem beszúrása szintén a fa mélységével arányos lépésszámban elvégezhető. Először meg kell keresni a helyét, majd a feltételnek megfelelő üres helyre felfűzni. A törlés egy picivel bonyolultabb, de természetesen ennek a lépésszáma is a fa mélységével arányos, azaz miután megvan a törlendő elem, meg kell nézni, hogy van-e bal- illetve jobboldali részfája. Ha egyik sincs, akkor törölhető. Ha csak baloldali, vagy jobboldali van, akkor a gyereke kerül a helyére. Egyébként pedig a jobboldali gyerekének kell a legkisebb elemét megkeresni, és a törölt helyére áthelyezni. Egy lehetséges bináris keresőfát ábrázol a következő ábra. A bináris keresőfának azonban van egy problémás tulajdonsága, könnyen előfordulhat, hogy "elfajul", azaz egy szülő baloldali részfájának a mélysége jóval nagyobb, vagy kisebb lesz, mint a jobboldalié. Sőt az is előfordulhat, hogy egy bináris keresőfa átváltozik láncolt listává, azaz ha például csak baloldali, illetve jobboldali ágak vannak benne. Ez történik például akkor, ha rendezett adatokat szúrunk egy üres fába. Ennek elkerülésére több megoldás is született, ezek közül az egyik a vörös-fekete fa. Az alapműveletek nem változtak, csak kiegészültek elfajulást megelőző (kiegyensúlyozó) kóddal. A vörös-fekete fa rendezőelve a következő:

• Minden elemnek van színe, ami vagy vörös, vagy fekete.
• Az üres mutató (NULL) színe fekete.
• Bármely vörös elem mindkét gyerekének a színe fekete.
• Bármely elemtől induló, üres mutatóig vezető úton a fekete csúcsok száma azonos.

Ha egy fára igazak ezek a szabályok, akkor a teljesül az, hogy a fa magassága maximum kétszerese az ideális fa magasságának, ebből következően a beszúrás, törlés, keresés lépésszáma arányos lg(n)-el.
Az STL a vörös-fekete fákat használja a rendezett asszociatív tárolók (map, multimap, set, multiset) megvalósítására. A vörös-fekete fa egy eleménél a fa fenntartásához szükséges járulékos memória igény (overhead) három mutató - kettő a gyerekek felé, illetve egy a szülő felé - illetve egy színinformációt hordozó változó. Ez az x86-os platformon 32 bites rendszert használva 16 byte.