Directed Tree: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(7 intermediate revisions by the same user not shown)
Line 2: Line 2:


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


= Basic Definitions =
= Basic Definitions =
Line 33: 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> (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>.
Line 45: Line 46:
### <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 53: Line 54:




= 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 67: Line 68:


'''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.





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).