Obsah:
- Definícia - Čo znamená samovyvažujúci strom binárneho vyhľadávania?
- Techopedia vysvetľuje samovyvažujúci strom binárneho vyhľadávania
Definícia - Čo znamená samovyvažujúci strom binárneho vyhľadávania?
Samovyrovnávací strom binárneho vyhľadávania je typ štruktúry údajov, ktorý sa sám nastavuje, aby poskytoval konzistentné úrovne prístupu k uzlom. V samovyrovnávacom binárnom vyhľadávacom strome sú spojenia z horného uzla k ďalším uzlom triedené a opätovne upravené tak, aby bol strom vyrovnaný, a riadky trajektórie vyhľadávania pre každý koncový uzol sú z hľadiska dĺžky rovnaké.
Samovyrovnávací binárny vyhľadávací strom sa tiež nazýva vyvážený strom alebo výškovo vyvážený binárny vyhľadávací strom.
Techopedia vysvetľuje samovyvažujúci strom binárneho vyhľadávania
Binárny vyhľadávací strom všeobecne poskytuje dátovú štruktúru s jedným uzlom na vrchu a jedným alebo dvoma uzlami k nemu pripojenými na každej nasledujúcej úrovni. Stromy binárneho vyhľadávania podporujú tri operácie - operátori môžu vkladať komponenty, mazať komponenty alebo vyhľadávať určitý počet alebo iný obsah uzlov. Jednou z výhod binárnych vyhľadávacích stromov je, že systém sa dá usporiadať tak, aby ignoroval jednu polovicu stromu na každej úrovni, čo vedie k efektívnejšiemu pracovnému zaťaženiu pri vyhľadávaní.
Pozitívnym aspektom samovyrovnávacieho binárneho vyhľadávacieho stromu je to, že prístup k uzlom je rovnaký - napríklad namiesto toho, aby ste museli ísť päť krokov na jednej strane stromu alebo tri kroky na druhej strane stromu, pretože - s upravenou štruktúrou uzlov by vyhľadávanie smerovalo iba určitý počet krokov (n) do ktoréhokoľvek daného koncového uzla. Toto je dosiahnuté odstránením jednotlivých spojení uzlov a ich nahradením binárnymi, aby sa skrátili konkrétne končatiny stromu.
Nevýhodou samovyrovnávacieho binárneho vyhľadávania tri je to, že funguje iba vtedy, ak sú spojenia uzlov „agnostické na úrovni“ - inými slovami, ak je možné jednotlivý uzol prestaviť na predchádzajúcu úroveň, aby sa skrátila vetva stromu., Napríklad, ak je samovyrovnávací binárny vyhľadávací strom zložený s daným číslom na vrchu a dvoma po sebe nasledujúcimi číslami na oboch stranách a existuje reťazec troch ďalších čísel s pripojeniami s jedným uzlom, úprava stromu by vložila piaty uzol spolu s tretím uzlom namiesto štvrtého uzla, takže tretí uzol má dva spojovacie uzly namiesto jedného. Ak však dátová štruktúra musí identifikovať konkrétny obsah uzlov ako súvisiaci v konkrétnom vzťahu rodič / dieťa, úprava týchto uzlov tak, aby vyhovovala rovnomernosti stromovej štruktúry, nebude fungovať.
