Bináris keresési fa – strukturált adatbázis, amely csomópontokat tartalmaz, két hivatkozást más csomópontokhoz, jobbra és balra. A csomópontok az osztály olyan objektumai, amelyekben adatok vannak, a NULL pedig a fa végét jelölő jel.
Gyakran BST-nek nevezik, amelynek van egy speciális tulajdonsága: a gyökérnél nagyobb csomópontok tőle jobbra, a kisebbek pedig balra helyezkednek el.
Általános elmélet és terminológia
A bináris keresési fában minden csomópont – a gyökér kivételével – egy irányított éllel van összekötve egyik csomóponttól a másikig, amelyet szülőnek nevezünk. Mindegyik tetszőleges számú csomóponthoz köthető, amelyeket gyermekeknek nevezünk. A "gyermekek" nélküli csomópontokat leveleknek (külső csomópontoknak) nevezik. Azokat az elemeket, amelyek nem levelek, belsőnek nevezzük. Az azonos szülővel rendelkező csomópontok testvérek. A legfelső csomópontot gyökérnek nevezzük. A BST-ben minden csomóponthoz rendeljen egy elemet, és győződjön meg arról, hogy be van állítva egy speciális tulajdonság.
Fa terminológia:
- Egy csomópont mélysége a gyökértől a csomópontig meghatározott élek száma.
- Egy csomópont magassága a tőle a legmélyebb levélig meghatározott élek száma.
- A fa magasságát a gyökér magassága határozza meg.
- A bináris keresőfa egy speciális kialakítás, ez biztosítja a legjobb magasság és csomópontok számának arányát.
- H magasság N csomóponttal legfeljebb O (log N).
Ezt könnyen bebizonyíthatja, ha minden szinten megszámolja a csomópontokat, a gyökértől kezdve, feltételezve, hogy ez tartalmazza a legtöbbet: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Ezt h-ra megoldva h=O (log n).
A fa előnyei:
- Tükrözi az adatok szerkezeti kapcsolatait.
- A hierarchiák megjelenítésére szolgál.
- Gondoskodjon hatékony telepítésről és keresésről.
- A fák nagyon rugalmas adatok, lehetővé téve az alfák minimális erőfeszítéssel történő mozgatását.
Keresési mód
Általában annak megállapításához, hogy egy érték szerepel-e a BST-ben, indítson el egy bináris keresési fát a gyökerénél, és állapítsa meg, hogy megfelel-e a követelményeknek:
- legyen a gyökérnél;
- legyen a gyökér bal részfájában;
- a gyökér jobb oldali részfájában.
Ha egyetlen alapregiszter sem teljesül, akkor rekurzív keresést hajt végre a megfelelő részfában. Valójában két alapvető lehetőség van:
- A fa üres – hamis értéket ad vissza.
- Az érték a gyökércsomópontban van – adja vissza true.
Meg kell jegyezni, hogy egy kidolgozott sémával rendelkező bináris keresőfa mindig a gyökértől a levélig tartó útvonalon kezdi meg a keresést. A legrosszabb esetben egészen a levélig megy. Ezért a legrosszabb idő arányos a gyökértől a levélig vezető leghosszabb út hosszával, ami a fa magassága. Általában ilyenkor tudnia kell, hogy mennyi ideig tart a keresés a fában tárolt értékek számának függvényében.
Más szóval, kapcsolat van a BST csomópontjainak száma és egy fa magassága között, annak "alakjától" függően. A legrosszabb esetben a csomópontoknak csak egy gyermeke van, és a kiegyensúlyozott bináris keresési fa lényegében egy linkelt lista. Például:
50
/
10
15
30
/
20
Ennek a fának 5 csomópontja van, magassága=5. A 16-19 és 21-29 tartományban lévő értékek megkereséséhez a gyökértől a levélig (a 20-as értéket tartalmazó csomópont) a következő útvonalra van szükség, pl., a csomópontok számával arányos időbe telik. Legjobb esetben mindegyiküknek 2 gyermeke van, és a levelek ugyanabban a mélységben helyezkednek el.
Ennek a bináris keresőfának 7 csomópontja van, magassága=3. Általában egy ilyen fa (teljes fa) magassága megközelítőleg log 2 (N), ahol N a csomópontok száma a fában. A log 2 (N) értéke az a szám (2), ahányszor N osztható, mielőtt elérné a nullát.
Összefoglalva: a BST-ben történő kereséshez szükséges legrosszabb idő az O (fa magassága). A legrosszabb "lineáris" fa az O(N), ahol N a fa csomópontjainak száma. A "teljes" fa legjobb esetben O(log N).
BST bináris beszúrás
Kíváncsi, hol legyenaz új csomópont a BST-ben található, érteni kell a logikát, ott kell elhelyezni, ahol a felhasználó találja. Ezenkívül emlékeznie kell a szabályokra:
- Duplikációk nem engedélyezettek, az ismétlődő érték beszúrásának kísérlete kivételt eredményez.
- A nyilvános beillesztési módszer egy segítő rekurzív "segítő" módszert használ a tényleges beszúráshoz.
- Az új értéket tartalmazó csomópont mindig levélként kerül be a BST-be.
- A nyilvános beszúrási metódus void-ot ad vissza, de a helper metódus egy BSTnode-ot ad vissza. Ezzel azt az esetet kezeli, amikor a neki átadott csomópont null.
Általában a segítő módszer azt jelzi, hogy ha az eredeti bináris keresési fa üres, akkor az eredmény egy egy csomóponttal rendelkező fa. Ellenkező esetben az eredmény egy mutató lesz ugyanarra a csomópontra, amelyet argumentumként adtak át.
Törlés bináris algoritmusban
Ahogyan az várható volt, egy elem törléséhez meg kell találni egy csomópontot, amely tartalmazza az eltávolítandó értéket. Számos dolog van ebben a kódban:
- A BST segítő, túlterhelt törlési módszert használ. Ha a keresett elem nincs a fában, akkor a segítő metódus végül n==null értékkel kerül meghívásra. Ez nem tekinthető hibának, a fa ebben az esetben egyszerűen nem változik. A delete helper metódus egy értéket ad vissza – egy mutatót a frissített fára.
- Amikor egy levelet eltávolítanak, a bináris keresési fából való eltávolítás a szülő megfelelő gyermekmutatóját nullára állítja, vagy a gyökerét nullára állítja, ha az eltávolította csomópont gyökér, és nincs gyermeke.
- Ne feledje, hogy a törlési hívásnak a következők egyikének kell lennie: root=delete (root, key), n.setLeft (delete (n.getLeft (), kulcs)), n.setRight (delete(n. getRight(), kulcs)). Így mindhárom esetben helyes, hogy a delete metódus egyszerűen nullát ad vissza.
- Ha a törlendő értéket tartalmazó csomópont keresése sikeres, három lehetőség közül választhat: a törölni kívánt csomópont egy levél (nincs gyermeke), a törölni kívánt csomópontnak egy gyermeke van, két gyerekek.
- Ha az eltávolítandó csomópontnak egy gyermeke van, egyszerűen lecserélheti egy gyermekre, és egy mutatót visz vissza a gyermekre.
- Ha a törölni kívánt csomópontnak nulla vagy 1 gyermeke van, akkor a törlési módszer "követi az utat" a gyökértől az adott csomópontig. Tehát a legrosszabb idő arányos a fa magasságával, mind a keresésnél, mind a beszúrásnál.
Ha az eltávolítandó csomópontnak két gyermeke van, akkor a következő lépéseket kell végrehajtani:
- Keresse meg a törölni kívánt csomópontot, kövesse a gyökértől a hozzá vezető útvonalat.
- Keresse meg v legkisebb értékét a jobb oldali részfában, haladva a levélhez vezető útvonalon.
- Rekurzív módon távolítsa el a v értékét, kövesse ugyanazt az utat, mint a 2. lépésben.
- Így a legrosszabb esetben a gyökértől a levélig vezető utat kétszer hajtják végre.
A bejárások sorrendje
A bejárás egy olyan folyamat, amely felkeresi a fa összes csomópontját. Mivel a C bináris keresési fa nemlineáris adatstruktúra, nincs egyedi bejárás. Például néha több bejárási algoritmusa következő két típusba sorolva:
- átkelés mélysége;
- első menet.
Csak egyféle szélességi keresztezés létezik – a szint megkerülése. Ez a bejárás a csomópontokat szinttel lefelé és balra, felül és jobbra látogatja.
Három különböző típusú mélységi kereszteződés létezik:
- Előrendelés átadása – először keresse fel a szülőt, majd a bal és a jobb oldali gyermeket.
- Sorrendbe adás - a bal oldali gyermek, majd a szülő és a jobb gyermek meglátogatása.
- Múlt az utórendelésen – a bal oldali gyermek meglátogatása, majd a jobb oldali gyermek, majd a szülő meglátogatása.
Példa egy bináris keresési fa négy bejárására:
- Előrendelés – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Rendelés - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Utólagos rendelés - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Az ábra a csomópontok látogatási sorrendjét mutatja. Az 1-es szám az első csomópont egy adott bejárásban, a 7 pedig az utolsó csomópont.
Ezek az általános bejárások egyetlen algoritmusként is ábrázolhatók, feltételezve, hogy minden csomópontot háromszor látogatnak meg. Az Euler-túra egy bináris fa körüli séta, ahol minden élt falként kezelnek, amelyen a felhasználó nem léphet át. Ebben a séta során az egyes csomópontokat vagy a bal oldalon, az alatta vagy a jobb oldalon keresik fel. Az Euler-túra, amely a bal oldali csomópontokat keresi fel, az elöljárószó megkerülését okozza. Amikor az alábbi csomópontokat meglátogatja, sorrendben bejárja őket. És amikor a jobb oldali csomópontokat meglátogatják - kaplépésről lépésre.
Navigáció és hibakeresés
A fán való könnyebb navigáció érdekében hozzon létre olyan függvényeket, amelyek először ellenőrzik, hogy a bal vagy a jobb oldali gyermekről van-e szó. Egy csomópont pozíciójának megváltoztatásához könnyen elérhetőnek kell lennie a szülőcsomóponton lévő mutatóhoz. A fa helyes megvalósítása nagyon nehéz, ezért ismernie kell és alkalmaznia kell a hibakeresési folyamatokat. Egy implementációval rendelkező bináris keresési fa gyakran tartalmaz olyan mutatókat, amelyek valójában nem jelzik a haladási irányt.
Ennek kiderítésére egy függvényt használnak, amely ellenőrzi, hogy a fa helyes-e, és segít sok hiba megtalálásában. Például ellenőrzi, hogy a szülőcsomópont gyermekcsomópont-e. Az assert(is_wellformed(root)) segítségével sok hiba idő előtt elkapható. Néhány megadott töréspont segítségével ezen a függvényen belül azt is meghatározhatja, hogy pontosan melyik mutató hibás.
Funkció Konsolenausgabe
Ez a funkció a teljes fát a konzolra helyezi, ezért nagyon hasznos. A fa kimeneti cél végrehajtási sorrendje a következő:
- Ehhez először meg kell határoznia, hogy milyen információk jelenjenek meg a csomóponton keresztül.
- És azt is tudnod kell, hogy milyen széles és magas a fa, hogy számolj azzal, mennyi helyet kell hagyni.
- A következő függvények számítják ki ezt az információt a fára és az egyes részfákra vonatkozóan. Mivel a konzolra csak soronként írhat, a fát is soronként kell kinyomtatnia.
- Most más módra van szükségünk a visszavonulásraaz egész fa, nem csak sorról sorra.
- A dump funkció segítségével elolvashatja a fát és jelentősen javíthatja a kimeneti algoritmust, ami a sebességet illeti.
Ezt a funkciót azonban nehéz lesz használni nagy fákon.
Konstruktor és destruktor másolása
Mivel a fa nem egy triviális adatstruktúra, jobb, ha implementál egy másoláskonstruktort, egy destruktort és egy hozzárendelési operátort. A destruktort könnyű rekurzívan megvalósítani. Nagyon nagy fák esetén képes kezelni a "halom túlcsordulást". Ebben az esetben iteratívan fogalmazódik meg. Az ötlet az, hogy az összes levél közül a legkisebb értéket képviselő levelet távolítsuk el, tehát az a fa bal oldalán legyen. Az első levelek levágása újakat hoz létre, és a fa összezsugorodik, míg végül meg nem szűnik.
A másolás konstruktor rekurzívan is megvalósítható, de legyen óvatos, ha kivételt dob. Ellenkező esetben a fa gyorsan zavarossá és hibákra hajlamossá válik. Ezért az iteratív verziót részesítik előnyben. Az ötlet az, hogy át kell menni a régi fán és az új fán, ahogy a destruktorban tenné, klónozva a régi fában lévő összes csomópontot, de az újakat nem.
Ezzel a módszerrel a bináris keresőfa megvalósítás mindig egészséges állapotban van, és a destruktor még hiányos állapotban is eltávolíthatja. Ha kivétel történik, csak utasítania kell a destruktort a félkész fa törlésére. hozzárendelés operátorkönnyen megvalósítható a Copy & Swap segítségével.
Bináris keresési fa létrehozása
Az optimális bináris keresőfák hihetetlenül hatékonyak, ha megfelelően kezelik őket. Néhány szabály a bináris keresési fákra:
- Egy szülőcsomópontnak legfeljebb 2 gyermekcsomópontja van.
- A bal oldali gyermekcsomópont mindig kisebb, mint a szülőcsomópont.
- Egy érvényes gyermekcsomópont mindig nagyobb vagy egyenlő, mint a szülőcsomópont.
A bináris keresési fa felépítéséhez használt tömb:
- Egy alap egész szám tömb hét értékből, rendezetlen sorrendben.
- A tömb első értéke 10, tehát a fa felépítésének első lépése egy 10-es gyökércsomópont létrehozása, amint az itt látható.
- A gyökércsomópont-készlettel az összes többi érték ennek a csomópontnak a gyermeke lesz. A szabályokra hivatkozva a 7-es fához való hozzáadásának első lépése az, hogy összehasonlítjuk a gyökércsomóponttal.
- Ha a 7-es érték kisebb, mint 10, akkor ez lesz a bal oldali gyermekcsomópont.
- Ha a 7 érték nagyobb vagy egyenlő, mint 10, akkor jobbra fog mozogni. Mivel a 7-ről ismert, hogy kisebb, mint 10, ez a bal oldali gyermekcsomópont.
- Rekurzív összehasonlítások végrehajtása az egyes elemeknél.
- Ugyanazt a mintát követve végezze el ugyanazt az összehasonlítást a tömb 14. értékével.
- A 14-es érték összehasonlítása a 10-es gyökércsomóponttal, annak tudatában, hogy a 14 a helyes gyermek.
- Sétálva a tömbön,gyere ide: 20.
- Kezdje össze a tömböt 10-zel, amelyik a nagyobb. Tehát menjen jobbra, és hasonlítsa össze a 14-gyel, ő elmúlt 14, és nincs gyereke a jobb oldalon.
- Ha az érték 5, hasonlítsa össze 10-el. Mivel az 5 kisebb, mint 10, lépjen balra, és hasonlítsa össze a 7-tel.
- Tudva, hogy az 5 kevesebb, mint 7, menjen lefelé a fán, és hasonlítsa össze az 5-öt 1 értékkel.
- Ha 1-nek nincs gyermeke, és az 5 nagyobb 1-nél, akkor az 5 1 csomópont érvényes gyermeke.
- Végül szúrja be a 8-as értéket a fába.
- Ha a 8 kisebb, mint 10, mozgassa balra, és hasonlítsa össze a 7-tel, a 8 nagyobb, mint 7, tehát mozgassa jobbra, és fejezze be a fát, így a 8 a 7 megfelelő gyermeke lesz.
1
Az optimális bináris keresőfák egyszerű eleganciájának lekérése és értékelése. Mint sok programozási téma, a bináris keresési fák ereje abból fakad, hogy képesek az adatokat kis, kapcsolódó komponensekre felbontani. Mostantól a teljes adatkészlettel szervezett módon dolgozhat.
Lehetséges bináris keresési problémák
A bináris keresőfák nagyszerűek, de van néhány figyelmeztetés, amelyet szem előtt kell tartani. Általában csak akkor hatékonyak, ha kiegyensúlyozottak. A kiegyensúlyozott fa olyan fa, amelybena fa bármely csomópontjának részfáinak magassága közötti különbség legfeljebb egy. Nézzünk egy példát, amely segíthet tisztázni a szabályokat. Képzeljük el, hogy a tömb rendezhetőként kezdődik.
Ha egy bináris keresési fa algoritmust próbál futtatni ezen a fán, az pontosan úgy fog működni, mintha csak iterálna a tömbön, amíg meg nem találja a kívánt értéket. A bináris keresés ereje a nem kívánt értékek gyors kiszűrésének képességében rejlik. Ha egy fa nincs kiegyensúlyozott, akkor nem fogja biztosítani ugyanazokat az előnyöket, mint egy kiegyensúlyozott fa.
A bináris keresési fa létrehozásakor nagyon fontos megvizsgálni azokat az adatokat, amelyekkel a felhasználó dolgozik. Integrálhat rutinokat, például tömb véletlenszerűsítést, mielőtt egy bináris keresési fát implementálna egész számokra, hogy kiegyensúlyozza azt.
Bináris keresési számítási példák
Meg kell határoznunk, hogy milyen fa jön létre, ha 25-öt beszúrunk a következő bináris keresési fába:
10
/
/
5 15
/ /
/ /
2 12 20
Ha x-et beszúrunk egy T fába, amely még nem tartalmaz x-et, az x kulcs mindig egy új levélbe kerül. Ezzel kapcsolatban az új fa így fog kinézni:
10
/
/
5 15
/ /
/ /
2 12 20
25
Milyen fát kapna, ha beszúrná a 7-est a következő bináris keresőfába?
10
/
/
5 15
/ /
/ /
2 12 20
Válasz:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
A bináris keresési fa bármilyen objektum tárolására használható. A linkelt lista helyett a bináris keresési fa használatának az az előnye, hogy ha a fa ésszerűen kiegyensúlyozott, és jobban hasonlít egy "teljes" fához, mint egy "lineárishoz", akkor a beillesztési, keresési és az összes törlési művelet végrehajtható. O(log N) idő.
