Mikor használ egy programozó láncolt listákat? És a fákat mikor használják?

Láncolt listát akkor használsz, ha nagyméretű ojjektumokat akarsz úgy kezelni, hogy gyakran kell a sorrendjükön változtatni, pl a közepére beszúrással, onnan törléssel. Meg ha kimérted, hogy az gyorsabb, mint a vector.

A fáknak meg általában van egy tulajdonsága, ami vonzóvá teszi őket, pl a rendezőfák rendezve tartják az elemeiket (egy bizonyos bejárás szerint), de nézd meg pl a TRIE adattípust, az is egy érdekes dolog.

Amúgy semmilyen feladathoz nem KELL ilyen adattípus, csak van, amihez kényelmesebb.

Pl a C++-os [multi]set/map is fával van implementálva, és erre a feladatra tényleg ez a legkézenfekvőbb megoldás, még ha nem is a leghatékonyabb.

Így van, egy láncolt listába könnyebb beszúrni egy elemet, vagy törölni, mint egy tömbszerű listából, könnyebb például megtartani a rendezettséget egy nagyobb lista esetén. Ráadásul nem is kell azonos méretűnek/típusúnak lennie az elemeknek. (Bár illik.)

Hátránya, hogy csak szekvenciálisan kereshető benne egy adott elem, nem lehet számítani az elemek címét, mint a tömb esetén.

[link]

"Ráadásul nem is kell azonos méretűnek/típusúnak lennie az elemeknek."

Mielőtt félreértés lenne, ezt úgy értem, hogy elég ha objektumok esetén egy közös ősosztályra mutat a next pointer. :)

Képzelj el egy adatbázist mely tartalmazza az összes (10 millió) magyar ember személyi igazolvány számát, születési dátumát, nevét stb.

Egyszerűség kedvéért csak személyi szám szerint keresünk. Ha az adatokat rendezetlenül táruljuk egyszerűen egy tömbbe és keresünk egy embert akkor legrosszabb esetben végig kell nézni mind a 10 millió-t, átlagosan 5 millió lépés kell, ezzel szemben egy tökéletesen kiegyensúlyozott bináris keresőfában legrosszabb esetben is log2(10 millió) azaz 24 lépés kell azért ez elég szép sebességkülönbség, viszont ennek a egyensúlyban tartása ,karbantartása nagyon műveletigényes, ha meg nem tartjuk karban sehogy akkor elveszítjük a gyors kereshetőségét, ha valamelyik részfa aránytalanul nagyobb mint a párja vagyis ha elfajuló a fa.

@12:20

"Hátránya, hogy a karbantartása, egyensúlyban tartása erőforrás-igényes."

Viszont ez mégsem igaz, az is nagyon jó ha nem teljesen kiegyensúlyozott cserébe a karbantartása is hatékony. Első ilyen ön-kiegyensúlyozó bináris fa az AVL fa volt. Ez legrosszabb esetben 1,44x rosszabb mint a tökéletesen kiegyensúlyozott fa. Vagyis visszatérve a személyi számos példára a legrosszabb keresési idő nem 24 lépés hanem 24*1,44 = 35 lépés szemben a 10 millióval igen jó.

Az ntx ráadásul nem is bináris fa volt, henem ha jól emlékszem 12-utas, és a log2-es keresésnél is gyorsabb volt.

Amúgy igaz, nem kellett folyamatosan helyrehozni, elég volt akkor, ha nem terhelte más a rendszert.

12:20 voltam.