| Both sides previous revision Previous revision Next revision | Previous revision |
| pjc:03:start [2013/02/23 13:44] – [Testování na OS Windows] vikturek | pjc:03:start [2013/02/26 14:55] (current) – [Úloha 3 - množina s binárním stromem] vikturek |
|---|
| ====== Domácí úkol 3 - množina s binárním stromem ====== | ====== Úloha 3 - množina s binárním stromem ====== |
| |
| {{:pjc:3_loga_velikost_100.jpg?800|}} | {{:pjc:3_loga_velikost_100.jpg|}} |
| | |
| | **Evropský sociální fond** |
| | |
| | **Praha & EU: Investujeme do vaší budoucnosti** |
| |
| Tato úloha vznikla za přispění fondu [[http://www.prahafondy.eu/cz/oppa.html|OPPA]]. | Tato úloha vznikla za přispění fondu [[http://www.prahafondy.eu/cz/oppa.html|OPPA]]. |
| Množina je datová struktura, do které lze ukládat datové prvky. Do standardní množiny lze uložit stejný prvek jen jednou. U naší množiny BSTSET to platí také, ale navíc si dokáže u každé vložené hodnoty zapamatovat, kolikrát byla vložena. Každá množina se vnitřně implementuje tak, že jsou prvky seřazeny a tím je usnadněno vyhledávání a tím tedy i rozhodování, zda se v množině hodnota již nachází nebo ne. V naší množině je řazení realizováno pomocí binárního vyhledavácího stromu (BST). BST má dva typy uzlů - vnitřní a okrajové. Okrajové uzly obsahují uloženou hodnotu a počet, kolikrát byla vložena. Vnitřní obsahují odkazy na levý a pravý podstrom, přičemž platí, že všechny hodnoty v levém podstromu jsou menší než všechny hodnoty v pravém podstromu. Primárně se vkládá do levého podstromu. Činnost BST pro vložení prvků 5, 8, 3, 6, 9 naznačuje následující obrázek: | Množina je datová struktura, do které lze ukládat datové prvky. Do standardní množiny lze uložit stejný prvek jen jednou. U naší množiny BSTSET to platí také, ale navíc si dokáže u každé vložené hodnoty zapamatovat, kolikrát byla vložena. Každá množina se vnitřně implementuje tak, že jsou prvky seřazeny a tím je usnadněno vyhledávání a tím tedy i rozhodování, zda se v množině hodnota již nachází nebo ne. V naší množině je řazení realizováno pomocí binárního vyhledavácího stromu (BST). BST má dva typy uzlů - vnitřní a okrajové. Okrajové uzly obsahují uloženou hodnotu a počet, kolikrát byla vložena. Vnitřní obsahují odkazy na levý a pravý podstrom, přičemž platí, že všechny hodnoty v levém podstromu jsou menší než všechny hodnoty v pravém podstromu. Primárně se vkládá do levého podstromu. Činnost BST pro vložení prvků 5, 8, 3, 6, 9 naznačuje následující obrázek: |
| |
| | {{:pjc:03:bstset.jpg|}} |
| {{:homeworks:2011zs:bstset.jpg|}} | |
| |
| Implementace BTSET obsahuje: | Implementace BTSET obsahuje: |