Directed Tree: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Definitions == # 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...") |
|||
| Line 1: | Line 1: | ||
= Definitions = | |||
# 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>. | # 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>. | ||
# A directed tree <math> T = (V,A)</math> is called '''binary''' if each node's outdegree is at most <math>2</math>. | # A directed tree <math> T = (V,A)</math> is called '''binary''' if each node's outdegree is at most <math>2</math>. | ||
| Line 8: | Line 8: | ||
## The height level of any other node is one more than the height level of its parent. | ## 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>-1</math>. For a non-empty tree, the '''height''' of the tree is the maximum height level of all of its nodes. | # 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 = | |||
= Multi-way Search Trees = | |||
= Ranges of Search Tree Nodes = | |||
= Order of Tree Nodes = | |||
= Immediate Predecessor and Successor = | |||
Revision as of 18:45, 29 September 2014
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 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.