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í strom

Definice

Dynamická množina je množina prvků (datová struktura), měnící se v čase. Každý její prvek je přístupný přes ukazatel a obsahuje:

- klíč (jednu položku, typicky hodnotu z lin. uspořádané množiny),
- ukazatel(e) na další prvky,
- případně další data.

Na takové množině jsou definovány tyto operace:

- find - nalezení prvku podle klíče
- insert - přidání dalšího prvku
- delete - odstranění prvku
- min, max - nalezení největšího / nejmenšího prvku
- succ, pred - nalezení následujícího / předcházejícího prvku k nějakému předem danému

Definice

Binární strom je dynamická množina, kde každý prvek (uzel, node) má kromě klíče a příp. dalších dat tři ukazatele na levého a pravého syna a rodiče. Speciální uzel je kořen, který má NULLový ukazatel na rodiče. Ten je v binárním stromě jeden. Uzly, které mají NULLové ukazatele na pravého i levého syna, se nazývají listy.

Podstrom je část stromu (vybrané prvky), která je sama stromem - např. pokud se jako kořen určí jeden z prvků. Levý(pravý) podstrom nějakého prvku je strom, ve kterém je kořenem levý(pravý) syn tohoto prvku. Výška stromu je délka nejdelší cesty od kořenu k listu.

Binární strom je vyvážený, pokud max. 1 uzel má jednoho syna (tj. všechny vnitřní uzly kromě až na jeden mají oba syny, listy z definice nemají žádného). Výška vyváženého stromu roste logaritmicky vzhledem k počtu uzlů. Výška nevyváženého stromu může růst až lineárně vzhledem k počtu prvků (i spojový seznam je platný bin. strom).