Directed Tree
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 [math]\displaystyle{ K \in S_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,v) }[/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 mutli-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 minS_w\} }[/math], if [math]\displaystyle{ i = 0 }[/math];
- [math]\displaystyle{ R_v := \{K \in R_w | K \geq maxS_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 of comparison [math]\displaystyle{ c }[/math].
Order of Tree Nodes
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 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).