struct node
id : key — klíč
left : node — levý potomek (nil, pokud neexistuje)
right : node — pravý potomek (nil, pokud neexistuje)
parent : node — rodič (nil, pokud neexistuje)
Binární vyhledávací strom je datová struktura, která umožňuje rychlé vyhledávání, vkládání a mazání prvků. V binárním vyhledávacím stromu jsou prvky uloženy tak, že v každém uzlu je hodnota klíče větší než vlevo a menší než vpravo. Každý uzel má maximálně 2 potomky. Vyhledávání, vkládání a mazání probíhá tak, že se porovnává hledaný prvek s hodnotou v uzlu. Pokud je hledaný prvek větší, tak se vyhledává vpravo, pokud je menší, tak se vyhledává vlevo.
tree-search-rec(key, node):
if node == nil or key == node.id:
return node
if key < node.id:
return tree-search-rec(key, node.left)
else:
return tree-search-rec(key, node.right)
tree-search(key, node):
y = node
while y != nil and key != y.id:
if key < y.id:
y = y.left
else:
y = y.right
return y
in-order-walk(node)
if node != nil:
in-order-walk(node.left)
print node.id
in-order-walk(node.right)
tree-min(node):
y = node
while y.left != nil:
y = y.left
return y
Pro hledání maxima je operace analogická, jen místo y.left použijeme y.right.
Pořádkový následník vrcholu x je vrchol, který má v množine {z | z.id > x.id} nejmenší klíč. Pokud je tato množina prázdná, pořádkový následník neexistuje.
tree-successor(node):
if node.right != nil:
return tree-min(node.right)
y = node.parent
while y != nil and node != y.left:
node = y
y = y.parent
return y
Některé operace mohou změnit kořen stromu. Z tohoto důvodu dáváme jako návratovou hodnotu funkcí kořen stromu (analogicky se dá použít i zarážka).
Pro vkládání vrcholu do stromu musíme najít vhodné místo pro nový vrchol. Vyhledáváme klíč nového vrcholu a pokud není nalezen, tak jej vložíme na místo nalezeného vrcholu. Pokud je nalezen, tak se vrchol nevkládá.
tree-insert(tree, added)
pokud t.root == nil, nastavíme t.root <- added a končíme
y <- poslední navštívený vrchol při neúspěšném hledání klíče added.id
pokud (added.id < y.id)
zapojíme added jako levého potomka y
pokud (added.id > y.id)
zapojíme added jako pravého potomka y
added.parent <- y — tady víme, že added != nil, obecně to musíme testovat
Pro odebírání vrcholu z stromu musíme najít vrchol, který chceme odebrat. Pokud vrchol není nalezen, tak se nic neděje. Pokud je nalezen, tak se vrchol odebere. Při odebírání mohou nastat 3 možnosti.
V tomto případě stačí vrchol odebrat.
V tomto případě stačí vrchol odebrat a potomka připojit k jeho rodiči.
V tomto případě musíme vrchol nahradit jeho pořádkovým následníkem. Pořádkový následník má maximálně jednoho potomka, takže se jedná o jeden z předchozích případů.
tree-swap(tree, node, replacement)
pokud tree.root == node, nastavíme tree.root <- replacement
jinak y = node.parent
pokud node == y.left, nastavíme y.left <- replacement
pokud node == y.right nastavíme y.right <- replacement
node-swap(tree, node, replacement)
node.left = replacement.left
node.right = replacement.right
if tree.root == node
tree.root = replacement
else
y = node.parent
if node == y.left
y.left = replacement
else
y.right = replacement
tree-delete(tree, node)
pokud node.left == nil, tree-swap(tree, node, node.right)
pokud node.right == nil, tree-swap(tree, node, node.left)
jinak y = tree-min(node.right)
tree-delete(tree, y)
node-swap(tree, node, y)