Strom, průchody stromem, binární vyhledávací stromy - Historie editací

88.102.245.51: /* Definice */

2018-05-22T20:12:18Z

Definice

← Starší verze		Verze z 22. 5. 2018, 20:12
Řádka 6:		Řádka 6:
	* '''Vrchol (uzel)''' - jeden prvek stromu. Má jednoho předchůdce a 0 - N následovníků.		* '''Vrchol (uzel)''' - jeden prvek stromu. Má jednoho předchůdce a 0 - N následovníků.
	* '''Hrana (větev)''' - spojení dvou vrcholů		* '''Hrana (větev)''' - spojení dvou vrcholů
−	* '''List''' - ~~nrchol~~ bez následovníků	+	* '''List''' - vrchol bez následovníků
	* '''Kořen''' - vrchol, který nemá žádné předchůdce. Z kořene je pak možné se dostat do jakéhokoliv uzlu stromu. Každý strom má jen jeden kořen.		* '''Kořen''' - vrchol, který nemá žádné předchůdce. Z kořene je pak možné se dostat do jakéhokoliv uzlu stromu. Každý strom má jen jeden kořen.
	* '''Podstrom''' - // dopsat		* '''Podstrom''' - // dopsat
Řádka 27:		Řádka 27:

	Adresářová struktura, sportovní výsledky, reprezentace stromů v přírodě :), ....		Adresářová struktura, sportovní výsledky, reprezentace stromů v přírodě :), ....
−

	== Průchod stromem ==		== Průchod stromem ==

Acolade: kategorizace

2014-02-20T06:35:21Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:35
Řádka 72:		Řádka 72:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Průchod stromem */

2011-08-30T16:07:22Z

Průchod stromem

← Starší verze		Verze z 30. 8. 2011, 16:07
Řádka 38:		Řádka 38:
	Procházení stromu může být průchod do hloubky dvojího druhu, podle priority operací:		Procházení stromu může být průchod do hloubky dvojího druhu, podle priority operací:
	* '''Preorder''' - Nejprve vyzvedneme data vrcholu a poté projdeme postupně všechny podstromy		* '''Preorder''' - Nejprve vyzvedneme data vrcholu a poté projdeme postupně všechny podstromy
		+	preorder(node) {
		+	print node.value
		+	if node.left ≠ null then preorder(node.left)
		+	if node.right ≠ null then preorder(node.right)
		+	}
		+
	* '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu		* '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu
		+	postorder(node) {
		+	if node.left ≠ null then postorder(node.left)
		+	if node.right ≠ null then postorder(node.right)
		+	print node.value
		+	}
		+

	Procházení binárního stromu má navíc ještě jeden způsob:		Procházení binárního stromu má navíc ještě jeden způsob:

Tester: /* Binární vyhledávací strom (BVS) */

2011-08-26T08:15:58Z

Binární vyhledávací strom (BVS)

← Starší verze		Verze z 26. 8. 2011, 08:15
Řádka 59:		Řádka 59:
	Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.		Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.

−	{{fav-kiv--bzinf}}	+	{{fav-kiv-bzinf}}

Tester: /* Binární vyhledávací strom (BVS) */

2011-08-26T08:11:41Z

Binární vyhledávací strom (BVS)

← Starší verze		Verze z 26. 8. 2011, 08:11
Řádka 58:		Řádka 58:

	Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.		Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.
		+
		+	{{fav-kiv--bzinf}}

Tester v 10. 8. 2011, 09:20

2011-08-10T09:20:55Z

← Starší verze		Verze z 10. 8. 2011, 09:20
Řádka 16:		Řádka 16:
	// přidat obrázek s popisem částí stromu		// přidat obrázek s popisem částí stromu

−		+	[[Soubor:Strom.jpg]]

Tester: /* Binární vyhledávací strom (BVS) */

2011-08-06T13:25:25Z

Binární vyhledávací strom (BVS)

