Samovyvažující binární vyhledávací strom - Self-balancing binary search tree

Příklad nevyváženého stromu; sledování cesty od kořene k uzlu trvá v průměru 3,27 přístupu k uzlu

Stejný strom poté, co byl výškově vyvážený; průměrná cesta se snížila na 3,00 uzlových přístupů

V informatice je samovyvažujícím binárním vyhledávacím stromem jakýkoli binární vyhledávací strom na bázi uzlů , který automaticky udržuje svou výšku (maximální počet úrovní pod kořenem) malou tváří v tvář vkládání a odstraňování libovolných položek. Tyto operace, jsou-li navrženy pro binární vyhledávací strom s vlastním vyvažováním, obsahují preventivní opatření proti neomezenému zvyšování výšky stromu, aby tyto abstraktní datové struktury získaly atribut „self-balancing“.

U výškově vyvážených binárních stromů je výška definována jako logaritmická v počtu položek. To je případ mnoha binárních vyhledávacích stromů, například stromů AVL a červeno-černých stromů -ten se nazýval symetrický binární B-strom a byl přejmenován; kvůli iniciálám jej však lze stále zaměňovat s obecným konceptem samovyrovnávacího binárního vyhledávacího stromu. ${\ displaystyle {\ mathcal {O}} (\ log n)}$ ${\ displaystyle n}$

Ale splay strom a Treaps jsou považovány samovyvažující stejně, i když jejich výška není zaručeno, že bude logaritmická v počtu kusů.

Samovyvažující binární vyhledávací stromy poskytují efektivní implementace pro měnitelné seřazené seznamy a lze je použít pro jiné abstraktní datové struktury, jako jsou asociativní pole , prioritní fronty a sady .

Přehled

Rotace stromů jsou velmi běžnými interními operacemi na samovyvažujících binárních stromech, aby byla udržena dokonalá nebo téměř dokonalá rovnováha.

Většina operací s binárním vyhledávacím stromem (BST) vyžaduje čas přímo úměrný výšce stromu, proto je žádoucí ponechat výšku malou. Binární strom s výškou h může obsahovat nejvýše 2 ⁰ +2 ¹ +··· +2 ^h = 2 ^{h +1} −1 uzly. Z toho vyplývá, že pro jakýkoli strom s n uzly a výškou h :

{\ Displaystyle n \ leq 2^{h+1} -1}

A to znamená:

{\ Displaystyle h \ geq \ lceil \ log _ {2} (n+1) -1 \ rceil \ geq \ lfloor \ log _ {2} n \ rfloor}

.

Jinými slovy, minimální výška binárního stromu s n uzly je log ₂ ( n ), zaokrouhleno dolů ; to je , . ${\ Displaystyle \ lfloor \ log _ {2} n \ rfloor}$

Nejjednodušší algoritmy pro vkládání položek BST však mohou v poměrně běžných situacích poskytnout strom s výškou n . Když jsou například položky vloženy v seřazeném pořadí klíčů , strom se degeneruje do propojeného seznamu s n uzly. Rozdíl ve výkonu mezi těmito dvěma situacemi může být obrovský: například když n = 1 000 000, minimální výška je . ${\ Displaystyle \ lfloor \ log _ {2} (1 000 000) \ rfloor = 19}$

Pokud jsou datové položky známy předem, lze výšku udržet v průměrném smyslu malou přidáním hodnot v náhodném pořadí, což má za následek náhodný binární vyhledávací strom . Existuje však mnoho situací (například online algoritmy ), kdy tato randomizace není životaschopná.

Samovyvažující binární stromy tento problém řeší prováděním transformací na stromě (například otáčení stromů ) v časech vložení klíčů, aby byla výška úměrná log ₂ ( n ). Přestože jde o určitou režii , není větší než vždy nutné náklady na vyhledávání a lze ji odůvodnit zajištěním rychlého provedení všech operací.

