TREE and GRAPH definitions and observations:
A Graph is defined as the union of a set of nodes and a set of edges. This is clearly a general structure with few restrictions.
A Tree on the other hand, is a graph with a specific set of restrictions. A tree is an SRDAG of indegree 1. (Singly Rooted, Directed, Acyclic Graph)
Algorithms that operate on either structure are usually recursive and tend to be short. The tree algorithms also tend to run in log N or N log N time, but graph algorithms are often slower, and sometimes much slower. Graph algorithms, particularly those involving searching and optimization, often run in quadratic time and sometimes in cubic or exponentialtime.
The tree restrictions permit a few fundamental observations concerning the tree structure:
- A tree has only one entry point, the root. Graphs generally do not have a predefined entry point.
- There is only one direct path from the root to any node in the tree. There are usually multiple paths to most of the nodes in a graph.
- A “well balanced” tree of degree D, containing N nodes will have height approximately logD N.
TreeSRDAG of indegree 1 (Singly Rooted, Directed, Acyclic Graph)
Graph N E (a set of nodes/vertices (N) and a set of edges (E) representing paths between nodes)
NodeLike point in geometry, a node represents a place in a graph (or a tree)
Edge a path between two nodesOR a pair of nodes
Edges come in two flavors, directed or undirected. Graphs may be directed, (sometimes called digraphs), or undirected. Trees are always directed (see the definition).
Undirected Edgea bi-directional path between two nodes
OR an unordered pair of nodes
Directed Edgea unidirectional path between two nodes
OR an ordered pair of nodes
In an undirected graph:
Degree of a nodethe number of edges touching the node
Degree of an undirected graphthe maximum degree found in the graph
In a directed graph:
Indegree of a node - the number of directed edges terminating at the node
Outdegree of a node - the number of directed edges leaving the node
Indegree of a directed graph - the maximum indegree found in the digraph
A tree is restricted to indegree 1 so that the following is not a tree. We want there to be only one valid path from the root to any particular node:
Outdegree of a directed graph- the maximum outdegree found in the digraph
Acyclic graph - a directed graph in which no path exists allowing a return to the starting node on the path
Degree of a tree - the maximum outdegree found in the tree
As a tree must have indegree 1, the term degree implicitly refers to the outdegree of the tree. The vast majority of trees are degree 2, called binary trees. Their advantage is that a single test at a node is generally sufficient to determine which edge is to be taken next. Trees with more than two descendants per node generally require multiple tests at each node.
NODE related terms: The set of nodes in any directed graph or tree can be divided into three distinct subsets: ROOTs, LEAVES, and INTERIOR NODEs where: N = R L I
Roota node with indegree 0
Leafa node with outdegree 0
Interior Nodea node with indegree and outdegree greater than 0
TREE related terms – in addition to digraph terms, tree terminology borrows freely from genealogical tree terms (ancestor, descendant, etc) and actual tree terms (root, leaf, etc)
Level of a nodethe distance from the root to the node measured in edges
Height of a treethe longest path from the root to a leaf measured in edges. OR the maximum level found in a tree
Ancestor / Parent / Father / Mother of a node self explanatory
Descendant / Child / Son / Daughter of a node self explanatory
These terms can also have straightforward modifiers such as “Direct Descendant”, “Immediate Ancestor”, and “Indirect Parent”.
Sibling of a nodeIn general, nodes that have the same ancestor are siblings. In some cases, all nodes on the same level may be considered siblings.
Observations about trees:
Maximum height of any tree containing N nodes is N-1
(See degenerate tree)
Minimum height of a binary tree containing N nodes is log 2 N
Minimum height of a degree D tree containing N nodes is
approximately log D N
Maximum number of nodes at level L in a binary tree is2L
Maximum number of nodes at level L in a tree of degree D is DL
Total number of nodes in a full tree of height H and degree D is
Dk (k = 0,, H)
For example, a full tree of degree 4 and height 3 will have 1 node on level 0, 4 nodes on level 1, and 16 nodes on level 2, and 64 nodes on level 3, for a total of 85 nodes.
Total number of nodes in a full binary tree of height H is2 H+1 –1
The math works better for binary trees as the sum will always be one less than the next power of 2. For example a full binary tree of height 4 will have 1, then 2, then 4, then 8, then 16 nodes for a total of 31. 31 is one less than 32, which is 25.
Specially named tree forms:
Full tree a tree in which all the leaves are on the same level and that level is full.
Complete treethe same as a full tree except the final level is not full and all leaves on that level are as far to the left as possible.
Almost Complete tree the same as a complete tree except that the leaves on the last level may not be as far to the left as possible.
Degenerate tree – a tree with no branching. The outdegree is never greater than 1. A degenerate tree containing N nodes will have height N-1.
Reasonably well-balanced tree There are a number of different definitions. The most well known is the height balanced binary search tree (or AVL tree). For right now, a reasonably well-balanced degree D tree containing N nodes has height approximately log D N. Notice that the tree below has 7 nodes, so the minimum height for the tree is 2, and this tree has height 3. That is close enough in almost all situations.
In addition to building and maintaining trees, there are two other basic operations on trees: search for a particular value, and traverse the tree by visiting every node in the tree once. Both of these operations may also be performed on graphs. In addition, a tour of a graph is also sometimes needed. A tour will visit every node at least once and will return to the starting node.