Hledat strom - Search tree

v počítačová věda, a vyhledávací strom je stromová datová struktura slouží k vyhledání konkrétních klíčů v rámci sady. Aby a strom aby fungoval jako vyhledávací strom, klíč pro každý uzel musí být větší než kterýkoli klíč v podstromech vlevo a menší než kterýkoli klíč v podstromech vpravo.^[1]

Výhodou vyhledávacích stromů je jejich efektivní doba hledání, protože strom je přiměřeně vyvážený, to znamená listy na obou koncích jsou srovnatelné hloubky. Existují různé datové struktury vyhledávacího stromu, z nichž některé také umožňují efektivní vkládání a mazání prvků, které pak operace musí udržovat rovnováhu stromu.

Vyhledávací stromy se často používají k implementaci asociativní pole. Algoritmus vyhledávacího stromu používá klíč z pár klíč – hodnota najít umístění a poté aplikace uloží celý pár klíč – hodnota na dané místo.

Druhy stromů

Binární vyhledávací strom

Binární vyhledávací strom

Binární vyhledávací strom je datová struktura založená na uzlech, kde každý uzel obsahuje klíč a dva podstromy, levý a pravý. Pro všechny uzly musí být klíč levého podstromu menší než klíč uzlu a klíč pravého podstromu musí být větší než klíč uzlu. Všechny tyto podstromy musí být kvalifikovány jako binární vyhledávací stromy.

Nejhorší případ časová složitost pro hledání binárního vyhledávacího stromu je výška stromu, který může být tak malý jako O (log n) pro strom s n prvky.

B-strom

B-stromy jsou zobecnění binárních vyhledávacích stromů v tom, že mohou mít v každém uzlu proměnný počet podstromů. Zatímco podřízené uzly mají předdefinovaný rozsah, nemusí být nutně vyplněny daty, což znamená, že B-stromy mohou potenciálně plýtvat určitým prostorem. Výhodou je, že B-stromy nemusí být znovu vyváženy tak často jako jiné samovyvažující stromy.

Vzhledem k variabilnímu rozsahu délky jejich uzlů jsou B-stromy optimalizovány pro systémy, které čtou velké bloky dat, jsou také běžně používány v databázích.

Časová složitost hledání B-stromu je O (log n).

(a, b) -strom

Strom (a, b) je vyhledávací strom, kde všechny jeho listy mají stejnou hloubku. Každý uzel má alespoň A děti a nanejvýš b děti, zatímco kořen má nejméně 2 děti a nanejvýš b děti.

A a b lze rozhodnout podle následujícího vzorce:^[2]

${ displaystyle 2 leq a leq { frac {(b + 1)} {2}}}$

Časová složitost hledání stromu (a, b) je O (log n).

Ternární vyhledávací strom

Ternární vyhledávací strom je typ strom které mohou mít 3 uzly: dítě, stejné dítě a dítě. Každý uzel ukládá jeden znak a samotný strom je uspořádán stejným způsobem jako binární vyhledávací strom, s výjimkou možného třetího uzlu.

Prohledávání ternárního vyhledávacího stromu zahrnuje předání a tětiva otestovat, zda ji nějaká cesta obsahuje.

Časová složitost prohledávání vyváženého ternárního vyhledávacího stromu je O (log n).

Vyhledávací algoritmy

Hledání konkrétního klíče

Za předpokladu, že je strom seřazený, můžeme vzít klíč a pokusit se ho najít ve stromu. Následující algoritmy jsou zobecněny pro binární vyhledávací stromy, ale stejný nápad lze aplikovat na stromy jiných formátů.

Rekurzivní

rekurzivní vyhledávání (klíč, uzel) -li uzel je NULA        vrátit se EMPTY_TREE    -li key jinak pokud klíč> node.key návrat vyhledávání rekurzivní (klíč, node.right) jiný        vrátit se uzel

Iterativní

searchIterative (klíč, uzel) currentNode: = uzel zatímco currentNode není NULA        -li currentNode.key = klíč vrátit se currentNode jinak pokud currentNode.key> klíč currentNode: = currentNode.left jiný            currentNode: = currentNode.right

Hledání min a max

V seřazeném stromu je minimum umístěno v nejvzdálenějším uzlu vlevo, zatímco maximum je umístěno v nejvzdálenějším uzlu vpravo.^[3]

Minimální

findMinimum (uzel) -li uzel je NULA        vrátit se EMPTY_TREE    min: = uzel zatímco min. vlevo není NULA        min: = min. vlevo vrátit se min. klíč

Maximum

findMaximum (uzel) -li uzel je NULA        vrátit se EMPTY_TREE    max: = uzel zatímco max. právo není NULA        max: = max. vpravo vrátit se max. klíč

Viz také

• Trie
• Binární strom
• Hledání do hloubky

Reference