Diskuze: Generické a binární stromy

Volná diskuze Generické a binární stromy

Avatar
Majkel
Člen
Avatar
Majkel:

Ahoj, jak se dají prakticky využít tyto datové struktury. Používáte to někdo na něco v praxi?

 
Odpovědět  +1 9. června 20:04
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Majkel
patrik.valkovic:

Samozřejmě, prioritní fronta, kterou určitě vyuříváš, pracuje nad haldou, což je binární strom. Binární vyhledávací strom je základní struktura, pokud chceš uchovávat data seřazená.

Nahoru Odpovědět 9. června 20:26
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Majkel
Člen
Avatar
Majkel:

A co generické stromové struktůry, které na rozdíl od binárních mohou mít libovololný počet podřazených uzlů? Jak se dají využít ty?

 
Nahoru Odpovědět  -1 11. června 13:13
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Majkel
Martin Dráb:

Generické stromy (přesněji: (a-b) stromy, popř. jejich konkrétnější a známější varianta – B-stromy) se dají využít, máš-li větší množství dat, která ale nechceš cpát do obludy typu [doplň svoji oblíbenou databázi] jednak proto, že je to kanón na vrabce, druhak třeba i proto, že neděláš webovku, kde je komunikace s databází zvykem, ale třeba desktopovou aplikaci a nechceš, aby si jenom kvůli tomu, že jsi líný, zákazník musel instalovat ještě další komponenty.

Konkrétně B-stromy a jejich různé varianty (B+, B*, ...) nalézají využití např. v souborových systémech. Například NTFS je používá pro reprezentaci indexů (jedním z typů indexů jsou obsahy adresářů, ale mají tam implementovaný obecný index (a taky jej i tak využívají)). Samozřejmě, *NIXové souborové systémy také nezůstávají pozadu (ReiserFS, určitě EXT3/4...). Výhodou (a-b) stromů zde je, že obsahují větší množství položek v jednom uzlu, což vyhovuje metodám přístupu k diskům (lze načítat pouze větší množství dat najednou).

Co se týče dalšího využití, zkus se podívat na datovou strukturu trie, nebo někam do oblasti počítačové trafiky (myslím, že např. oct-trees (osmistromy)) tam také mají svá uplatnění.

Nahoru Odpovědět 11. června 14:43
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.