Bináris fa tárolása?
Biráris fa adatait szeretném eltárolni a lehető leggazdaságosabban, természetesen úgy, hogy a fa az állományból visszaállítható legyen.
A tárolandó adatok tipusa byte.
Előre is köszönöm.
válasza:#9: Ill még valami... a példád kicsit sántít, helyesen így lenne, nem?
5, -, 3, -, -
Nyilván a fájl vége miatt akár el is hagyható az utolsó kettő, de az picit növeli a beolvasás logikáját, hisz nézni kell vége van-e a fájlnak:) szóval érdemes kirakni ott is a "gyerekeket" (amik nincsenek)... mert ez csak a legjobboldalibb levélre hagyható el, a többi esetben amúgyis kell, tehát maximum 2 érték, szövegfájlban maximum 4 byte.
válasza:"Nyilván a fájl vége miatt akár el is hagyható az utolsó kettő, de az picit növeli a beolvasás logikáját, hisz nézni kell vége van-e a fájlnak"
Nem egészen értem, amúgy nem kell figyelni, hogy vége van-e a fájlnak?
válasza:Ami nekem eddig összejött:
A teljes fában tárolt értékek mennyiségét kiírom. Ez egy, esetleg két byte. ezután az elemeket eltárolom (bináris formában) soronkénti beolvasással, tehát,
első sor [X], második sor [X,X], harmadik sor [X,X,X,X], és így tovább. Amikor ezzel végeztem, akkor készítek egy leírót, egy map-et ami mutatja, hogy a fa mely pozícióján van érték. Ez úgy nézne ki, hogy elvileg egy teljes fát írna le, bitenként.
A fenti példa tartalmilag [1,11,1111]. Ha mondjuk a fenti példa úgy módosulna, hogy jobb részfa nem lenne, akkor azt nullákkal egészíteni ki (placeholder) valahogy így [1,10,1100].
Eddig ez talán a legtakarékosabb, csak az vele a gond, hogy ha nem teljes a fa, akkor sok bitre van szükség.
Bár most, ezt leírva és visszaolvasva, azt hiszem van egy jó lehetőség. Ki lehet használni azt az információt, amit a nulla hordoz, gondolok arra, hogy ha mondjuk a harmadik szinten behal a jobb oldali ág, akkor ezt a bitenkénti leírónál figyelembe lehet venni és nem szükséges fölöslegesen pakolni a nullákat.
Ez egy járható út, nem? Ennél jobbat a dologból talán ki sem lehet hozni, ha azt valószinűsítjük, hogy a fák szinte soha nem lesznek teljesek, a bennük tárolt értékek száma max. 200, a tárolás módja pedig bináris kell, hogy legyen.
válasza:"De akkor honnan tudjuk, hogy nem kell tovább olvasni?" pont a kötőjelekből. Ha az van, nincs bal/jobb fa.
"a bennük tárolt értékek száma max. 200"
Jól értem hogy max 200 csomópont van a fában? Akkor mit vacakolsz? Nem fájlba mented? A fájlendszer cluster mérete miatt amúgyis legalább 512 byte lesz, hiába csinálsz te 100 byteos filet valami varázslással...
Vagy pl adatbázisba mentesz millió ilyen fát?
válasza:kérdező: az általad leírt algoritmus ami eltárolja hogy melyik pozícióban van fának eleme nagyon nem takarékos. Már ha egy szinttel túllóg valamelyik ág, akkor kell annak a szintnek megfelelő mennyiségű bit, ami ugye exponenciálisan nő és már +1 szint esetén is elemszám*2.. tehát igazából a 10bit/csomópont a legjobb eddig.
Arról nem is beszélve, hogy nem csak helypazarló, de komplikált is az algoritmusod.
Mi a bajod a preorder bejárással?
Nem egészen.
Ez az adatszerkezet beágyazott rendszeren lesz használva. Ezért is fontos a méret csökkentése.
válasza:További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!