Definujte binární strom. Definujte binární vyhledávací strom a popište v něm operace vložení a odstranění prvku a uveďte jejich časové složitosti.

Definice binárního stromu a binárního vyhledávacího stromu je na předchozí Veta otázce

BSTInsert

• předpokládáme, že pracujeme s BST s unikátními klíči vrcholů

Vstup: klíč určený k vložení do BST, ukazatel na kořen BST

Výstup : ukazatel na kořen BST s vloženým klíčem, či bez něj (pokud už ve stromě existoval)

bool BSTInsert(klíč x, vrchol v)
{
	Pokud v == NULL:
		vytvoř nový vrchol s klíčem x
		return v;
	
	Pokud: x = k(v): return v;

	Pokud x < k(v): l(v) := BSTInsert(x, l(v))
	Pokud x > k(v): p(v) := BSTInsert(x, p(v))
	
return v;
}

Maximální časová složitost: O(h) → h = výška BST

• pokud je strom vybalancovaný ⇒ rozdíl hloubek podstromů není více než 2
  • pracujeme se složitostí O(log n)
• pokud je strom nevybalancovaný a představuje ho například list
  • pracujeme se složitostí O(n)