Algorithms Notes – Trees

720px-binary_search_tree-svg

Example of a tree. 8 is the root. 3 and 10 are children of 8. 1, 13, 4 and 7 are leaves. 10 is an ancestor of 13. 4 is a descendant of 3. 3 is also a descendant of 3 but not a proper descendant. 10 is an ancestor of 10 but not a proper ancestor.

 

Recursive Definition of a Tree:

Def: A tree is a collection of nodes. If the collection can be empty, in which case it is usually denoted as \Lambda. Otherwise, it consists of a node r, called the root, and zero or more (sub)-trees T_{1}, T_{2}, ... , T_{k} each of whose roots are connected by a directed edge to the r.

Def: Let r be the root of a tree with one or more subtrees connected to it. The root of any sub-tree connected to r is called a child of r.

Def: Let r_{2} be the root of a sub-tree and r_{1} be the root node the subtree is connected to. r_{1} is called the parent of r_{2}.

Recursive Definition of a Tree

Def: A node in a tree that has no children is referred to as a leaf of the tree.

Def: Let n_{1} and n_{2} be two nodes in a tree that have the same parent. n_{1} is called the sibling of n_{2} and vice versa.

Def: A sequence of nodes n_{1}, n_{2}, .... , n_{k} such that n_{i} is the parent of n_{i+1} for 1 \leq i \leq k is referred to as a path.

Def: The number of edges in a path is called the length of the path.

Assertions that have beautiful proofs which you should look up:

  • There is a path of length 0 from every node to itself in a tree.
  • In a tree, there is exactly one path from the root to each node.

Def: For any node, n in a tree, the depth of n_{i} is the length of the unique path from the root of the tree to n.

  • By definition, the depth of the root is 0.

Def: Let n be any node in a tree. The height of n is the length of of the longest path from n to a leaf.

  • By definition, all leaves have a height of 0.
  • The height of a tree is basically the height of the root.

Def: Let n_{1} and n_{2} be two nodes in a tree. If a path exists between n_{1} and n_{2} then n_{1} can be called an ancestor of n_{2}. If n_{1} \neq n_{2} then n_{1} is a proper ancestor of n_{2}.

Def: Let n_{1} and n_{2} be two nodes in a tree. If a path exists between n_{1} and n_{2} then n_{2} can be called a descendant of n_{1}. If n_{1} \neq n_{2} then n_{2} is a proper descendant of n_{1}.

tree

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s