← Starší verze		Verze z 6. 8. 2011, 13:25
Řádka 49:		Řádka 49:
	Pri přidáváni vrcholu začínáme u kořene, a rozhodujeme se, kterou hranou jít dále, tedy je li vkládaný prvek menší , nebo větší než tento kořen. Takto postupujeme i vybraným podstromem až najdeme místo, kam vrchol umístit. Umístěný vrchol je vždy listem stromu.		Pri přidáváni vrcholu začínáme u kořene, a rozhodujeme se, kterou hranou jít dále, tedy je li vkládaný prvek menší , nebo větší než tento kořen. Takto postupujeme i vybraným podstromem až najdeme místo, kam vrchol umístit. Umístěný vrchol je vždy listem stromu.

−	Mazání je složitější.	+	Mazání je složitější. Nejprve vrchol najdeme ve stromu a podle toho jaký je:
−	Nejprve vrchol najdeme ve stromu.	+	* Pokud je listem, je to triviální
−	Pokud je ~~lisemt~~, je to triviální	+	* Pokud vrchol má pouze jeden podstrom, vrchol smažeme a na jeho místo umístíme kořen jeho (jediného) podstromu
−	Pokud vrchol má pouze jeden podstrom, vrchol smažeme a na jeho místo umístíme kořen jeho (jediného) podstromu	+	* Pokud má dva, vydáme se doprava a poté jdeme stále doleva dokud nenarazíme na list, který smažeme, ale jeho hodnotu přiřadíme původně mazanému vrcholu.
−	Pokud má dva, vydáme se doprava a poté jdeme stále doleva dokud nenarazíme na list, který smažeme, ale jeho hodnotu přiřadíme původně mazanému vrcholu.	+

	Tento strom je nevyvážený, tedy může nastat situace, kdy bude jeden podstrom kořenu mít výrazně větší výšku než podstrom druhý.		Tento strom je nevyvážený, tedy může nastat situace, kdy bude jeden podstrom kořenu mít výrazně větší výšku než podstrom druhý.
	První vložený prvek bude vždy kořen stromu. Při načítání prvků do stromu je tedy vhodné alespoň pro tento prvek nalézt medián.		První vložený prvek bude vždy kořen stromu. Při načítání prvků do stromu je tedy vhodné alespoň pro tento prvek nalézt medián.

−	Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.	+	Přidání prvku do pole a mazání je maximálně O(n) (pro strom, který byl vytvořen ze seřazené posloupnosti - je to tedy pouze lineární spojový seznam), očekávaná složitost operací je však O(log2 n) jelikož je strom v každém vrcholu rozdělen na 2 skupiny hodnot.

Tester: /* Průchod stromem */

2011-08-06T09:22:46Z

Průchod stromem

← Starší verze		Verze z 6. 8. 2011, 09:22
Řádka 40:		Řádka 40:
	* '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu		* '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu

−	Procházení binárního stromu má navíc ještě jeden způsob,	+	Procházení binárního stromu má navíc ještě jeden způsob:
	* '''Inorder''' - Projdeme levý podstrom, poté vyzvedneme data vrcholu, a poté pravý podstrom. Při výpisu BVS touto metodou dojdeme k seřazenému poli.		* '''Inorder''' - Projdeme levý podstrom, poté vyzvedneme data vrcholu, a poté pravý podstrom. Při výpisu BVS touto metodou dojdeme k seřazenému poli.
−

	== Binární vyhledávací strom (BVS) ==		== Binární vyhledávací strom (BVS) ==

Tester v 6. 8. 2011, 09:22

2011-08-06T09:22:21Z

← Starší verze		Verze z 6. 8. 2011, 09:22
Řádka 28:		Řádka 28:
	Adresářová struktura, sportovní výsledky, reprezentace stromů v přírodě :), ....		Adresářová struktura, sportovní výsledky, reprezentace stromů v přírodě :), ....

−	~~Průchod stromem:~~

−	Do šířky - Projdeme vrcholy po patrech, tedy kořen, postupně kořeny jeho podstromů, kořeny všech těchto podstromů atd. Jelikož ve stromech obecně neznáme sousedy, musíme se často vracet. Měřením cesty vrcholů však múžeme prohledávání do šířky převést na prohledávání do hloubky, i když ne zrovna elegantní (vyhledáme všechny vrcholy o hloubkách 0, pak 1, pak 2, ...)	+	== Průchod stromem ==
		+
		+	'''Do šířky''' - Projdeme vrcholy po patrech, tedy kořen, postupně kořeny jeho podstromů, kořeny všech těchto podstromů atd. Jelikož ve stromech obecně neznáme sousedy, musíme se často vracet. Měřením cesty vrcholů však múžeme prohledávání do šířky převést na prohledávání do hloubky, i když ne zrovna elegantní (vyhledáme všechny vrcholy o hloubkách 0, pak 1, pak 2, ...)
		+
		+	'''Do hloubky''' - Procházíme vrcholy do hloubky, tedy dojdeme-li do vrcholu, projdeme jeho podstromy a poté se teprve vracíme
		+

