Directed Tree - Revision history

Weihe at 11:29, 26 May 2015

2015-05-26T11:29:44Z

← Older revision		Revision as of 11:29, 26 May 2015
Line 37:		Line 37:
	## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and		## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and
	## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.		## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.


	= Ranges of Search Tree Nodes =		= Ranges of Search Tree Nodes =
Line 51:		Line 52:
	### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;		### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.


	= Order of Tree Nodes in a Binary Search Tree =		= Order of Tree Nodes in a Binary Search Tree =

Weihe: /* Multi-way Search Trees */

2015-05-26T11:28:58Z

Multi-way Search Trees

← Older revision		Revision as of 11:28, 26 May 2015
Line 34:		Line 34:
	# Each node <math>v \in V</math> is assigned a non-empty multiset <math>S_v \subseteq \mathcal{K}</math>.		# Each node <math>v \in V</math> is assigned a non-empty multiset <math>S_v \subseteq \mathcal{K}</math>.
	# Consider a node <math>v \in V</math> and let <math>d_v</math> denote <math>v</math>'s [[Basic graph definitions#Adjacency, incidence, and degree\|outdegree]]. If <math>d_v > 0</math>, it is <math>\|S_v\| = d_v - 1</math>; otherwise, <math>\|S_v\|</math> may be arbitrary.		# Consider a node <math>v \in V</math> and let <math>d_v</math> denote <math>v</math>'s [[Basic graph definitions#Adjacency, incidence, and degree\|outdegree]]. If <math>d_v > 0</math>, it is <math>\|S_v\| = d_v - 1</math>; otherwise, <math>\|S_v\|</math> may be arbitrary.
	# For <math>v \in V</math>, the outgoing arcs of <math>v</math> are ordered and assigned positions numbered <math>0,\dots,\|S_v\|</math>. For the outgoing arc <math>(v,w) \in A</math> at position <math>i \in \{0,\dots,\|S_v\|\}</math> and any key <math>K</math>in the subtree rooted at <math>w</math>, it is		# For <math>v \in V</math>, the outgoing arcs of <math>v</math> are ordered and assigned positions numbered <math>0,\dots,\|S_v\|</math>. For the outgoing arc <math>(v,w) \in A</math> at position <math>i \in \{0,\dots,\|S_v\|\}</math> and any key <math>K</math>in the subtree rooted at <math>w</math> (incl. <math>w</math>), it is
	## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and		## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and
	## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.		## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.

Weihe at 10:45, 20 May 2015

2015-05-20T10:45:32Z

← Older revision		Revision as of 10:45, 20 May 2015
Line 67:		Line 67:
	'''Remark:'''		'''Remark:'''
	The sorted sequence of all keys in a binary search tree is the left-root-right order.		The sorted sequence of all keys in a binary search tree is the left-root-right order.


	= Immediate Predecessor and Successor =		= Immediate Predecessor and Successor =

Weihe: /* Order of tree nodes in a binary search tree */

2015-05-20T10:45:08Z

Order of tree nodes in a binary search tree

← Older revision		Revision as of 10:45, 20 May 2015
Line 52:		Line 52:
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.

	= Order of ~~tree nodes~~ in a ~~binary search tree~~ =		= Order of Tree Nodes in a Binary Search Tree =
	Let <math>T = (V,A)</math> be a binary search tree and let <math>S \subseteq \mathcal{K}</math> denote the set of all key values of all nodes of <math>T</math>.		Let <math>T = (V,A)</math> be a binary search tree and let <math>S \subseteq \mathcal{K}</math> denote the set of all key values of all nodes of <math>T</math>.

Weihe: /* Order of Tree Nodes */

2015-05-20T10:44:46Z

Order of Tree Nodes

← Older revision		Revision as of 10:44, 20 May 2015
Line 52:		Line 52:
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.

	= Order of ~~Tree Nodes~~ =		= Order of tree nodes in a binary search tree =
	Let <math>T = (V,A)</math> be a binary search tree and let <math>S \subseteq \mathcal{K}</math> denote the set of all key values of all nodes of <math>T</math>.		Let <math>T = (V,A)</math> be a binary search tree and let <math>S \subseteq \mathcal{K}</math> denote the set of all key values of all nodes of <math>T</math>.

Line 66:		Line 66:

	'''Remark:'''		'''Remark:'''
	The sorted sequence of all keys in a search tree is the left-root-right order.		The sorted sequence of all keys in a binary search tree is the left-root-right order.


	= Immediate Predecessor and Successor =		= Immediate Predecessor and Successor =

Weihe: /* Ranges of Search Tree Nodes */

2015-05-20T10:41:50Z

Ranges of Search Tree Nodes

← Older revision		Revision as of 10:41, 20 May 2015
Line 45:		Line 45:
	### <math>R_v := R_u \cap \{K \in \mathcal{K} \| K \leq K_u\}</math>		### <math>R_v := R_u \cap \{K \in \mathcal{K} \| K \leq K_u\}</math>
	### <math>R_w := R_u \cap \{K \in \mathcal{K} \| K \geq K_u\}</math>		### <math>R_w := R_u \cap \{K \in \mathcal{K} \| K \geq K_u\}</math>
	# Now let <math>T = (V,A)</math> be a ~~mutli~~-way search tree:		# Now let <math>T = (V,A)</math> be a multi-way search tree:
	## Again, the range of <math>r</math> is <math>\mathcal{K}</math>.		## Again, the range of <math>r</math> is <math>\mathcal{K}</math>.
	## For <math>v \in V\setminus\{r\}</math>, let <math>w \in V</math> denote the parent node, and let <math>i</math> be the position of <math>(w,v)</math> in the ordered sequence of outgoing arcs of <math>w</math>. Then the '''range''' of <math>v</math> is		## For <math>v \in V\setminus\{r\}</math>, let <math>w \in V</math> denote the parent node, and let <math>i</math> be the position of <math>(w,v)</math> in the ordered sequence of outgoing arcs of <math>w</math>. Then the '''range''' of <math>v</math> is
