Expression Fák - studopediya
Ábra. 72. kizárása csomópontok dichotomikus fa
Ábra. 71. A degenerált dichotom fa
Ábra. 70. Dihomicheskie fák
A dichotomikus keresés Csomópontfa a megadott kulcs értéke összehasonlítása alapján egy előre meghatározott kulcsot a gyökér kulcs. Az egyetlen összehasonlítás mehetsz balra vagy jobbra al-fa gyökere. Ha dichotoma fa kiegyensúlyozott, akkor a csomópont egy adott keresési kulcs értéke igényel legfeljebb [log2 N] 1 összehasonlításokat, ahol N - a csomópontok száma dichotóm fa. Abban az esetben, ha több billentyű van lineárisan rendezett fa dichotoma hatékonyan degenerates egy lineáris lista (ábra. 71). Ebben az esetben, a keresés körében végzett N csomópontok maximális N összehasonlítások és átlagban - az N / 2 összehasonlítás.
dichotom fa struktúra határozza meg a szekvencia hozzárendelési kulcsok. Szekvenciák gomb hozzárendelések
¨ Fügefa. a) - 150, 70, 300, 100, 30, 200, 50;
¨ Fügefa. b) - 100, 50, 30, 70, 200, 150, 300;
¨ Fügefa. - 300, 200, 150, 100, 70, 50, 30.
Befogadás dichotoma Csomópontfa a megadott kulcs értéke elő az alábbiak szerint: ha a csomópont keresési vezetett zsákutcába (vagyis az üres részfájának jelölve a referenciaérték NIL), majd egy új csomópontot kell szerepelnie a fában helyett egy üres részfa. Tehát egy node szerepel a fa mindig dichotoma mint a fal.
Eljárás Ins_Node (var root: PDtree;
Ha a gyökér nem tartalmaz a keresési kulcsot, az eljárás nevezi magát rekurzív folytatni a keresést, vagy a jobb vagy a bal fele a fa. Abban az esetben, ha a végére ért az ágak és nem találta meg a kívánt gombot, az újabb szakértői ezzel kulcs értékét. A rekurzió ér véget, amikor a kívánt kulcsot talált (ebben az esetben egy üzenet arról, hogy lehetetlen újra aktiválni a node), vagy eléri a végén egy ág (ebben az esetben egy új csomópont szerepel a fa).
Mi bejárás algoritmus alapján a csomópont kapcsolási eljárások dichotom fát?
Amikor postroeniidihotomicheskogo fa csomópontok N az egyes N lépéssorozatot azért végzik, hogy adja meg a behelyezés csomópont kulcs értéke (Ins_Node eljárás hívás). Ezért a komplexitás létrehozásának dichotóm fa N csomópont becsült N * log2 N műveleteket.
Amikor udaleniiuzla. egy adott kulcs értéke egy dichotóm fa, három esetben:
1. A csomópontot a megadott kulcs érték a fában nincs.
2. összeállítás adja meg a kulcs értéke nem több, mint egy leszármazottja. Ebben az esetben a kizárt csomópont helyébe utódai.
3. A Node, hogy meghatározza a legfontosabb érték két leszármazottai. Ebben az esetben a kizárt csomópont helyére, vagy a jobb szélső csomópontja bal részfa. nem több, mint egy gyerek, vagy a bal oldali legszélső csomópont jogával részfa. nem több mint egy leszármazottja.
Példa kivételével csomópontok dichotom fa ábrán látható. 72.
A pusztítás bármilyen bináris fa sorozatos felszabadulását memória területeket, ahol vannak elrendezve tárgyak tárolására csomópontok vissza őket, hogy a kupac. Ennek eredményeként a megsemmisítése a fa kiürül.
Mi bejáráshoz kell megsemmisítésére használt bináris fa?
expressziós fa - egy bináris fa, amely a gyökér csomópont attribútumok tárolt műveleteket, és a terminál csomópontok - expressziós operandusok (változók vagy állandók). kifejezésfa ábrán látható. 73.