Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Binární vyhledávací strom

Definice

Binární vyhledávací strom je takový binární strom, ve kterém je jeho struktura určená podle klíču jeho uzlů: pro každý uzel s klíčem hodnoty platí, že jeho levý podstrom obsahuje jen uzly s menší hodnotou klíče než a jeho pravý podstrom jen uzly s hodnotou klíče větší nebo rovnou .

Algoritmus (Vyhledávání v bin. stromě)

    Find( x - kořen, k - hledaná hodnota klíče ){
    while( x != NULL && k != x->klíč ){
    if ( k < x->klíč )
    x = x->levý_syn;
    else
    x = x->pravý_syn;
    }
    return x;
    }

Složitost je v nejhorším případě, kde je výška stromu (tj. pro nevyvážené stromy až kde je počet prvků). Asymptotická časová složitost ostatních operací je stejná.

Vložení a vymazání prvku se provádí prostým nalezením místa, kam by se prvek měl vložit (nebo kde už je), a přepojením pointerů.