Directed Tree

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