Tree

3.8.4 Tree

Knowledge Base > Algorithm > Data Structure

Overview

A tree is a nonempty and recursively defined structure, consisted of vertices and edges. A vertex is a object that contains either a value or a pointer to a subtree or NULL, if it is a leaf node. An edge is a connection between two vertices, and a path is a list of distinct vertices in which successive vertices are connected by edges in the tree.

Each node in the tree can have zero (then is NULL) or more child nodes or descendent nodes. A node that has a child is called the parent node . If two nodes have the same parent, they are sibling nodes. The topmost node in a tree is called the root node, and which by definition, does not have parents. The root node is where the operations on the tree commonly begin. Nodes at the bottommost level of the tree are called leaf or external nodes, and they will not have any child nodes. An internal node is any node of a tree that has child nodes. A successor of a node x is the node with the smallest key greater than x, and a predecessor is the node with the largest key smaller than x. Every node in a tree can be seen as the root node of the subtree rooted at that node.

The number of children of a node x is the tree is called the degree of x. The height of a node is the length of the longest path to a leaf from that node. The depth of a node is the length of the path to the root. The height of a tree is equal to the largest depth of any node in the tree.

The idea of tree structure can help us understand and analyze recursive program as well as advanced data structure. Usually, operations in tree follows the divide-and-conquer mechanism (of method 3.7.3.1). There are many well-known sorting and graph algorithms that are built on tree structure.

In Graph theory, there are many different kinds of tree, where their mathematical properties may be slightly different.

A Graph is a set of nodes together with a set of edges that connect pairs of distinct nodes.[2]
A Free Tree is a connected, acyclic, undirected graph. If this undirected graph is acyclic but disconnected, we call it forest.[1]
A Rooted Tree or Unordered Tree is a tree in which one of the nodes is distinguished as the root, connected to an unordered forest.[1]
A Ordered Tree is a rooted tree in which the order of the children at every node is specified. Most of the them, when we talk about a generic tree structure, we usually refer to Ordered Tree.[1]
An M-array Tree is a tree that have a specific number of children appearing in a specific order.[2]
A Binary Tree is a ordered tree (or an empty tree), which consists of disjoint subsets of a root node, a left binary subtree and a right binary subtree.

Basic Operation

void traversal():
an operation that step through all elements of the tree. There are three ways to traverse a tree, depending on the order of stepping into a child nodes.
int height(<E>):
returns the number of edges on the longest simple downward path from the given node to a leaf. the height of a leaf node is 0.
int depth(<E>):
returns the length of the path from the root to the given node.

Binary Tree

A binary tree is defined to be an ordered tree, in which each internal node must contain two children. Here are the mathematical properties of a binary tree [2]:

