Directed Tree: Difference between revisions

From Algowiki
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:


# The outgoing arcs of a node are labeled: at most one is labeled '''left''', at most one is labeled '''right'''.We speak of '''the''' left and '''the''' right arc of a node, respectively.
# 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>\Kappa</math> and a comparison on <math>\Kappa</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 \Kappa</math>.
# 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>\Kappa</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,v)</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:
## 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 \Kappa | 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 \Kappa | 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>\Kappa</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 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 \Kappa</math> denote the set of all key values of all nodes of <math>T</math>.
= 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 ===
'''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

  1. 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].
  2. A directed tree [math]\displaystyle{ T = (V,A) }[/math] is called binary if each node's outdegree is at most [math]\displaystyle{ 2 }[/math].
  3. 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].
  4. 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].
  5. The height level (or height, for short) of a node in a directed tree is recursivley defined as follows:
    1. The height level of the root is [math]\displaystyle{ 0 }[/math].
    2. The height level of any other node is one more than the height level of its parent.
  6. 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:

  1. 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.
  2. 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].
  3. Each node [math]\displaystyle{ v \in V }[/math] is assigned a value [math]\displaystyle{ K_v \in \mathcal{K} }[/math].
  4. For an arc [math]\displaystyle{ (v,w) \in A }[/math], the following holds:
    1. 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]).
    2. 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:

  1. 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].
  2. Each node [math]\displaystyle{ v \in V }[/math] is assigned a non-empty multiset [math]\displaystyle{ S_v \subseteq \mathcal{K} }[/math].
  3. 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.
  4. 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
    1. [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
    2. [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:

  1. First let [math]\displaystyle{ T }[/math] be a binary tree:
    1. The range of [math]\displaystyle{ r }[/math] is [math]\displaystyle{ \mathcal{K} }[/math].
    2. 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:
      1. [math]\displaystyle{ R_v := R_u \cap \{K \in \mathcal{K} | K \leq K_u\} }[/math]
      2. [math]\displaystyle{ R_w := R_u \cap \{K \in \mathcal{K} | K \geq K_u\} }[/math]
  2. Now let [math]\displaystyle{ T = (V,A) }[/math] be a multi-way search tree:
    1. Again, the range of [math]\displaystyle{ r }[/math] is [math]\displaystyle{ \mathcal{K} }[/math].
    2. 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
      1. [math]\displaystyle{ R_v := \{K \in R_w | K \leq \min S_w\} }[/math], if [math]\displaystyle{ i = 0 }[/math];
      2. [math]\displaystyle{ R_v := \{K \in R_w | K \geq \max S_w\} }[/math], if [math]\displaystyle{ i = |S_w| }[/math];
      3. [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].

  1. 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]:
    1. 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];
    2. 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].
  2. 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]:
    1. 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];
    2. 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].
  3. 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]:
    1. 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];
    2. 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,

  1. the immediate predecessor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate predecessor in left-root-right order (if existing), and
  2. the immediate successor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate successor in left-root-right order (if existing).