Directed Tree: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (22 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
= Definitions = | [[Category:Checkup]] | ||
[[Category:Background]] | |||
= Basic Definitions = | |||
# A '''directed tree''' is a directed graph <math>T = (V,A)</math> with a designated node <math>r \in V</math>, the '''root''', such that for each node <math>v \in V</math>, there is exactly one path from <math>r</math> to <math>v</math> in <math>T</math>. | # A '''directed tree''' is a directed graph <math>T = (V,A)</math> with a designated node <math>r \in V</math>, the '''root''', such that for each node <math>v \in V</math>, there is exactly one path from <math>r</math> to <math>v</math> in <math>T</math>. | ||
# A directed tree <math> T = (V,A)</math> is called '''binary''' if each node's outdegree is at most <math>2</math>. | # A directed tree <math> T = (V,A)</math> is called '''binary''' if each node's outdegree is at most <math>2</math>. | ||
# The '''subtree''' of <math>T</math> '''rooted''' at <math>v \in V</math> is the subgraph induced by all nodes that are reachable from <math>v</math> via paths in <math>T</math> (including <math>v</math>). In particular, <math>T</math> is the subtree of <math>T</math> rooted at <math>r</math>. | # The '''subtree''' of <math>T</math> '''rooted''' at <math>v \in V</math> is the subgraph induced by all nodes that are reachable from <math>v</math> via paths in <math>T</math> (including <math>v</math>). In particular, <math>T</math> is the subtree of <math>T</math> rooted at <math>r</math>. | ||
# For an arc <math>(v,w)</math> in a directed tree, <math>w</math> is a '''child''' of <math>v</math>, and <math>v</math> is the (unique) '''parent''' of <math>w</math>. | # For an arc <math>(v,w)</math> in a directed tree, <math>w</math> is a '''child''' of <math>v</math>, and <math>v</math> is the (unique) '''parent''' of <math>w</math>. | ||
# The '''height level''' of a node in a directed tree is recursivley defined as follows: | # The '''height level''' (or '''height''', for short) of a node in a directed tree is recursivley defined as follows: | ||
## The height level of the root is <math>0</math> | ## The height level of the root is <math>0</math>. | ||
## The height level of any other node is one more than the height level of its parent. | ## The height level of any other node is one more than the height level of its parent. | ||
# The '''height''' of an empty tree is <math>-1</math>. For a non-empty tree, the '''height''' of the tree is the maximum height level of all of its nodes. | # The '''height''' of an empty tree is <math>-1</math>. For a non-empty tree, the '''height''' of the tree is the maximum height level of all of its nodes. | ||
= Binary Search Tree = | = Binary Search Tree = | ||
| Line 13: | Line 19: | ||
A '''binary search tree''' is a binary tree <math>T = (V,A)</math> such that: | A '''binary search tree''' is a binary tree <math>T = (V,A)</math> such that: | ||
# | # Each arc is assigned a unique label, either '''left''' or '''right''': at most one outgoing arc of a node is labeled '''left''', at most one is labeled '''right'''.We speak of '''the''' left and '''the''' right arc of a node, respectively. | ||
# Associated with <math>T</math>, there is a '''key type''' <math>\ | # Associated with <math>T</math>, there is a '''key type''' <math>\mathcal{K}</math> and a [[Genericity#Comparison|comparison]] on <math>\mathcal{K}</math>. | ||
# Each node <math>v \in V</math> is assigned a value <math>K_v \in \ | # Each node <math>v \in V</math> is assigned a value <math>K_v \in \mathcal{K}</math>. | ||
# For an arc <math>(v,w) \in A</math>, the following holds: | # For an arc <math>(v,w) \in A</math>, the following holds: | ||
## If <math>(v,w)</math> is the left arc of <math>v</math>, it is <math>K \leq K_v</math> for all keys <math>K</math> in the subtree rooted at <math>w</math> (incl. <math>K_w</math>). | ## If <math>(v,w)</math> is the left arc of <math>v</math>, it is <math>K \leq K_v</math> for all keys <math>K</math> in the subtree rooted at <math>w</math> (incl. <math>K_w</math>). | ||
## If <math>(v,w)</math> is the right arc of <math>v</math>, it is <math>K \geq K_v</math> for all keys <math>K</math> in the subtree rooted at <math>w</math> (incl. <math>K_w</math>). | ## If <math>(v,w)</math> is the right arc of <math>v</math>, it is <math>K \geq K_v</math> for all keys <math>K</math> in the subtree rooted at <math>w</math> (incl. <math>K_w</math>). | ||
= Multi-way Search Trees = | = Multi-way Search Trees = | ||
A '''multi-way search tree''' is a directed tree <math>T = (V,A)</math> such that: | |||
# Associated with <math>T</math>, there is a '''key type''' <math>\mathcal{K}</math> and a [[Genericity|comparison]] on <math>\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. | |||
# 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 \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 = | ||
Let <math>T = (V,A)</math> be a search tree with root <math>r</math>. The '''range''' of a node is defined recursively: | Let <math>T = (V,A)</math> be a search tree with root <math>r</math>. The '''range''' of a node is defined recursively: | ||
# First let <math>T</math> be a binary tree: | # First let <math>T</math> be a binary tree: | ||
## The range of <math>r</math> is <math>\ | ## The range of <math>r</math> is <math>\mathcal{K}</math>. | ||
## Let <math>u \in V</math>. If existing, let <math>(u,v)</math> and <math>(u, | ## Let <math>u \in V</math>. If existing, let <math>(u,v)</math> and <math>(u,w)</math> denote the left and right arc of <math>u</math>, respectively. The ranges <math>R_v</math> of <math>v</math> and <math>R_w</math> of <math>w</math> are defined as follows: | ||
### <math>R_v := R_u \cap \{K \in \ | ### <math>R_v := R_u \cap \{K \in \mathcal{K} | K \leq K_u\}</math> | ||
### <math>R_w := R_u \cap \{K \in \ | ### <math>R_w := R_u \cap \{K \in \mathcal{K} | K \geq K_u\}</math> | ||
# Now let <math>T = (V,A)</math> be a | # Now let <math>T = (V,A)</math> be a multi-way search tree: | ||
## Again, the range of <math>r</math> is <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 | ### <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 | ### <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 | ### <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 = | |||
Let <math>T = (V,A)</math> be a binary search tree and let <math>S \subseteq \ | = 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>. | |||
# The '''left-root-right order''' of <math>T</math> is the (unique) order of <math>S</math> such that for every node <math>v \in V</math>: | # The '''left-root-right order''' of <math>T</math> is the (unique) order of <math>S</math> such that for every node <math>v \in V</math>: | ||
| Line 49: | Line 67: | ||
## 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:''' | |||
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 = | ||
Latest revision as of 11:29, 26 May 2015
Basic Definitions
- A directed tree is a directed graph [math]\displaystyle{ T = (V,A) }[/math] with a designated node [math]\displaystyle{ r \in V }[/math], the root, such that for each node [math]\displaystyle{ v \in V }[/math], there is exactly one path from [math]\displaystyle{ r }[/math] to [math]\displaystyle{ v }[/math] in [math]\displaystyle{ T }[/math].
- A directed tree [math]\displaystyle{ T = (V,A) }[/math] is called binary if each node's outdegree is at most [math]\displaystyle{ 2 }[/math].
- The subtree of [math]\displaystyle{ T }[/math] rooted at [math]\displaystyle{ v \in V }[/math] is the subgraph induced by all nodes that are reachable from [math]\displaystyle{ v }[/math] via paths in [math]\displaystyle{ T }[/math] (including [math]\displaystyle{ v }[/math]). In particular, [math]\displaystyle{ T }[/math] is the subtree of [math]\displaystyle{ T }[/math] rooted at [math]\displaystyle{ r }[/math].
- For an arc [math]\displaystyle{ (v,w) }[/math] in a directed tree, [math]\displaystyle{ w }[/math] is a child of [math]\displaystyle{ v }[/math], and [math]\displaystyle{ v }[/math] is the (unique) parent of [math]\displaystyle{ w }[/math].
- The height level (or height, for short) of a node in a directed tree is recursivley defined as follows:
- The height level of the root is [math]\displaystyle{ 0 }[/math].
- The height level of any other node is one more than the height level of its parent.
- The height of an empty tree is [math]\displaystyle{ -1 }[/math]. For a non-empty tree, the height of the tree is the maximum height level of all of its nodes.
Binary Search Tree
A binary search tree is a binary tree [math]\displaystyle{ T = (V,A) }[/math] such that:
- Each arc is assigned a unique label, either left or right: at most one outgoing arc of a node is labeled left, at most one is labeled right.We speak of the left and the right arc of a node, respectively.
- Associated with [math]\displaystyle{ T }[/math], there is a key type [math]\displaystyle{ \mathcal{K} }[/math] and a comparison on [math]\displaystyle{ \mathcal{K} }[/math].
- Each node [math]\displaystyle{ v \in V }[/math] is assigned a value [math]\displaystyle{ K_v \in \mathcal{K} }[/math].
- For an arc [math]\displaystyle{ (v,w) \in A }[/math], the following holds:
- If [math]\displaystyle{ (v,w) }[/math] is the left arc of [math]\displaystyle{ v }[/math], it is [math]\displaystyle{ K \leq K_v }[/math] for all keys [math]\displaystyle{ K }[/math] in the subtree rooted at [math]\displaystyle{ w }[/math] (incl. [math]\displaystyle{ K_w }[/math]).
- If [math]\displaystyle{ (v,w) }[/math] is the right arc of [math]\displaystyle{ v }[/math], it is [math]\displaystyle{ K \geq K_v }[/math] for all keys [math]\displaystyle{ K }[/math] in the subtree rooted at [math]\displaystyle{ w }[/math] (incl. [math]\displaystyle{ K_w }[/math]).
Multi-way Search Trees
A multi-way search tree is a directed tree [math]\displaystyle{ T = (V,A) }[/math] such that:
- Associated with [math]\displaystyle{ T }[/math], there is a key type [math]\displaystyle{ \mathcal{K} }[/math] and a comparison on [math]\displaystyle{ \mathcal{K} }[/math].
- Each node [math]\displaystyle{ v \in V }[/math] is assigned a non-empty multiset [math]\displaystyle{ S_v \subseteq \mathcal{K} }[/math].
- Consider a node [math]\displaystyle{ v \in V }[/math] and let [math]\displaystyle{ d_v }[/math] denote [math]\displaystyle{ v }[/math]'s outdegree. If [math]\displaystyle{ d_v \gt 0 }[/math], it is [math]\displaystyle{ |S_v| = d_v - 1 }[/math]; otherwise, [math]\displaystyle{ |S_v| }[/math] may be arbitrary.
- For [math]\displaystyle{ v \in V }[/math], the outgoing arcs of [math]\displaystyle{ v }[/math] are ordered and assigned positions numbered [math]\displaystyle{ 0,\dots,|S_v| }[/math]. For the outgoing arc [math]\displaystyle{ (v,w) \in A }[/math] at position [math]\displaystyle{ i \in \{0,\dots,|S_v|\} }[/math] and any key [math]\displaystyle{ K }[/math]in the subtree rooted at [math]\displaystyle{ w }[/math] (incl. [math]\displaystyle{ w }[/math]), it is
- [math]\displaystyle{ K \geq K' }[/math] for at least [math]\displaystyle{ i }[/math] elements [math]\displaystyle{ K' }[/math] of [math]\displaystyle{ S_v }[/math] and
- [math]\displaystyle{ K \leq K' }[/math] for at least [math]\displaystyle{ |S_v| - i }[/math] elements [math]\displaystyle{ K' }[/math] of [math]\displaystyle{ S_v }[/math].
Ranges of Search Tree Nodes
Let [math]\displaystyle{ T = (V,A) }[/math] be a search tree with root [math]\displaystyle{ r }[/math]. The range of a node is defined recursively:
- First let [math]\displaystyle{ T }[/math] be a binary tree:
- The range of [math]\displaystyle{ r }[/math] is [math]\displaystyle{ \mathcal{K} }[/math].
- Let [math]\displaystyle{ u \in V }[/math]. If existing, let [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (u,w) }[/math] denote the left and right arc of [math]\displaystyle{ u }[/math], respectively. The ranges [math]\displaystyle{ R_v }[/math] of [math]\displaystyle{ v }[/math] and [math]\displaystyle{ R_w }[/math] of [math]\displaystyle{ w }[/math] are defined as follows:
- [math]\displaystyle{ R_v := R_u \cap \{K \in \mathcal{K} | K \leq K_u\} }[/math]
- [math]\displaystyle{ R_w := R_u \cap \{K \in \mathcal{K} | K \geq K_u\} }[/math]
- Now let [math]\displaystyle{ T = (V,A) }[/math] be a multi-way search tree:
- Again, the range of [math]\displaystyle{ r }[/math] is [math]\displaystyle{ \mathcal{K} }[/math].
- For [math]\displaystyle{ v \in V\setminus\{r\} }[/math], let [math]\displaystyle{ w \in V }[/math] denote the parent node, and let [math]\displaystyle{ i }[/math] be the position of [math]\displaystyle{ (w,v) }[/math] in the ordered sequence of outgoing arcs of [math]\displaystyle{ w }[/math]. Then the range of [math]\displaystyle{ v }[/math] is
- [math]\displaystyle{ R_v := \{K \in R_w | K \leq \min S_w\} }[/math], if [math]\displaystyle{ i = 0 }[/math];
- [math]\displaystyle{ R_v := \{K \in R_w | K \geq \max S_w\} }[/math], if [math]\displaystyle{ i = |S_w| }[/math];
- [math]\displaystyle{ R_v := \{K \in R_w | K \geq a, K \leq b\} }[/math], otherwise, where [math]\displaystyle{ a,b \in S_w }[/math] are the [math]\displaystyle{ i }[/math]-th and [math]\displaystyle{ (i + 1) }[/math]-st element of [math]\displaystyle{ S_w }[/math] in the sorting order defined by comparison [math]\displaystyle{ c }[/math].
Order of Tree Nodes in a Binary Search Tree
Let [math]\displaystyle{ T = (V,A) }[/math] be a binary search tree and let [math]\displaystyle{ S \subseteq \mathcal{K} }[/math] denote the set of all key values of all nodes of [math]\displaystyle{ T }[/math].
- The left-root-right order of [math]\displaystyle{ T }[/math] is the (unique) order of [math]\displaystyle{ S }[/math] such that for every node [math]\displaystyle{ v \in V }[/math]:
- if the left arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] precede the key of [math]\displaystyle{ v }[/math];
- if the right arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] succeed to key of [math]\displaystyle{ v }[/math].
- The left-right-root order of [math]\displaystyle{ T }[/math] is the (unique) order of [math]\displaystyle{ S }[/math] such that for every node [math]\displaystyle{ v \in V }[/math]:
- if the left arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] precede the key of [math]\displaystyle{ v }[/math];
- if the right arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] precede the key of [math]\displaystyle{ v }[/math].
- The root-left-right order of [math]\displaystyle{ T }[/math] is the (unique) order of [math]\displaystyle{ S }[/math] such that for every node [math]\displaystyle{ v \in V }[/math]:
- if the left arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] succeed the key of [math]\displaystyle{ v }[/math];
- if the right arc [math]\displaystyle{ (v,w) }[/math] exists, all keys in the subtree rooted at [math]\displaystyle{ w }[/math] succeed the key of [math]\displaystyle{ v }[/math].
Remark: The sorted sequence of all keys in a binary search tree is the left-root-right order.
Immediate Predecessor and Successor
For a node [math]\displaystyle{ v }[/math] of a binary or multi-way search tree,
- the immediate predecessor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate predecessor in left-root-right order (if existing), and
- the immediate successor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate successor in left-root-right order (if existing).