Directed Tree

Jump to: navigation, search

Basic Definitions

1. A directed tree is a directed graph $T = (V,A)$ with a designated node $r \in V$, the root, such that for each node $v \in V$, there is exactly one path from $r$ to $v$ in $T$.
2. A directed tree $T = (V,A)$ is called binary if each node's outdegree is at most $2$.
3. The subtree of $T$ rooted at $v \in V$ is the subgraph induced by all nodes that are reachable from $v$ via paths in $T$ (including $v$). In particular, $T$ is the subtree of $T$ rooted at $r$.
4. For an arc $(v,w)$ in a directed tree, $w$ is a child of $v$, and $v$ is the (unique) parent of $w$.
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 $0$.
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 $-1$. 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 $T = (V,A)$ 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 $T$, there is a key type $\mathcal{K}$ and a comparison on $\mathcal{K}$.
3. Each node $v \in V$ is assigned a value $K_v \in \mathcal{K}$.
4. For an arc $(v,w) \in A$, the following holds:
1. If $(v,w)$ is the left arc of $v$, it is $K \leq K_v$ for all keys $K$ in the subtree rooted at $w$ (incl. $K_w$).
2. If $(v,w)$ is the right arc of $v$, it is $K \geq K_v$ for all keys $K$ in the subtree rooted at $w$ (incl. $K_w$).

Multi-way Search Trees

A multi-way search tree is a directed tree $T = (V,A)$ such that:

1. Associated with $T$, there is a key type $\mathcal{K}$ and a comparison on $\mathcal{K}$.
2. Each node $v \in V$ is assigned a non-empty multiset $S_v \subseteq \mathcal{K}$.
3. Consider a node $v \in V$ and let $d_v$ denote $v$'s outdegree. If $d_v \gt 0$, it is $|S_v| = d_v - 1$; otherwise, $|S_v|$ may be arbitrary.
4. For $v \in V$, the outgoing arcs of $v$ are ordered and assigned positions numbered $0,\dots,|S_v|$. For the outgoing arc $(v,w) \in A$ at position $i \in \{0,\dots,|S_v|\}$ and any key $K$in the subtree rooted at $w$ (incl. $w$), it is
1. $K \geq K'$ for at least $i$ elements $K'$ of $S_v$ and
2. $K \leq K'$ for at least $|S_v| - i$ elements $K'$ of $S_v$.

Ranges of Search Tree Nodes

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

1. First let $T$ be a binary tree:
1. The range of $r$ is $\mathcal{K}$.
2. Let $u \in V$. If existing, let $(u,v)$ and $(u,w)$ denote the left and right arc of $u$, respectively. The ranges $R_v$ of $v$ and $R_w$ of $w$ are defined as follows:
1. $R_v := R_u \cap \{K \in \mathcal{K} | K \leq K_u\}$
2. $R_w := R_u \cap \{K \in \mathcal{K} | K \geq K_u\}$
2. Now let $T = (V,A)$ be a multi-way search tree:
1. Again, the range of $r$ is $\mathcal{K}$.
2. For $v \in V\setminus\{r\}$, let $w \in V$ denote the parent node, and let $i$ be the position of $(w,v)$ in the ordered sequence of outgoing arcs of $w$. Then the range of $v$ is
1. $R_v := \{K \in R_w | K \leq \min S_w\}$, if $i = 0$;
2. $R_v := \{K \in R_w | K \geq \max S_w\}$, if $i = |S_w|$;
3. $R_v := \{K \in R_w | K \geq a, K \leq b\}$, otherwise, where $a,b \in S_w$ are the $i$-th and $(i + 1)$-st element of $S_w$ in the sorting order defined by comparison $c$.

Order of Tree Nodes in a Binary Search Tree

Let $T = (V,A)$ be a binary search tree and let $S \subseteq \mathcal{K}$ denote the set of all key values of all nodes of $T$.

1. The left-root-right order of $T$ is the (unique) order of $S$ such that for every node $v \in V$:
1. if the left arc $(v,w)$ exists, all keys in the subtree rooted at $w$ precede the key of $v$;
2. if the right arc $(v,w)$ exists, all keys in the subtree rooted at $w$ succeed to key of $v$.
2. The left-right-root order of $T$ is the (unique) order of $S$ such that for every node $v \in V$:
1. if the left arc $(v,w)$ exists, all keys in the subtree rooted at $w$ precede the key of $v$;
2. if the right arc $(v,w)$ exists, all keys in the subtree rooted at $w$ precede the key of $v$.
3. The root-left-right order of $T$ is the (unique) order of $S$ such that for every node $v \in V$:
1. if the left arc $(v,w)$ exists, all keys in the subtree rooted at $w$ succeed the key of $v$;
2. if the right arc $(v,w)$ exists, all keys in the subtree rooted at $w$ succeed the key of $v$.

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 $v$ of a binary or multi-way search tree,

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