Co je vyhledávací strom?
Prohledávací strom je datová struktura používaná v počítačovém programování k tomu, aby obsahovala a organizovala seznam dat. Každý vyhledávací strom se skládá z uspořádané sady uzlů, které lze připojit k nule nebo více jiným uzly. Jednotlivé uzly obsahují některá data i odkazy na jiné uzly. Data, která jsou obsažena v uzlech stromu, jsou často nějakým způsobem uspořádána, aby umožnila efektivní vyhledávání algoritmů, vložit a odstranit uzly s lehkostí.
Uzly vyhledávacího stromu jsou popsány se čtyřmi důležitými pojmy: Horní část stromu, kde je umístěn první uzel, se nazývá kořen. Pokud uzel obsahuje odkazy na dílčí uzel - uzly, tento uzel je známý jako nadřazený. Uzly, které jsou pod rodičem, se nazývají podřízené a jakýkoli uzel, který nemá podřízené uzly, se nazývá list. je identifikován kořenový uzel, protože nemá rodiče a listové uzly nebudou mít žádné děti.
Program je schopen procházet stromem, který vyhledává data, počínaje konkrétním uzlem, provádějící podmíněnou kontrolu a poté se přesouvá k dalšímu logickému uzlu, pokud požadovaná data nejsou k dispozici. , může toto hledání trvat různě dlouho. Pokud je strom hledání uspořádán během procesu přidávání a odebírání uzlů, může být vyhledávání velmi rychlé. Když je strom sestaven náhodně, není zatříděno nebo umožňuje více rodičům, vyhledávání může trvat velmi dlouho.
Jedním z faktorů, který ovlivňuje použití vyhledávacích stromů, je otázka rovnováhy. Vyvážený strom je takový, ve kterém pravý i levý podřízený kořenový uzel obsahují buď stejnou hloubku podřízených uzlů, nebo jsou v počtu jednoho uzlu. Hloubka stromu je počet uzlů od nejnižšího listu stromu ke kořenu. Nevyvážený strom může mít všechny uzly pouze na jedné straně nebo může mít všechny uzly uspořádané lineárním způsobem bez větví. Když se hloubka stromu zvýší, rychlost algoritmů vyhledávání se může dramaticky snížit.
Existují určité typy prohledávacích stromů, které jsou popsány jako samovyvažování. Tyto stromy používají operace, jako je střídání stromů, aby udržely rovnováhu při zachování pořadí dat v listech. rotace stromů může zpomalit program při přidávání a odebírání uzlů, což je dáno rychlostí, jakou lze data načíst.
Ačkoli existuje mnoho typů vyhledávacích stromů, nejběžnější stromovou datovou strukturou je binární vyhledávací strom. Tento datový typ se skládá z uzlů, z nichž každý má nula až dva podřízené uzly. Existuje pouze jeden kořenový uzel, a všechny listy ve stromu jsou řazeny zleva doprava ve vzestupných hodnotách podle dat, která drží. Mnoho algoritmů existuje pro binární vyhledávací stromy, které mohou velmi usnadňují objednávání dat.
Neexistuje žádná jediná standardní implementace pro uzly vyhledávacího stromu. Uzly mohou být reprezentovány širokou řadou datových struktur. Lze použít pole polí, jak by se mohlo množit propojené seznamy. Prohledávací strom používá vlastní datovou strukturu, která je navržena tak, aby usnadnila dokončení nezbytných operací vyžadovaných programem. Některé standardní programovací knihovny dokonce obsahují své vlastní interní implementace vyhledávacích stromů.