Varrott bináris fák - studopediya
Utóbbi esetben a meghatalmazást egy bináris fa csomópontoknak információkat tartalmazó mezőt és két mező, kommunikáció-mezők száma, amelynek az értéke nulla. mindig nagyobb, mint a kapcsolatok száma rámutatva, hogy a valóban létező helyek. Ezért az ilyen eljárás gyakran bizonyul hatástalannak tárolása fák memóriakihasználás szempontjából, különösen, ha az információs mező hasonló a méretét jelző.
Ábra. 6.1 - szimmetrikusan varrott jobb bináris fa
Mert meg kell valamilyen módon megkülönböztetni a normális linket üregelő menet, minden csomópont hozzáteszi két single-bit (logikai) területén tag: ltag és rtag. Ha true tag. megfelelő kommunikációs területen egy közös kötvény esetén az érték false - üregelő menet.
Ebben a tekintetben a hagyományos bináris fa node szerkezet képviselők
Node tűzött bináris fa szerkezete más
Logikai mező a varrott fa vehet a következő értékeket.
1. ltag = true. Ezért, bal oldalon egy hagyományos kötés.
2. ltag = false. Ezért, bal jelzi a megelőző csomópont.
3. rtag = true. ezért jobb ez egy hagyományos kötés.
4. rtag = false. Ezért jobb jelzi a leszármazott csomópont.
Tekintsük beillesztését egy új csomópont a bal oldalon egy adott szimmetrikusan varrott bináris fa (ábra. 6.2). Ábra. 6.3 ábra az eredmény fát.
Ábra. 6.2 - eredetileg szimmetrikusan tűzött fa
Ábra. 5 - varrott fa behelyezése után egy új elemet
Itt akartam szúrni a tetején a bal oldali részfa vkachestve tetején A. Ha A nincs bal részfa. Ellenkező esetben az új csomópont között helyezkedik el az A és fia maradt.
Az egyszerűbb létrehozása és bejárás, egy további fejfájás Apex Head. amely arra szolgál, mint a prekurzor egy szimmetrikus áthaladó első csúcspont és a vevő az ő terminális csúcsot.
Együtt az előnyöket varrott fák: gyors bypass, nincs szükség a verem meg tudja határozni a jogelőd és jogutód csúcsok, vannak hátrányai. A felvétel egy új csomópont a fában több időt vesz igénybe, mert meg kell tartania két típusú kapcsolatok: strukturális és fonalak. Ezért varrott fákat kell használni azokban az alkalmazásokban, ahol a változások a fák ritkák, és mászott gyakran.