Binární vyhledávací strom: Porovnání verzí

Skočit na navigaci Skočit na vyhledávání
Přidáno 1 630 bajtů ,  před 14 lety
bez shrnutí editace
Bez shrnutí editace
Bez shrnutí editace
== Operace ==
Všechny operace na binárním stromě využívají několik volání komparátoru, který je podprogramem pro zjištění pořadí dvou hodnot.
V obecných implementacích BST program při tvorbě stromu běžně poskytuje zpětné volání komparátoru, buď explicitně nebo v jazycích, které podporují [[Objektově orientované programování|polymorfismus]] hodnotou, kterou lze porovnávat.
 
 
== Vyhledávání ve stromu ==
Prohledávání binárního stromu na specifickou hodnotu je proces, který lze provádět rekursivně díky struktuře, ve které jsou hodnoty uloženy. Jako výchozí uzel zvolme například [[Strom (datová struktura)#Základní prvky stromu|kořen stromu]]. Pokud hodnota, kterou hledáme je s tímto uzlem ekvivalentní, hodnota byla nalezena. Pokud je menší, pokračujeme rekursivně v procházení levého podstromu. Pokud je v větší, procházíme rekursivně pravý podstrom. Pokud je hodnota [[Strom (datová struktura)#Základní prvky stromu|listem]], nebo již neobsahuje podstrom vzhledem k hledané hodnotě, pak uzel není tam, kde by měl být, takže není ani nikde jinde v BST. Porovnání může být vytvořeno z [[binární vyhledávání|binárního vyhledávání]], které pracuje obdobně, ale přistupuje k poli namísto následujících uzlů.
 
Zde je vyhledávací algoritmus v programovacím jazyce [[Python]]:
<code lang="python">
def search_binary_tree(node, key):
if node is None:
return None # klíč nebyl nalezen
if key < node.key:
return search_binary_tree(node.left, key)
elif key > node.key:
return search_binary_tree(node.right, key)
else: # klíč je ekvivalentní s klíčem uzlu
return node.value # klíč nalezen
</code>
Tato operace má logaritmickou časovou složitost [[Asymptotická složitost|O]](log ''n''), ale pokud je strom nevyvážený a podobá se seznamu, může mít i lineární časovou složitost [[Asymptotická složitost|O]](''n'').
 
== Vyhledávání ve stromuQ ==
Hodnoty v uzlech jsou uspořádány tak, že pro každý uzel stromu ''u'' platí:
* hodnota uložená v ''u'' je větší nebo rovna než hodnota uložená v levém podstromu ''u''
16

editací

Navigační menu