binární vyhledávací stromy podporují tři hlavní operace: vkládání prvků, mazání prvků a vyhledávání (kontrola, zda je klíč přítomen).

SearchingEdit

Vyhledávání v binárním vyhledávacím stromu pro konkrétní klíč lze naprogramovat rekurzivně nebo opakované.

začneme zkoumáním kořenového uzlu. Pokud je strom nulový, klíč, který hledáme, ve stromu neexistuje. V opačném případě, pokud se klíč rovná kořenu, je vyhledávání úspěšné a uzel vrátíme. Pokud je klíč menší než klíč kořene, prohledáme levý podstrom., Podobně, pokud je klíč větší než klíč kořene, hledáme správný podstrom. Tento proces se opakuje, dokud není nalezen klíč nebo zbývající podstrom je null. Pokud hledaný klíč není nalezen po dosažení nulového podstromu, klíč není ve stromu přítomen. To je jednoduše vyjádřen jako rekurzivní algoritmus (implementována v Pythonu):

stejný algoritmus může být realizován iterativně:

Tyto dva příklady nepodporují duplicity, to znamená, oni se spoléhají na, aby vztah byl celkem pořádek.

lze poznamenat, že rekurzivní algoritmus je rekurzivní., V jazyce podporujícím optimalizaci tail call se rekurzivní a iterativní příklady kompilují do ekvivalentních programů.

protože v nejhorším případě musí tento algoritmus hledat od kořene stromu k listu nejdále od kořene, operace vyhledávání vyžaduje čas úměrný výšce stromu (viz terminologie stromu). V průměru mají binární vyhledávací stromy s klíči uzlů výšku o (log |Nodes|). V nejhorším případě však mohou mít binární vyhledávací stromy výšku o (|uzly/), když nevyvážený strom připomíná propojený seznam (degenerovaný strom).,

Vyhledávání s duplikáty allowedEdit

Pokud je cílem vztahu je pouze celkem předobjednávku, přiměřené rozšíření funkčnosti je následující: také v případě rovnosti vyhledávání dolů na listy. Tím umožňuje určit (nebo hard-wire) směr, kam vložit duplikát, a to buď vpravo nebo vlevo od všech duplikátů ve stromu tak daleko. Pokud je směr pevný, obě možnosti, vpravo a vlevo, podporují zásobník s vložkou duplikát jako push operace a odstranit jako pop operace.,: 155

Binary tree sort vybavené takovou vyhledávací funkcí se stává stabilní.

InsertionEdit

Vložení začíná jako hledání začne; pokud klíč není stejné jako kořen, musíme hledat vlevo nebo vpravo podstromy jako předtím. Nakonec jsme se dosáhnout vnější uzel a přidat nový pár klíč-hodnota (zde kódovány jako záznam ‚newNode), pokud jeho pravé nebo levé dítě, v závislosti na uzlu, je klíčové., Jinými slovy, zkoumáme kořen a rekurzivně vkládáme nový uzel do levého podstromu, pokud je jeho klíč menší než klíč kořene nebo pravý podstrom, pokud je jeho klíč větší nebo rovný kořenu.

zde je návod, jak lze typické vložení binárního vyhledávacího stromu provést v binárním stromu v c++:

Alternativně může být takto implementována nerekurzivní verze., Pomocí ukazatele-ukazatel sledovat, odkud jsme přišli, umožňuje kód vyhnout explicitní kontrola a manipulace případu, kde je třeba vložit uzel v strom root:

výše uvedené destruktivní procesní varianta upravuje strom na místě. Používá pouze konstantní haldy prostor (a iterativní verze používá konstantní stack prostor, jakož), ale předchozí verze stromu je ztracena., Případně, jako v následujícím příklad v Pythonu, můžeme rekonstruovat všechny předky vložen uzel; jakýkoli odkaz na původní strom, kořen zůstává v platnosti, takže strom perzistentní datové struktury:

část, která je přestavěna používá O(log n) prostoru v průměrném případě a O(n) v nejhorším případě.

V obou verze, tato operace vyžaduje čas úměrný výšce stromu, v nejhorším případě, což je O(log n) času v případě průměru přes všechny stromy, ale O(n) času v nejhorším případě.,

dalším způsobem, jak vysvětlit vložení, je to, že pro vložení nového uzlu do stromu je jeho klíč nejprve porovnán s klíčem kořene. Pokud je jeho klíč menší než kořen, je porovnán s klíčem levého dítěte kořene. Pokud je jeho klíč větší, porovnává se s pravým dítětem kořene. Tento proces pokračuje, dokud není nový uzel porovnán s listovým uzlem, a pak se přidá jako pravé nebo levé dítě tohoto uzlu, v závislosti na jeho klíči: pokud je klíč menší než klíč listu, je vložen jako levé dítě listu, jinak jako pravé dítě listu.,

existují i jiné způsoby vkládání uzlů do binárního stromu, ale je to jediný způsob, jak vložit uzly na listy a současně zachovat strukturu BST.

DeletionEdit

při odstraňování uzlu z binárního vyhledávacího stromu je nutné udržovat sekvenci uzlů v pořadí. Existuje mnoho možností, jak to udělat. Následující metoda, kterou navrhl T. Hibbard v roce 1962, však zaručuje, že výšky dílčích stupňů předmětu se změní nanejvýš o jednu., Existují tři možné případy, které je třeba zvážit:

• odstranění uzlu bez dětí: jednoduše odstraňte uzel ze stromu.
• odstranění uzlu s jedním dítětem: odstraňte uzel a nahraďte jej jeho dítětem.
• odstranění uzlu D se dvěma dětmi: vyberte buď předchůdce v pořadí D nebo nástupce v pořadí E (viz obrázek). Místo mazání D, přepsat jeho klíč a hodnota s E to. Pokud E nemá dítě, odstranit E od své předchozí rodič G. Jestli E má dítě F, to je v pořádku dítě, tak, že je nahradí E na E rodič.,

