page1
Chapter 11 Formulas / Theorems sheet
[Def] A tree is an undirected graph that is connected and has no simple circuits (cycles).
[Theorem] An undirected graph is a tree iff there is a unique simple path between any two of its vertices.
[Def] A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
[Def] The level of a vertex is its distance from to the root.
[Def] The height of a tree is the highest level of any vertex.
[Corollary] There is a unique path from the root of the tree to each vertex of the tree.
[Def] The tree is call a full m-ary tree if every internal vertex has exactly m children.
[Def] A complete m-ary tree is a full m-ary tree in which each leaf is at the same level.
[Theorem 2] A rooted tree with n vertices has n-1 edges
[Theorem 4] A full m-ary tree with
(1) n vertices has internal vertices, and leaves;
(2) i internal vertices has n = mi+1 vertices, and l = (m-1)i+1 leaves;
(3) l leaves has vertices, and internal vertices.
[Def] A rooted m-ary tree of height h is balanced if all leaves are at levels h or h-1.
[Theorem 5] There are at most mh leaves in an m-ary tree of height h, i.e. l  mh
[Corollary]
1) For a full and balanced m-ary tree of height h with l leaves, h = logml
2) For an m-ary tree of height h with l leaves, h  logml.
Binary search tree (BST), is a binary tree with keys assigned to vertices/nodes, where every vertex/node v has the following property:
length of the longest path in BST = height of the BST =
[Def] A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of the decision, is called a decision tree.
The possible solutions of the problem correspond to the paths to the leaves of this rooted tree.
[Def] prefix codes: letters are encoded in such a way that the bit string for a letter never occurs as the first part of the bit string for another letter.
[Def] Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex of G.
[Theorem 1] A simple graph is connected iff it has a spanning tree.
[Def] A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.
each key in the left subtree is less than the key at the vertex v,
each key in the right subtree is greater than the key at the vertex v.
log2(n+1) = log(n+1) if a balanced tree
n if an unbalanced tree