Co je binární vyhledávací strom?

Binární vyhledávací strom je jednou z různých datových struktur, které nám pomáhají organizovat a třídit data. Je to efektivní způsob ukládání dat v hierarchii a je velmi flexibilní.

V tomto článku se blíže podíváme na to, jak funguje – spolu s jeho vlastnostmi a aplikacemi.

Co je binární vyhledávací strom?

Binární vyhledávací strom je datová struktura složená z uzlů – podobně jako propojené seznamy. Mohou existovat dva typy uzlů: nadřazený a podřízený. Kořenový uzel je počátečním bodem struktury, která se rozvětvuje do dvou dceřiných uzlů, nazývaných levý uzel a pravý uzel.

Na každý uzel může odkazovat pouze jeho rodič a my můžeme procházet uzly stromu v závislosti na směru. Binární vyhledávací strom má tři hlavní vlastnosti:

1. Levý uzel je menší než jeho rodič.
2. Pravý uzel je větší než jeho rodič.
3. Levý a pravý podstrom musí být binární vyhledávací stromy.

Perfektního binárního vyhledávacího stromu je dosaženo, když jsou vyplněny všechny úrovně a každý uzel má levý a pravý podřízený uzel.

Příbuzný: Knihovny datových věd pro Python by měl používat každý datový vědec

Základní operace binárního vyhledávacího stromu

Nyní máte lepší představu o tom, co je binární vyhledávací strom, níže se můžeme podívat na jeho základní operace.

1. Vyhledávací operace

Vyhledávání nám umožňuje najít konkrétní hodnotu přítomnou ve stromu. Můžeme použít dva typy vyhledávání: prohledávání do šířky (BFS) a prohledávání do hloubky (DFS). Vyhledávání do šířky je vyhledávací algoritmus, který začíná v kořenovém uzlu a prochází horizontálně, ze strany na stranu, dokud není nalezen cíl. Každý uzel je během tohoto vyhledávání navštíven jednou.

Hloubkové vyhledávání naproti tomu prochází stromem vertikálně – začíná od kořenového uzlu a pokračuje v jedné větvi. Pokud je cíl nalezen, operace končí. Ale pokud ne, prohledá ostatní uzly.

2. Operace vložení

Operace vložení využívá operaci vyhledávání k určení místa, kam by měl být vložen nový uzel. Proces začíná od kořenového uzlu a začíná hledání, dokud není dosaženo cíle. Při vkládání je třeba zvážit tři případy.

• Případ 1: Když neexistuje žádný uzel. Uzel, který se má vložit, se stane kořenovým uzlem.

• Případ 2: Nejsou žádné děti. V tomto případě bude uzel porovnán s kořenovým uzlem. Je-li větší, stane se tím správným dítětem; jinak se stane levým dítětem.

• Případ 3: Když je přítomen kořen a jeho potomci. Nový uzel bude porovnán s každým uzlem na jeho cestě, aby se určilo, který uzel navštíví jako další. Pokud je uzel větší než kořenový uzel, bude procházet dolů pravým podstromem nebo doleva. Podobně se na každé úrovni provádějí srovnání, aby se určilo, zda půjde doprava nebo doleva, dokud nedorazí na místo určení.

3. Smazat operaci

Operace odstranění se používá k odstranění konkrétního uzlu ve stromu. Odstranění je považováno za složité, protože po odstranění uzlu musí být strom podle toho znovu uspořádán. Je třeba zvážit tři hlavní případy:

• Případ 1: Odstranění listového uzlu. Listový uzel je uzel bez jakýchkoli potomků. Toto je nejjednodušší odstranit, protože to neovlivňuje žádný jiný uzel; jednoduše procházíme stromem, dokud k němu nedosáhneme a odstraníme jej.

• Případ 2: Odstranění uzlu s jedním potomkem. Odstranění rodiče s jedním uzlem povede k tomu, že dítě zaujme jeho pozici a všechny následující uzly se posunou o úroveň výše. Ve struktuře podstromů nedojde k žádné změně.

• Případ 3: Odstranění uzlu se dvěma dětmi. Když musíme odstranit uzel se dvěma dětmi, musíme nejprve najít následující uzel, který může zaujmout jeho pozici. Dva uzly mohou nahradit odstraněný uzel, následník nebo předchůdce v pořadí. Následník v pořadí je nejlevější potomek pravého podstromu a předchůdce v pořadí je nejpravější potomek levého podstromu. Zkopírujeme obsah následníka/předchůdce do uzlu a vymažeme pořadí následníka/předchůdce.

Příbuzný: Jak vytvářet datové struktury pomocí tříd JavaScript ES6

Jak procházet binární vyhledávací strom

Procházení je proces, kterým procházíme binární vyhledávací strom. Provádí se k vyhledání konkrétní položky nebo k vytištění obrysu stromu. Vždy začínáme od kořenového uzlu a musíme sledovat hrany, abychom se dostali k dalším uzlům. Každý uzel by měl být považován za podstrom a proces se opakuje, dokud nejsou navštíveny všechny uzly.

• Přecházení v pořadí: Procházení v pořadí vytvoří mapu ve vzestupném pořadí. U této metody začínáme od levého podstromu a pokračujeme ke kořenovému a pravému podstromu.

• Přechod předobjednávky: Při této metodě je nejprve navštíven kořenový uzel, poté následuje levý podstrom a pravý podstrom.

• Přechod po objednávce: Toto procházení zahrnuje návštěvu kořenového uzlu jako poslední. Začneme od levého podstromu, pak od pravého podstromu a pak od kořenového uzlu.

Aplikace v reálném světě

Jak tedy využíváme binární algoritmy vyhledávacího stromu? Jak lze usuzovat, jsou extrémně efektivní při vyhledávání a třídění. Největší předností binárních stromů je jejich organizovaná struktura. Umožňuje vyhledávání provádět pozoruhodnou rychlostí snížením množství dat, která potřebujeme analyzovat, na polovinu na jeden průchod.

Binární vyhledávací stromy nám umožňují efektivně udržovat dynamicky se měnící datovou sadu v organizované formě. Pro aplikace, které často vkládají a odebírají data, jsou velmi užitečné. Motory videoher používají algoritmus založený na stromech známých jako binární prostorový oddíl, který pomáhá s řádným vykreslováním objektů. Microsoft Excel a většina tabulkového procesoru používá jako základní datovou strukturu binární stromy.

Možná vás překvapí, že Morseova abeceda používá ke kódování dat binární vyhledávací strom. Dalším významným důvodem, proč jsou stromy binárního vyhledávání tak užitečné, je jejich více variant. Jejich flexibilita vedla k vytvoření mnoha variant pro řešení nejrůznějších problémů. Při správném použití jsou binární vyhledávací stromy velkým přínosem.

Binární vyhledávací stromy: Perfektní výchozí bod

Jedním z hlavních způsobů, jak změřit odbornost inženýrů, je jejich znalost a aplikace datových struktur. Datové struktury jsou užitečné a mohou pomoci vytvořit efektivnější systém. Binární vyhledávací stromy jsou skvělým úvodem do datových struktur pro každého začínajícího vývojáře.

15 metod JavaScript Array, které byste dnes měli zvládnout

Chcete porozumět polím JavaScript, ale nemůžete se s nimi vypořádat? Pokyny naleznete v našich příkladech pole JavaScript.

Přečtěte si další

O autorovi