I když je možné udržovat BST s minimální výškou s očekávanými časovými operacemi (vyhledávání/vkládání/odebírání), dodatečné požadavky na prostor potřebné k udržení takové struktury mají tendenci převážit nad zkrácením doby hledání. Pro srovnání, strom AVL je zaručeně v faktoru 1,44 optimální výšky a přitom vyžaduje pouze dva další bity úložiště v naivní implementaci. Většina algoritmů BST s vlastním vyvážením proto udržuje výšku v rámci konstantního faktoru této dolní hranice. ${\ displaystyle O (\ log n)}$

V asymptotickém (" Big-O ") smyslu, samovyvažující BST struktura obsahující n položek umožňuje vyhledávání, vložení a vyjmutí položky v době nejhoršího případu O (log n ) a seřazený výčet všech položek v O ( n ) čas. U některých implementací se jedná o časové limity pro jednotlivé operace, zatímco u jiných jde o amortizované meze přes posloupnost operací. Tyto časy jsou asymptoticky optimální mezi všemi datovými strukturami, které manipulují s klíčem pouze prostřednictvím srovnání.

Implementace

Datové struktury implementující tento typ stromu zahrnují:

Aplikace

Samovyvažující binární vyhledávací stromy lze použít přirozeným způsobem ke konstrukci a údržbě seřazených seznamů, jako jsou například prioritní fronty . Lze je také použít pro asociativní pole ; páry klíč – hodnota se jednoduše vloží s uspořádáním založeným pouze na klíči. V této funkci mají BST s vlastním vyvažováním řadu výhod a nevýhod oproti svým hlavním konkurenčním, hashovacím tabulkám . Jednou z výhod BST s vlastním vyvažováním je, že umožňují rychlé (skutečně asymptoticky optimální) výčty položek v pořadí klíčů , což hashovací tabulky neposkytují. Jednou nevýhodou je, že se jejich vyhledávací algoritmy komplikují, když může být více položek se stejným klíčem. Samovyvažující BST mají lepší výkon vyhledávání v nejhorších případech než hashovací tabulky (O (log n) ve srovnání s O (n)), ale mají horší výkon v průměrném případě (O (log n) ve srovnání s O (1)).

Samovyvažující BST lze použít k implementaci jakéhokoli algoritmu, který vyžaduje měnitelné seřazené seznamy, aby bylo dosaženo optimálního asymptotického výkonu v nejhorším případě. Pokud je například binární třídění stromů implementováno pomocí samovyvažujícího BST, máme velmi snadno popsatelný, ale asymptoticky optimální algoritmus řazení O ( n log n ). Podobně mnoho algoritmů ve výpočetní geometrii efektivně využívá variace BST s vlastním vyvažováním k řešení problémů, jako je problém průsečíku úsečky a problému s umístěním bodu . (Pro průměrného-case výkon však samovyvažující BSTs může být méně účinná než jiná řešení. Binární strom třídění, zvláště, je pravděpodobné, že bude pomalejší než merge sort , quicksort nebo Heapsort , protože ze stromu vyrovnávání nad hlavou as stejně jako vzory přístupu do mezipaměti .)

Samovyvažující BST jsou flexibilní datové struktury, protože je snadné je rozšířit tak, aby efektivně zaznamenávaly další informace nebo prováděly nové operace. Například lze zaznamenat počet uzlů v každém podstromu, který má určitou vlastnost, což umožňuje počítat počet uzlů v určitém rozsahu klíčů s touto vlastností v čase O (log n ). Tato rozšíření lze použít například k optimalizaci databázových dotazů nebo jiných algoritmů pro zpracování seznamu.

Viz také

Reference

externí odkazy

Slovník algoritmů a datových struktur: Výškově vyvážený binární vyhledávací strom
GNU libavl , knihovna licencí LGPL implementací binárních stromů v C, s dokumentací

Languages

In other projects