Datové struktury - U vod
Navrhněte co nejjednodušší datovou strukturu, která podporuje následující operace:
1. Insert a Delete v O(n), Search v 0(\og rí)\
Datové struktury - U vod
Navrhněte co nejjednodušší datovou strukturu, která podporuje následující operace:
1. Insert a Delete v O(n), Search v 0(\og n);
2. Insert a Delete v O(n), Predecessor a Successor v 0(1);
Datové struktury - U vod
Navrhněte co nejjednodušší datovou strukturu, která podporuje následující operace:
1. Insert a Delete v O(n), Search v 0(\og n);
2. Insert a Delete v O(n), Predecessor a Successor v (9(1);
3. Insert a Delete v 0(1), Minimum a Maximum(S) v O(n).
Datové struktury - Príklad 1
Klíč a priorita
Mějme prvky tvaru (/c,p), kde k je klíč a p je priorita. Navrhněte datovou strukturu takovou, aby následující tři operace měly složitost 0(\ogn), kde n je počet prvků ve struktuře.
► Insert(/c,p) - pokud prvek s klíčem k ve struktuře neexistuje, vloží nový prvek do struktury; pokud už prvek s klíčem k existuje, změní jeho prioritu
► Delete(/c) - odstraní prvek s klíčem k
► Get(/c) - najde prvek s nejmenší prioritou z těch, které mají klíč < k
Datové struktury - Príklad 2
Navrhněte datovou strukturu vytvořenou ze sekvence n hodnot xi, .. ., xn a která má podporovat následující operaci:
► Min(/,j) - nejmenší hodnota z x;, x;+i, ..., xy.
Jaký nejlepší poměr časové složitosti vytvoření dané struktury a dotazů Min jste schopni dosáhnout?
Datové struktury - Vyváženost stromů
Rozhodněte (a dokažte), zda následující podmínky zaručují vyváženost binárních stromů, tj. zda mají všechny binární stromy splňující danou podmínku výšku 0(\ogn), kde n je počet uzlů stromu.
1. Každý uzel je buď list nebo má právě dva potomky.
Datové struktury - Vyváženost stromů
Rozhodněte (a dokažte), zda následující podmínky zaručují vyváženost binárních stromů, tj. zda mají všechny binární stromy splňující danou podmínku výšku 0(\ogn), kde n je počet uzlů stromu.
1. Každý uzel je buď list nebo má právě dva potomky.
2. Velikost každého podstromu je právě 2k — 1, kde k EN. {k nemusí být stejné pro všechny podstromy.)
Datové struktury - Vyváženost stromů
Rozhodněte (a dokažte), zda následující podmínky zaručují vyváženost binárních stromů, tj. zda mají všechny binární stromy splňující danou podmínku výšku 0(\ogn), kde n je počet uzlů stromu.
1. Každý uzel je buď list nebo má právě dva potomky.
2. Velikost každého podstromu je právě 2k — 1, kde k EN. {k nemusí být stejné pro všechny podstromy.)
3. Existuje 0 < c < 1 takové, že pro každý uzel platí, že velikost jeho menšího podstromu je alespoň cnásobek velikosti jeho většího podstromu. (Má-li uzel jen jednoho potomka, uvažujeme, že jeho menší podstrom má velikost 0).
Datové struktury - Vyváženost stromů
Rozhodněte (a dokažte), zda následující podmínky zaručují vyváženost binárních stromů, tj. zda mají všechny binární stromy splňující danou podmínku výšku 0(\ogn), kde n je počet uzlů stromu.
1. Každý uzel je buď list nebo má právě dva potomky.
2. Velikost každého podstromu je právě 2k — 1, kde k EN. {k nemusí být stejné pro všechny podstromy.)
3. Existuje 0 < c < 1 takové, že pro každý uzel platí, že velikost jeho menšího podstromu je alespoň cnásobek velikosti jeho většího podstromu. (Má-li uzel jen jednoho potomka, uvažujeme, že jeho menší podstrom má velikost 0).
4. Existuje c takové, že pro každý uzel platí, že výška podstromů jeho dvou potomků se liší maximálně o c.
Datové struktury - Vyváženost stromů
Rozhodněte (a dokažte), zda následující podmínky zaručují vyváženost binárních stromů, tj. zda mají všechny binární stromy splňující danou podmínku výšku 0(\ogn), kde n je počet uzlů stromu.
1. Každý uzel je buď list nebo má právě dva potomky.
2. Velikost každého podstromu je právě 2k — 1, kde k EN. {k nemusí být stejné pro všechny podstromy.)
3. Existuje 0 < c < 1 takové, že pro každý uzel platí, že velikost jeho menšího podstromu je alespoň cnásobek velikosti jeho většího podstromu. (Má-li uzel jen jednoho potomka, uvažujeme, že jeho menší podstrom má velikost 0).
4. Existuje c takové, že pro každý uzel platí, že výška podstromů jeho dvou potomků se liší maximálně o c.
5. Průměrná hloubka uzluje 0(\ogn). (Hloubka uzlu je vzdálenost od kořene.)