Bináris keresési fa
A számítástechnikában a bináris keresőfa vagy az ABR (angolul: bináris keresési fa vagy BST ) egy olyan adatstruktúra, amely egy halmazt vagy egy asszociatív tömböt képvisel, amelynek kulcsai egy teljesen rendezett halmazhoz tartoznak . A bináris keresőfa lehetővé teszi a gyors műveleteket a kulcs megtalálásához, a kulcs behelyezéséhez vagy törléséhez.
Meghatározás
Általános meghatározás
A bináris keresési fa olyan bináris fa , amelyben minden csomópontnak van egy kulcsa , oly módon, hogy a bal alfa minden csomópontjának kulcsa kisebb vagy egyenlő, mint az adott csomópont, és a jobb oldali rész minden csomópontjának kulcsa nagyobb, mint vagy ezzel egyenlő - az ABR megvalósításától függően az azonos értékű kulcsok tilosak vagy nem. Az általunk hozzáadott csomópontok a fa leveleivé válnak.
Konkrét meghatározások
- A bináris keresési fa akkor mondható teljesnek, ha a fa összes szintje kitöltve van, kivéve esetleg az utolsót, amelyen a bal oldali csomópontok találhatók.
- A tökéletes bináris fa egy teljes fa, amelynek összes levele azonos magasságban van (az utolsó szint teljesen elfoglalt).
- A bináris fáról azt mondják, hogy degenerált, ha minden csomópontjának legfeljebb egy gyermeke van.
- A bináris fa kiegyensúlyozott, ha a gyökértől a levélig minden út azonos hosszúságú.
Tevékenységek
Kutatás
A bináris fában egy adott csomópont keresése rekurzív folyamat . A gyökér vizsgálatával kezdjük. Ha a kulcsa a keresett kulcs, akkor az algoritmus leáll és visszaadja a gyökért. Ha szigorúan kevesebb, akkor a bal alfában van, amelyen ezt követően rekurzívan végezzük a keresést. Hasonlóképpen, ha a keresett kulcs szigorúan nagyobb, mint a root kulcs, a keresés a jobb alfában folytatódik. Ha olyan levélhez érünk, amelynek kulcsa nem a keresett, akkor tudjuk, hogy a keresett kulcs nem tartozik egyetlen csomóponthoz sem, így nem jelenik meg a kereső fában. Összehasonlíthatjuk egy bináris keresőfa feltárását a dichotómiás kereséssel, amely ugyanúgy halad, azzal a különbséggel, hogy közvetlenül egy tömb minden eleméhez megy a linkek követése helyett. A két algoritmus közötti különbség az, hogy a dichotóm keresésben feltételezzük, hogy van egy kritériumunk a tér két részre történő felosztásához, amely a fában történő keresés során nincs meg.
fonction Recherche(A,e) Si A = . retourner Faux Sinon A = (x,FilsGauche,FilsDroit) Si x = e retourner Vrai Sinon si e < x retourner Recherche(FilsGauche,e) Sinon retourner Recherche(FilsDroit,e)Ehhez a művelethez átlagos időre van szükség O-ban (log (n)) , de kritikus esetben O (n) -ben, ahol a fa teljesen kiegyensúlyozatlan, és összekapcsolt listának tűnik. Ez a probléma kizárt, ha a tengely kiegyenlítődik a behelyezés közbeni forgatással , ami túl hosszú listákat hozhat létre.
Beszúrás
A csomópont beillesztése kereséssel kezdődik: megkeressük a beillesztendő csomópont kulcsát; amikor egy levélhöz érkezünk, hozzáadjuk a csomópontot a levél gyermekeként, összehasonlítva annak kulcsát a levél kulcsával: ha alacsonyabb, akkor az új csomópont a bal oldalon lesz; különben helyes lesz.
fonction Insertion(A,e) Si A = . retourner (e,.,.) Sinon A = (x,FilsGauche,FilsDroit) Si e < x retourner (x,Insertion(FilsGauche,e),FilsDroit) Sinon retourner (x,FilsGauche,Insertion(FilsDroit,e))A bonyolultság megegyezik a kereséssel: átlagos esetben O (log n) és kritikus esetben O (n) .
Lehetőség van egy eljárás írására is egy elem hozzáadásához a bináris fa gyökeréhez. Ez a művelet ugyanolyan összetettséget igényel, de jobb az elemekhez való hozzáférés szempontjából.
Törlés
Kezdjük azzal, hogy megtaláljuk a törlendő csomópont kulcsát a fában. Több esetet is fontolóra kell venni, ha a törlendő csomópont a kulcsával megtalálható:
- Levél eltávolítása : Csak el kell távolítania a fáról, mivel nincsenek szálai.
- Csomópont eltávolítása gyermekkel : El kell távolítani a fáról úgy, hogy kicserélik a fiára.
- Kétgyermekes csomópont törlése : Tegyük fel, hogy a törlendő csomópontot N-nek hívják (az alábbi ábrán látható 7-es értékű csomópont). Cseréljük az N csomópontot a legközelebbi utódjával (a jobb részfa bal oldali csomópontja alul, a 9. érték csomópontja) vagy legközelebbi elődjével (az alfa jobb oldali csomópontja balra, alul, a 6. érték csomópontjával). Ez lehetővé teszi a bináris keresőfa szerkezet megőrzését a művelet végén. Ezután ismét alkalmazzuk a törlési eljárást N-re , amely most egy levél vagy egy csomópont, amelyben csak egy gyermek van.
A megvalósításnak ez a választása hozzájárulhat a fa egyensúlyhiányához . Valójában, mivel mindig a bal alfa leveleit töröljük, ennek a funkciónak a gyakori használata egy nehezebb fához vezet a jobb oldalon, mint a bal oldalon. Ezt úgy lehet orvosolni, hogy a jobb fia minimumának törlését egymás után felváltva a bal fia maximális törlésével váltogatjuk, ahelyett, hogy mindig az utóbbit választanánk. Például lehet véletlenszerű tényezőt használni: a programnak egy az egyben esélye lesz a megfelelő gyermek kiválasztására, és minden második esély a bal gyermek kiválasztására.
Ez a művelet minden esetben megköveteli a fa áthaladását a gyökérből a levélbe: a végrehajtási idő tehát arányos a fa mélységével, amely legrosszabb esetben megegyezik n -vel, ezért az O (n) bonyolultsági maximuma .
Alkalmazások
Rendezett tanfolyam
Egy bináris keresőfa kulcsait növekvő sorrendben tudjuk lekérni egy infix-vizsgálat végrehajtásával. Ebben a sorrendben össze kell összefűzni azt a rendezett listát, amelyet rekurzívan kaptunk a bal gyökér bejárásával, majd a jobb gyermeket bejárva rekurzívan. Lehetséges fordított sorrendben, a megfelelő részfával kezdve. A fa útja lineáris időben történik, mivel minden csomóponton csak egyszer kell áthaladnia.
fonction ParcoursInfixe(A): si A = . retourner [] sinon A = (x,FilsGauche,FilsDroit) retourner ParcoursInfixe(FilsGauche) + [x] + ParcoursInfixe(FilsDroit)Válogató
Ezért létrehozhatunk egy egyszerű, de nem hatékony rendezési algoritmust , ha az összes rendezni kívánt kulcsot beillesztjük egy új bináris keresési fába, majd a fentiek szerint rendezett módon böngészünk ebben a fában.
A = . pour e dans L faire A = Insertion(A,e) ListeTriee = ParcoursInfixe(A)A legrosszabb végrehajtási idő O-ban van (n²), ahol n a kulcsok száma a fában, amelyet akkor kapunk, amikor a kulcsokat már megrendelik: akkor van egy összekapcsolt listánk. Például, ha az 1, 2, 3, 4, 5 kulcsokat ebben a sorrendben adjuk meg, megkapjuk a fát (Void, 1, (Void, 2, (Void, 3, (Void, 4, (Void, 5, Üres))))) . Sokféleképpen lehet elkerülni ezt a problémát, a leggyakoribb a kiegyensúlyozott fa. Ezután elérhetjük O legrosszabb esetét (n * ln (n)).
Kiemelt sorok
A bináris keresési fák felhasználhatók a prioritási sor absztrakt típusának megvalósítására . valójában a kulcs behelyezésének és a vákuumtesztnek a műveleteit előnyös bonyolultsággal hajtják végre (rendre O-ban (log (n)) és O (1) -ben, ahol n a fában ábrázolt kulcsok száma). A legnagyobb kulcs törléséhez elegendő a fát a gyökérből tallózni az egyes csomópontok megfelelő gyermekének kiválasztásával, és törölni kell a terminál levelét. ehhez a fa magasságával megegyező számú műveletre van szükség, ezért logaritmikus bonyolultságra van szükség a kulcsok számában. A prioritási sor ezen ábrázolásának hírhedt előnye, hogy hasonló folyamat mellett a legkisebb kulcs eltávolítása is megtörténik a logaritmikus időben.
Kiegyensúlyozás
A beillesztést és a törlést O (h) ponton hajtják végre, ahol h a fa magassága. Ez különösen költségesnek bizonyul, ha a fa nagyon kiegyensúlyozatlan (például egy fésűfa, amelynek magassága a billentyűk számában lineáris), és ezért hatékonyabbá válunk a fák kiegyensúlyozásában használatuk során. Vannak technikák a kiegyensúlyozott fák megszerzésére , vagyis a logaritmikus magasság garantálására az elemek számában:
- Az AVL fa
- a fák vörös-fekete
- fák 2-3
- a 2-3-4 fa
- a B-fák
Hosszabbítások
A splash fa egy bináris kereső fa, amely automatikusan közelíti a gyakran használt elemeket a gyökérhez. Egy csalásban minden csomópontnak magasabb prioritása van, mint minden gyermekének.