Directed Tree

From Algowiki
Jump to: navigation, search


Basic Definitions

  1. 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].
  2. A directed tree [math] T = (V,A)[/math] is called binary if each node's outdegree is at most [math]2[/math].
  3. 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].
  4. 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].
  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]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]-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]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]T[/math], there is a key type [math]\mathcal{K}[/math] and a comparison on [math]\mathcal{K}[/math].
  3. Each node [math]v \in V[/math] is assigned a value [math]K_v \in \mathcal{K}[/math].
  4. For an arc [math](v,w) \in A[/math], the following holds:
    1. 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]).
    2. 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

A multi-way search tree is a directed tree [math]T = (V,A)[/math] such that:

  1. Associated with [math]T[/math], there is a key type [math]\mathcal{K}[/math] and a comparison on [math]\mathcal{K}[/math].
  2. Each node [math]v \in V[/math] is assigned a non-empty multiset [math]S_v \subseteq \mathcal{K}[/math].
  3. Consider a node [math]v \in V[/math] and let [math]d_v[/math] denote [math]v[/math]'s outdegree. If [math]d_v \gt 0[/math], it is [math]|S_v| = d_v - 1[/math]; otherwise, [math]|S_v|[/math] may be arbitrary.
  4. 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
    1. [math]K \geq K'[/math] for at least [math]i[/math] elements [math]K'[/math] of [math]S_v[/math] and
    2. [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

Let [math]T = (V,A)[/math] be a search tree with root [math]r[/math]. The range of a node is defined recursively:

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

  1. 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]:
    1. if the left arc [math](v,w)[/math] exists, all keys in the subtree rooted at [math]w[/math] precede the key of [math]v[/math];
    2. if the right arc [math](v,w)[/math] exists, all keys in the subtree rooted at [math]w[/math] succeed to key of [math]v[/math].
  2. The left-right-root order of [math]T[/math] is the (unique) order of [math]S[/math] such that for every node [math]v \in V[/math]:
    1. if the left arc [math](v,w)[/math] exists, all keys in the subtree rooted at [math]w[/math] precede the key of [math]v[/math];
    2. if the right arc [math](v,w)[/math] exists, all keys in the subtree rooted at [math]w[/math] precede the key of [math]v[/math].
  3. The root-left-right order of [math]T[/math] is the (unique) order of [math]S[/math] such that for every node [math]v \in V[/math]:
    1. if the left arc [math](v,w)[/math] exists, all keys in the subtree rooted at [math]w[/math] succeed the key of [math]v[/math];
    2. 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 binary search tree is the left-root-right order.


Immediate Predecessor and Successor

For a node [math]v[/math] of a binary or multi-way search tree,

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