Pojmem binární vyhledávací strom označujeme binární strom, jehož uzly obsahují vzájemně porovnatelné klíče a jenž je uspořádaný takovým způsobem, že klíče všech uzlů levého podstromu jsou menší nebo rovny klíči aktuálního uzlu a klíče všech uzlů pravého podstromu jsou větší než klíč aktuálního uzlu (viz Obr. 3.11). Pokud nepřipouštíme vícenásobný výskyt klíčů, pak na obou stranách bude mezi klíči platit ostrá nerovnost.

Obrázek 3.11. Binární vyhledávací strom

Vyhledávání v binárním vyhledávacím stromu je založeno na již představeném principu binárního vyhledávání. Zde se množina hodnot, v nichž vyhledáváme, rozděluje na dvě části dané levým a pravým podstromem aktuálního uzlu. Je-li vyhledávaná hodnota menší než je klíč aktuálního uzlu, pak pokračujeme levým podstromem, je-li větší, pokračujeme pravým podstromem.

Vzpomínáte si, co jsme si říkali o složitosti binárního vyhledávání? Tato složitost je logaritmická, ovšem za předpokladu, že množinu vyhledávaných hodnot rozdělíme vždy přesně na polovinu. Jenže u binárního vyhledávacího stromu tato podmínka platit nemusí, stačí si představit strom, jehož každý vnitřní uzel má levý podstrom tvořený pouze jediným listem (Obr. 3.12). Binární strom vlastně degraduje na obyčejný seznam a složitost vyhledávání vzroste na lineární.

Obrázek 3.12. Binární strom degenerovaný na seznam

V ideálním případě má každý vnitřní uzel vyhledávacího stromu právě dva následníky. Takovému stromu se pak říká absolutně vyvážený strom a u něj je logaritmická složitost zaručena. Jenže zajistit absolutní vyvážení při vkládání a rušení uzlů je časově dosti nákladné, a proto se používají některé suboptimální metody, které kladou poněkud méně přísné, zato lépe zajistitelné podmínky na strukturu stromu. Do této skupiny patří např. AVL nebo Red- Black stromy, s jejichž implementací se můžete podrobně seznámit v literatuře.

Jako ukázku si nyní uvedeme metodu pro vyhledávání uzlu s daným klíčem. Vzhledem k tomu, že potřebujeme nad klíči definovat uspořádání, musíme opět předpokládat, že klíče implementují rozhraní Comparable, případně musíme vyhledávacímu algoritmu dodat Comparator, jenž porovnání klíčů zajistí. S těmito rozhraními a jejich použitím jsme se už setkali v části 3.6 věnované množinám.

Příklad 3.17.

Realizujte metodu pro vyhledání uzlu binárního vyhledávacího stromu se zadanou hodnotou klíče. Pro vyhledání můžeme využít elegantní rekurzivní algoritmus, jenž spočívá v porovnání aktuálního klíče s hledaným a v případě neshody rekurzivní volání metody pro vyhledávání v levém nebo pravém podstromu. Musíme pouze dát pozor na to, abychom se včas zastavili, pokud je vybraný podstrom prázdný: public TreeNode recursiveLookup(Object key) { int compare = ((Comparable)_data).compareTo(key); if( compare == 0 ) return this; TreeNode node; if( compare > 0 ) { node = _left==null ? null : _left.recursiveLookup(key); } else { node = _right==null ? null : _right.recursiveLookup(key); } return node; }

Jinou možností je využití obyčejného cyklu, kterému budeme na základě porovnání aktuálního uzlu s hledaným pouze "přehazovat výhybku" na levý nebo pravý podstrom:

public TreeNode loopLookup(Object key) 
{ 
  TreeNode node = this; 
  while( node != null ) { 
    int compare = ((Comparable)node.getData()).compareTo(key); 
    if( compare == 0 ) return node; 
    if( compare > 0 ) 
      node = node.getLeft(); 
    else 
      node = node.getRight(); 
  } 
  return null; 
}