−	~~Do hloubky - Procházíme vrcholy do hloubky, tedy dojdeme-li do vrcholu, projdeme jeho podstromy a poté se teprve vracíme~~
	Procházení stromu může být průchod do hloubky dvojího druhu, podle priority operací:		Procházení stromu může být průchod do hloubky dvojího druhu, podle priority operací:
−	Preorder - Nejprve vyzvedneme data vrcholu a poté projdeme postupně všechny podstromy	+	* '''Preorder''' - Nejprve vyzvedneme data vrcholu a poté projdeme postupně všechny podstromy
−	Postorder - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu	+	* '''Postorder''' - Nejprve projdeme všechny podstromy, a poté vyzvedneme data vrcholu
		+
	Procházení binárního stromu má navíc ještě jeden způsob,		Procházení binárního stromu má navíc ještě jeden způsob,
−	3. Inorder - Projdeme levý podstrom, poté vyzvedneme data vrcholu, a poté pravý podstrom. Při výpisu BVS touto metodou dojdeme k seřazenému poli.	+	* '''Inorder''' - Projdeme levý podstrom, poté vyzvedneme data vrcholu, a poté pravý podstrom. Při výpisu BVS touto metodou dojdeme k seřazenému poli.
		+

−	Binární vyhledávací strom (BVS):	+	== Binární vyhledávací strom (BVS) ==

	BVS je binární strom (strom, který má maximálně 2 podstromy v kažném vrholu) vytvořený tak, že kořen levého podstromu každého vrcholu má nižší hodnotu než tento vrchol a ten má nižší hodnotu než kořen pravého podstromu.		BVS je binární strom (strom, který má maximálně 2 podstromy v kažném vrholu) vytvořený tak, že kořen levého podstromu každého vrcholu má nižší hodnotu než tento vrchol a ten má nižší hodnotu než kořen pravého podstromu.

Tester v 5. 8. 2011, 18:23

2011-08-05T18:23:28Z

← Starší verze		Verze z 5. 8. 2011, 18:23
Řádka 4:		Řádka 4:
	== Definice ==		== Definice ==

−	'''Vrchol (uzel)''' - jeden prvek stromu. Má jednoho předchůdce a 0 - N následovníků.	+	* '''Vrchol (uzel)''' - jeden prvek stromu. Má jednoho předchůdce a 0 - N následovníků.
−	'''Hrana (větev)''' - spojení dvou vrcholů	+	* '''Hrana (větev)''' - spojení dvou vrcholů
−	'''List''' - nrchol bez následovníků	+	* '''List''' - nrchol bez následovníků
−	'''Kořen''' - vrchol, který nemá žádné předchůdce. Z kořene je pak možné se dostat do jakéhokoliv uzlu stromu. Každý strom má jen jeden kořen.	+	* '''Kořen''' - vrchol, který nemá žádné předchůdce. Z kořene je pak možné se dostat do jakéhokoliv uzlu stromu. Každý strom má jen jeden kořen.
−	'''Podstrom''' - // dopsat	+	* '''Podstrom''' - // dopsat
−	'''Cesta stromem''' - cesta od libovolného vrcholu ke kořeni stromu. Tato cesta je ve stromu unikátní.	+	* '''Cesta stromem''' - cesta od libovolného vrcholu ke kořeni stromu. Tato cesta je ve stromu unikátní.
−	'''Hloubka vrcholu''' - délka cesty od kořene do daného vrcholu.	+	* '''Hloubka vrcholu''' - délka cesty od kořene do daného vrcholu.
−	'''Výška stromu''' - nejdelší možná cesta ve stromu.	+	* '''Výška stromu''' - nejdelší možná cesta ve stromu.