Line 51:		Line 51:
	### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;		### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.


	= Order of Tree Nodes =		= Order of Tree Nodes =

Weihe: /* Multi-way Search Trees */

2015-05-20T10:40:17Z

Multi-way Search Trees

← Older revision		Revision as of 10:40, 20 May 2015
Line 34:		Line 34:
	# Each node <math>v \in V</math> is assigned a non-empty multiset <math>S_v \subseteq \mathcal{K}</math>.		# Each node <math>v \in V</math> is assigned a non-empty multiset <math>S_v \subseteq \mathcal{K}</math>.
	# Consider a node <math>v \in V</math> and let <math>d_v</math> denote <math>v</math>'s [[Basic graph definitions#Adjacency, incidence, and degree\|outdegree]]. If <math>d_v > 0</math>, it is <math>\|S_v\| = d_v - 1</math>; otherwise, <math>\|S_v\|</math> may be arbitrary.		# Consider a node <math>v \in V</math> and let <math>d_v</math> denote <math>v</math>'s [[Basic graph definitions#Adjacency, incidence, and degree\|outdegree]]. If <math>d_v > 0</math>, it is <math>\|S_v\| = d_v - 1</math>; otherwise, <math>\|S_v\|</math> may be arbitrary.
	# For <math>v \in V</math>, the outgoing arcs of <math>v</math> are ordered and assigned positions numbered <math>0,\dots,\|S_v\|</math>. For the outgoing arc <math>(v,w) \in A</math> at position <math>i \in \{0,\dots,\|S_v\|\}</math> and any <math>K \in ~~S_w~~</math>, it is		# For <math>v \in V</math>, the outgoing arcs of <math>v</math> are ordered and assigned positions numbered <math>0,\dots,\|S_v\|</math>. For the outgoing arc <math>(v,w) \in A</math> at position <math>i \in \{0,\dots,\|S_v\|\}</math> and any key <math>K</math>in the subtree rooted at <math>w</math>, it is
	## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and		## <math>K \geq K'</math> for at least <math>i</math> elements <math>K'</math> of <math>S_v</math> and
	## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.		## <math>K \leq K'</math> for at least <math>\|S_v\| - i</math> elements <math>K'</math> of <math>S_v</math>.


	= Ranges of Search Tree Nodes =		= Ranges of Search Tree Nodes =

Weihe at 07:32, 18 May 2015

2015-05-18T07:32:19Z

← Older revision		Revision as of 07:32, 18 May 2015
Line 2:		Line 2:

	[[Category:Background]]		[[Category:Background]]


	= Basic Definitions =		= Basic Definitions =

Weihe at 07:31, 18 May 2015

2015-05-18T07:31:58Z

← Older revision		Revision as of 07:31, 18 May 2015
Line 50:		Line 50:
	### <math>R_v := \{K \in R_w \| K \leq \min S_w\}</math>, if <math>i = 0</math>;		### <math>R_v := \{K \in R_w \| K \leq \min S_w\}</math>, if <math>i = 0</math>;
	### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;		### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order of [[Genericity\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order defined by [[Genericity#Comparison\|comparison]] <math>c</math>.


	= Order of Tree Nodes =		= Order of Tree Nodes =
Line 65:		Line 66:
	## if the right arc <math>(v,w)</math> exists, all keys in the subtree rooted at <math>w</math> succeed the key of <math>v</math>.		## if the right arc <math>(v,w)</math> exists, all keys in the subtree rooted at <math>w</math> succeed the key of <math>v</math>.

			'''Remark:'''
	~~===~~ Remark ~~===~~
	The sorted sequence of all keys in a search tree is the left-root-right order.		The sorted sequence of all keys in a search tree is the left-root-right order.

Weihe: /* Ranges of Search Tree Nodes */

2015-05-18T07:30:36Z

Ranges of Search Tree Nodes

← Older revision		Revision as of 07:30, 18 May 2015
Line 48:		Line 48:
	## Again, the range of <math>r</math> is <math>\mathcal{K}</math>.		## Again, the range of <math>r</math> is <math>\mathcal{K}</math>.
	## For <math>v \in V\setminus\{r\}</math>, let <math>w \in V</math> denote the parent node, and let <math>i</math> be the position of <math>(w,v)</math> in the ordered sequence of outgoing arcs of <math>w</math>. Then the '''range''' of <math>v</math> is		## For <math>v \in V\setminus\{r\}</math>, let <math>w \in V</math> denote the parent node, and let <math>i</math> be the position of <math>(w,v)</math> in the ordered sequence of outgoing arcs of <math>w</math>. Then the '''range''' of <math>v</math> is
	### <math>R_v := \{K \in R_w \| K \leq ~~minS_w~~\}</math>, if <math>i = 0</math>;		### <math>R_v := \{K \in R_w \| K \leq \min S_w\}</math>, if <math>i = 0</math>;
	### <math>R_v := \{K \in R_w \| K \geq ~~maxS_w~~\}</math>, if <math>i = \|S_w\|</math>;		### <math>R_v := \{K \in R_w \| K \geq \max S_w\}</math>, if <math>i = \|S_w\|</math>;
	### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order of [[Genericity\|comparison]] <math>c</math>.		### <math>R_v := \{K \in R_w \| K \geq a, K \leq b\}</math>, otherwise, where <math>a,b \in S_w</math> are the <math>i</math>-th and <math>(i + 1)</math>-st element of <math>S_w</math> in the sorting order of [[Genericity\|comparison]] <math>c</math>.