Property 3.8.4.1. A binary tree with n internal nodes has n + 1 external (leaf) nodes.
Proof> (Proof by Induction)
Assume the statement is true. When n = 0 (base case), the tree has 0 internal node, and 1 external node, which is the root. Thus, holds for the base case.
Next, for any tree with n internal nodes has m internal nodes in left subtree and n - m - 1 (n - m - root) internal nodes in right subtree. Hence, in inductive hypothesis n, the tree would have m + 1 external nodes in left subtree and n-m external nodes in right subtree, and adds up to be n+1 external nodes for the whole tree. Thus, proved.
Property 3.8.4.2. A binary tree with n internal nodes has 2n links: n - 1 links to internal nodes and n + 1 links to external nodes.
Proof>
For any tree with n internal nodes, there are n - 1 internal nodes that has parent node (except root node). Thus, the tree has n - 1 links among internal nodes. From the previous property, a tree with n internal nodes has n + 1 external nodes, which implies that the tree has n + 1 links from external nodes to its parents (internal nodes). This adds up to be 2n links for the whole true. Thus, proved.
Property 3.8.4.3. A complete binary tree of height h has at most 2^h+1 - 1 or
$∑ 2k 0≤k≤h$
nodes.
Proof>(Proof by Induction)
Assume the statement is true. when h = 0 ⇒ 2¹⁺⁰ - 1 = 1, is exactly the root node. Thus, holds for the base case.
Next, we create a new complete binary tree of height h + 1, called it T₃, by adding a root node and two copies of subtree with height h, called them T₁ and T₂. So, the number of nodes in the new complete binary tree is T₃ = T₁ + T₂ = 1 + 2 ⋅ (2^h+1 - 1) = 2^h+2 - 1. Thus, proved.
$| T3 | | h + 1 h T1 T2 h | | | | | | | | x x x x |$
Property 3.8.4.4. A binary tree of height h has at least 2^h nodes.
Proof>(Proof by Induction)
Assume the statement is true. When h = 0 ⇒ 2⁰ = 1, is exactly the root node. Thus, holds for the base case.
We call this incomplete binary tree of height h, T₁. Then, we create a new complete binary tree, T₃ of height (h + 1) , by adding a root and a right subtree to be the copy of T₁ to (h - 1) levels, which is a complete binary tree. We call this T₂. Finally, we add the left subtree as T₁, and the number of nodes in T₃ = 1+T₁ +T₂ = 1+2^h+(2^h-1) = 2⋅2^h = 2^(h+1). Thus, proved.
$| T3 | | h + 1 | T1 T2 | | | | | h| x x x x h - 1 | | | | | | x$
Property 3.8.4.5. For a tree of height h, there are at most 2^H nodes at height level H, where H ≤ h.
Proof>
The number of nodes at a height level can be retrieved by subtracting the minimum number of node at the height level (from property 3.8.4.3) with the maximum number of nodes (from property 3.8.4.4). That is, at height level H,H ≤ h, h is the height of the tree. Number of nodes at height level H can at most be (2^H+1 -1)-(2^H)+1 = 2⋅2^H-1-2^H+1 = 2^H. Thus, proved.
Property 3.8.4.6. There are at most ⌈⌉ nodes at height level H in an n-element heap, where H ≤ h, h is the height of tree. Proof>
We can proof this by dividing the tree structure into 3 parts:
- Number of nodes at height level H, call it N_H.
- Number of nodes above height level H is N_H - 1 (from property 3.8.4.5).
- Number of nodes of the subtrees rooted at nodes at height level H is N_H ⋅ (2^H+1 - 1). (from property 3.8.4.3)
We sum up these nodes, which is at most maximum number of nodes. That is,
$NH ⋅(2H+1 - 1)+ NH - 1 ≤ n ⇒ N ⋅2H+1 - 1 ≤ n H n ⇒ NH ≤ 2H+1---1 -n--- ⇒ NH = ⌈2H+1⌉, for large enough H$
$R x x H| ---T -- ---T--- ---T --- ---T -- |---- --- --- --- --- --- --- --- - --- --- --- -$
Property 3.8.4.7. The height of a binary tree with n internal nodes is at least lg n and at most n + 1.
Proof>
The worst case is a linear tree with only one leaf, and thus has n + 1 nodes, that is h ≤ O(n+1). The best base is a binary tree, with 2^k internal nodes at each level, except for the bottom level (they are all leaf nodes). However, the completion of nodes at the bottom level can effect the number of external nodes from 2^h-1 (the bottom level has only the left-most pair of nodes) to 2^h (a complete binary tree) external nodes, where h is the height of the tree. Thus, we can have this inequality for external nodes for a true with n internal nodes: 2^h-1 < n + 1 ≤ 2^h ⇒ h- 1 < lg (n + 1) ≤ h. Thus, lg n ≤ h ≤ n + 1.

Grammar 3.8.4.1. Backus-Naur Form for Binary Tree

<bintree>	::=	<null>
	::=	< <symbol> <number> <bintree> <bintree> >

Source Code

Here is the Binary Tree implementation, written in Scheme:

Binary Tree (Scheme)
<a href="exp/binary-tree.html">Hmm, you are using a very old browser. Click here to go directly to included content.</a>