Bináris keresés fák
Definíció egy bináris fa keresés (bináris keresés Tree BST)
Piros-fekete fák (piros-fekete fa, RB-fa)
Összehasonlító jellemzőit a sebesség a különböző adatstruktúrák

Definíció egy bináris fa keresés (bináris keresés Tree BST)
Binary keresési fa (MDC) nevű fa minden amelynek csúcsai vannak elrendezve, hogy minden egyes csomóponthoz legfeljebb két gyermek (nevezzük őket a bal és jobb), és minden csomópont a gyökér kivételével szülője. Top, amelynek nincs leszármazottai, az úgynevezett lap. Magától értetődik, hogy minden csomópont felel meg egy elemet, vagy több elem, bizonyos kulcsfontosságú értékek, a továbbiakban a kulcsot. Általában egyik csúcsa felel meg az egyik eleme, ezért ezek a feltételek lehetővé veszteség nélkül tekinthető szinonimák, bár meg kell emlékezni, hogy ez nem így van egyes megvalósítások. A fenti algoritmusok, úgy véljük, hogy az egyik csúcs csak egy eleme. Ezért fogjuk használni a koncepció a felső és a tetején a legfontosabb adatokat, azaz az adatokat kulcs és a megfelelő elemet a csúcs. Azt is meg fogják érteni beszúrásával tetején kiegészítve a tetejét a megadott érték az elem és hozzá jelek a szülő és leszármazottai érvényes értékeket. Ez a gomb minden műveletet az összehasonlító elemeket. Az elem is tartalmazhat kapcsolatos adatokat a kulcs. A gyakorlatban az adatok az elem része lehet használni, mint egy kulcs. A kulcs is lehet tárolni, mint egy egyetlen érték. MDC segítségével az alábbi műveleteket:
- Keresés a tetején a gombot.
- Meghatározása csúcsok a minimális és maximális értéke gombot.
- Ugrás az előző vagy a következő vertex meghatározott sorrendben kulcsokat.
- Helyezze be a tetején.
- Kiemelhető.
Bináris fa lehet logikailag osztva szinten. A gyökér a fa a nulla szintet, a leszármazottai a gyökér - az első szinten, utódaik - a második stb A mélysége a fa a maximális szintet. mélység fogalmát is leírható az út, vagyis a mélységben a fa hossza a leghosszabb út a root levél, ha követi a szülő csomópont a gyermeknek. Minden fa tetején lehet tekinteni, mint a gyökér a részfa, amely meghatározza egy adott vertex és minden leszármazottja ez a csomópont, a közvetlen és közvetett. Így a fa lehet leírni, mint egy rekurzív szerkezetét. keresés a hatékonyság fa közvetlenül kapcsolódik az egyensúlyát, vagyis a maximális különbség a mélység a bal és jobb oldali részfa összes csomópontja. Két szélsőséges esetben - a kiegyensúlyozott bináris fa (ahol minden szinten van egy sor csúcsok) és egy degenerált fa, ahol minden szinten szükség van a tetején egy. A degenerált fa egyenértékű a láncolt lista. A végrehajtás az összes főbb műveletek mélységének arányában a fa. Így, a nagy sebességű kereső a DCF leírások változhat O (log2 N) abban az esetben, a teljes fa O (N) - esetén egy degenerált.
DCF lehet használni, mint végrehajtásába absztrakciók, mint egy rendezett listát, egy szótár (egy sor megfelelések „kulcs-érték”), prioritási sort, és így tovább.
Végrehajtása során a fa mellett a legfontosabb érték a (kulcs), és az adatok is tárolásra három mutató: a szülő (nettó), balra (bal) és a jobb (jobb) leszármazottai. Ha a szülő vagy a gyermek nem egy mutatót üzletek nulla (NULL, NIL) értéket.
bináris keresési fa rendezési tulajdonság
Ha x - egy tetszőleges csúcs a PDD és a vertex y a bal felső sub x, akkor y.key <= x.key. Если x – это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y.key>= X.key. Az ingatlan az következik, hogy ha y.key == x.key, akkor a csúcs y lehet a bal és a jobb részfa viszonyított x csúcs.
Nem szabad elfelejteni, hogy a jelenléte több csúcsot azonos kulcs értéke egyes algoritmusok nem fog megfelelően működni. Például a keresési algoritmus mindig vissza a mutatót csak egy csúcsot. Ezt a problémát meg lehet oldani tárolja az elemeket azonos kulcsok ugyanazon a tetején egy listát. Ebben az esetben mi fogja ugyanazt a vertex több elemből, de az ügy nem tekinthető a cikkben.
Ez egy bináris keresési fa:
Lehetséges megoldások DCF
Háromféle módon dolgozni körül: Közvetlen (előrendelésre), Cross (inorder) Fordított (postorder).
- Közvetlen kiiktatás: önköltsége adott csúcsban, a bal részfa a csomópont, majd a jobb oldali részfa a csomópont.
- Keresztirányú kiiktatás: önköltsége bal részfa a csúcsok, akkor ez a csúcs, majd a jobb oldali részfa a csomópont. Csúcsok ugyanazt fogja követni a nem csökken (a kulcs kulcs) sorrendben.
- Fordított kiiktatás: önköltsége bal részfa a csúcsok, majd jobbra, akkor ez csúcs.
A 3. ábrán, a vertex bejárás meghatározott sorrendben számok, azt feltételezzük, hogy a csúcsok maguk vannak elrendezve úgy, hogy kialakítjuk DCF.
A leggyakrabban használt cross-kerek, mint minden más módon megkerülni egymást követő csúcsok nem köti a feltételeket a kapcsolatot.
Keresés felsők a PDD
Keresés Az ötlet egyszerű. A kereső algoritmus a PDD eredendően rekurzív. A leírás legegyszerűbb használni a koncepció egy részfa. A keresés elindul a gyökér, amely figyelembe, mint a gyökér a jelenlegi részfa és annak fő összehasonlítjuk a kívánt elemet. Ha ezek egyenlőek, akkor nyilvánvaló, hogy a keresés vége. Ha a legfontosabb az, hogy keresünk, kiderült, hogy nagyobb, mint a jelenlegi, akkor nyilvánvaló, hogy a kívánt csúcs található, a jobb részfa, egyébként - a bal oldalon. Továbbá, ezt a műveletet megismételjük a bal vagy a jobb részfa. A hagyományos kódot, ez a következőképpen írható le:
Keresés a tetején egy minimális és maximális értéket a kulcshoz
Top minimum és maximum érték megtalálható a kulcsot, séta fel a bal (jobb) jeleket a gyökér (amíg el nem érjük NIL). Visszatérési érték - egy mutatót a tetején a minimum (maximum) érték a kulcs.
Megtaláljuk a következő és az előző csúcsok a PDD
Ahhoz, hogy megtalálja az előző és a következő csomópont, szükség van ismét felidézni a rendezési tulajdonság. Tekintsük ezt a példát TreeNext funkciót. Úgy véli, a két esetben. Ha a jobb oldali részfa nem üres, akkor a csúcsát a jobb részfa a minimális kulcs értékét és lesz a következő. Ha a jobb oldali részfa üres, akkor menjünk fel, amíg meg nem találja a teteje, ami a bal gyermek a szülő. Ez a szülő (ha van ilyen), és lesz a következő tetején. Visszatérési érték - egy mutatót a tetején a következő (előző) értéke egy billentyűt, vagy NIL, ha nincs ilyen csúcs.
Hozzáadása vertex
Hozzáadása egy csúcs a PDD jár néhány probléma. Hozzáadása után a DCF kell tartani a sorrendben ingatlan, ami azt jelenti, hogy az első, bárhol nem lehet hozzáadni. Ezért, mielőtt behelyezi a felső, meg kell találni a megfelelő helyet, akkor van egy hely, után, amelynek során a fa megtartja rendezési tulajdonság. Más szóval, meg kell egy hely után a tetején a legfontosabb a legmagasabb az összes kisebbik.
Kiemelhető
Problémák merülnek fel, amikor eltávolítja. Meg kell őrizni a megrendelő tulajdonában MDC. Ha eltávolítjuk a három eset lehetséges: eltávolítottuk a felső nincs gyermeke, hogy eltávolította a tetején van egy leszármazottja, és eltávolította a felső két gyerek. Ha a gyermek nem rendelkezik, akkor egyszerűen távolítsa el a felső. Ha egy gyermek egyedül, akkor távolítsa el a felső, akkor „vágott”, rámutatva, hogy a szülei, mint a gyermek az egyetlen rendelkezésre álló leszármazottja levehető tetején. Ha a leszármazottai két további lépésekre van szükség. Meg kell találni a következő a törölt (sorrendben kulcsok) top, másolja a tartalmát (a kulcs és adat) egy levehető felső (most nem lesz eltávolítva fizikailag, hanem logikailag eltűnnek), majd távolítsa el a felső (ő nem marad gyermek). Először TreeDelete funkció megkeresi a legjobb, hogy törli, akkor nodeTemp változó kap egy olyan mutatót, amely a már meglévő gyermek így a felső (vagy NIL, ha a gyerekek nem rendelkeznek). Ezután a hegyet eltávolítják a fáról, és az esetek külön foglalkoznak, amikor a gyermekek nem rendelkeznek, és ha az eltávolítható csúcs - a gyökér a fa. Visszatérési érték - egy mutatót a távvezérlő tetején. Rajta nincs utalás a fa, de még mindig úgy memóriát. Az idő a tényleges eltávolítása függ a használt memória allokációs módszerek.
NIL, NULL, és a kis trükkök
Most mindenhol CTree osztály változó lehet használni treeNil. Az előnyök nyilvánvalóak. Miután eltöltött mintegy tizenkét (3 * sizeof (CTree *)) bájt memóriát, már egyszerűsíti és gyorsítja a fejlesztési program.
A fő probléma a DCF
A fő probléma a használata a DCF hogy a beszúrások és eltávolítását csúcsok, megőrzésének biztosítása tulajdon érdekében, hogy nem segíti, hogy optimalizálja az alapvető műveleteket az MDC. Például, ha a behelyezett a PDD sorrendben növekvő vagy csökkenő számban, ez lesz, sőt, kétszeresen láncolt lista, és az alap működését időt vesz igénybe arányos a csúcsok száma, nem pedig a logaritmus.
Így O (log2 N) nagyságrendű teljesítményt kell fára volt a lehető legmagasabb egyenleg (azaz valószínűleg kisebb magasság). Általában többféle egyensúly kiosztott. A teljes egyensúly, amikor a fa tetején az egyes csúcsok száma a bal és a jobb oldali részfa nem tér el több mint 1 Sajnos, ez az egyensúly nehéz elérni a gyakorlatban. Ezért a gyakorlatban, hogy használják a kevésbé szigorú formák egyensúlyát. Például a magyar matematikus GM Adelson-Belsky és E.M.Landisom elvek AVL fák fejlesztettek ki. Az AVL fa minden csúcsa mindkét részfa fa mélysége nem térhet el több mint 1 másik „fejlett” fa nézet az úgynevezett piros-fekete fák. AVL fák nagyobb egyensúly a fa, de a fenntartási költségei fölé. Mivel a gyakorlatban a különbség a kettő közötti egyensúly típusú fák nem magas, gyakran használják a piros-fekete fák.
Piros-fekete fák (piros-fekete fa, RB-fa)
Szóval, az egyik módja annak, hogy oldja meg a fő problémát a használata a DCF piros-fekete fák. Vörös és fekete (a név történelmileg kapcsolódó kártya miatt könnyen megoldható egyszerű modellek) fák (PSA) - a DCF, minden csúcsa, amely tárolja még egy további logikai mező (színes), feltüntetve a szín: piros vagy fekete. Tény, hogy a PSA garantált, hogy a szinteket a két levél nem tér el több mint kétszerese. Ez az állapot elegendő ahhoz, hogy egy nagy sebességű keresési teljesítmény közel O (log2 N). Amikor behelyezi / cserélje ki a további lépéseket az egyensúly a fa, amely nem lassítja le a fáról. A bemutató algoritmusok azt feltételezzük, hogy NIL - egy mutatót a tetején a dummy, és a műveletek (NIL) .left (NIL) .right (NIL) .color értelme. Azt is feltételezzük, hogy minden csomópont két gyermeke van, és csak a NIL nincs gyermeke. Így minden csúcsában válik a belső (amelynek leszármazottai, bár fiktív), és a levelek csak dummy vertex nulla.
tulajdonságok PSA
- Minden csúcs lehetnek piros vagy fekete. Színtelen felsők, vagy tetejét egy másik színt nem lehet.
- Minden levél (NIL) fekete.
- Ha a csomópont piros, akkor mind a gyerekek - fekete.
- Egészen a gyökér a levelek tartalmazzák az azonos számú fekete csomópontokat.
Példa PSA tekintve pozícióinkat a 4. ábrán látható Megjegyezzük, hogy a felső 9 lehet piros, de a jövőben csak azokat fák amelynek gyökere fekete. Mi ezt annak érdekében, hogy root leszármazottai bármilyen színű.
inszerciókat és deléciókat a csúcsok a PSA tulajdonságait árthatnak PSA. Ezen lehetőségek visszaállításához, akkor meg kell átfestés néhány csúcs, és módosítsa a szerkezet a fa. Szerkezetének megváltoztatása használt műveletek, az úgynevezett forgatást. Visszatérve PSA tulajdonságait, forgás is az egyensúly helyreállítása, a fa. A forgatásokat bal és jobb, ezek az 5. ábrán látható.
Mint látható, forgás közben a csúcsok nem sértik a rendelési tulajdonságait.
Az eljárás RBTLeftRotate feltételezte, hogy node.right! = NIL. Az eljárás RBTRightRotate feltételezte, hogy node.left! = NIL.
6. táblázat eltávolítása kulcsfontosságú elem (véletlen kulcsok)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
7. táblázat hozzáadása elemet (növekvő billentyűk)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
8. táblázat A keresés elem (növekvő billentyűk)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
9. táblázat eltávolítása a kulcs elem (növekvő kulcsok)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
10. táblázat hozzáadása elemet (véletlen kulcsok)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
11. táblázat A keresés elem (véletlen kulcsok)
Folyamatosan rendezett tömböt
Nem rendezett tömböt
Array postsortirovkoy
12. TÁBLÁZAT eltávolítása a kulcs elem (véletlen kulcsok)
Világosan látható, hogy a nagyobb méretű fák gyönyörködtető elem, és még jelentősen felülmúlják tömbök. Így nyilvánvaló, hogy a választás a adatstruktúrák erősen függ a becsült elemek száma és mérete. Végezetül szeretném elmondani, hogy a helyes választás az adat struktúra egyik fő pontokat, amelyek meghatározzák a teljesítményt a programot. Ezért választotta óvatosan, gondolkodás révén minden lehetséges - a legvalószínűbb és legrosszabb esetben.