Ve všech případech, kdy D se stane být root, aby nahrazení uzlu root znovu.

uzly se dvěma dětmi je těžší odstranit., In-order nástupce uzlu je jeho pravý subtree je vlevo-most dítě, a uzel je v pořadí předchůdce je levý subtree je pravá většina dítě. V obou případech bude mít tento uzel pouze jedno nebo žádné dítě. Odstraňte jej podle jednoho ze dvou jednodušších případů výše.

Důsledně pomocí in-order nástupce, nebo v řádu předchůdce pro každou instanci dva-dítě případ, může vést k nevyvážené strom, takže některé implementace vyberte jeden nebo druhý v různých časech.,

Runtime analýza: i když tato operace nemusí vždy procházet stromu k listu, je vždy možné; proto, v nejhorším případě, to vyžaduje čas úměrný výšce stromu. Nevyžaduje více, i když má uzel dvě děti, protože stále sleduje jednu cestu a dvakrát nenavštěvuje žádný uzel.,

TraversalEdit

Jednou binární vyhledávací strom byl vytvořen, jeho prvky mohou být vyvolány v pořadí podle rekurzivně pojezdu levého podstromu do kořenového uzlu, přístup k uzlu samotného, pak rekurzivně pojezdu pravý podstrom uzlu, pokračuje tento vzor se každý uzel ve stromu, jako je rekurzivně přístupné. Stejně jako u všech binárních stromů, jeden může provádět pre-order traversal nebo post-order traversal, ale ani jsou pravděpodobně užitečné pro binární vyhledávací stromy., In-order traversal binárního vyhledávacího stromu bude mít vždy za následek seřazený seznam položek uzlu (čísla, řetězce nebo jiné srovnatelné položky).

kód pro in-order traversal v Pythonu je uveden níže. To bude volat zpětné volání (některé funkce programátor chce volat na hodnotu uzlu, jako je tisk na obrazovku) pro každý uzel ve stromu.

Traversal vyžaduje O (n) čas, protože musí navštívit každý uzel. Tento algoritmus je také O (n), takže je asymptoticky optimální.

Traversal lze také implementovat iterativně. Pro některé aplikace, např., větší rovné vyhledávání, aproximativní vyhledávání, operace pro jeden krok (iterativní) traversal může být velmi užitečné. To je samozřejmě implementováno bez konstrukce zpětného volání a v nejhorším případě bere O(1) v průměru a o(log n).

VerificationEdit

Někdy už máme binární strom, a musíme určit, zda se jedná o BST. Tento problém má jednoduché rekurzivní řešení.,

BST vlastnost—každý uzel v pravém podstromu musí být větší než aktuální uzel a každý uzel levého podstromu musí být menší než aktuální uzel—je klíčem k zjišťuje, zda strom je BST, nebo ne. Greedy algoritmus—jednoduše procházet strom, každý uzel zkontrolujte, zda uzel obsahuje hodnotu větší než hodnota na levé dítě a menší než hodnota na pravé dítě—není práce pro všechny případy., Zvažte následující strom:

 20 / \ 10 30 / \ 5 40

Ve stromu výše, každý uzel splňuje podmínku, že uzel obsahuje hodnotu větší než jeho levý dítě a menší než jeho správně dítě držet, a přesto to není BST: hodnota 5 je na pravý podstrom uzlu obsahuje 20, porušení BST majetku.

místo toho, abychom se rozhodli pouze na základě hodnot uzlu a jeho dětí, potřebujeme také informace proudící od rodiče., V případě stromu výše, pokud bychom pamatovat na uzel obsahující hodnotu 20, viděli bychom, že uzel s hodnotou 5 je porušení BST smlouvu.,

stav musíme zkontrolovat v každém uzlu je:

• pokud uzel je nechal dítě jeho rodič, pak to musí být menší než (nebo rovno) mateřská a musí předat hodnotu z jeho rodič, aby jeho pravého podstromu, aby ujistěte se, že žádný z uzlů v podstromu je větší, než rodiče
• pokud uzel je pravé dítě svých rodičů, pak to musí být větší, než je rodič a musí předat hodnotu z jeho rodič, aby jeho levý podstrom, aby ujistěte se, že žádný z uzlů v podstromu je menší než rodič.,

rekurzivní řešení v C++ lze vysvětlit tento další:

node->key+1 node->key-1 jsou na tom, aby se pouze odlišné prvky v BST.

Pokud chceme, aby byly přítomny stejné prvky, můžeme na obou místech použít pouze node->key.

počáteční volání této funkce může být něco jako toto:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

v Podstatě jsme udržet vytváření platný rozsah (od ) a aby zmenšuje to pro každý uzel, jak jsme jít dolů rekurzivně.,

jak je uvedeno v sekci #Traversal, v pořadí traversal binárního vyhledávacího stromu vrátí uzly seřazené. Tak my jen potřebujeme, aby poslední navštívené uzlu při křížení strom a zkontrolujte, zda je jeho klíč je menší (nebo menší/stejné, pokud duplikáty jsou povoleny ve stromu) ve srovnání s aktuální klíč.

Paralelní algorithmsEdit

k Dispozici jsou také paralelní algoritmy pro binární vyhledávací stromy, včetně vkládání/mazání více prvky, konstrukce z pole, filtr s určitými predicator, vyrovnat do řady, slučování/odečtením/protínající dva stromy, atd., Tyto algoritmy lze implementovat pomocí algoritmů join-based tree, které mohou také udržet strom vyvážený pomocí několika vyvažovacích schémat (včetně AVL tree, red-black tree, weight-balanced tree a treap) .