Trees

a tree is a undirected graph with a special node called the root, in which every node is connected to the root by exactly one path

parent: related to a neighbor nodes in a graph, the node nearest the root is called the parent

child: other nodes except parent

leaf node: node with no children, or it will be internal node

height: maximum level of any of its nodes

ancestor: g is ancestor of x if x can get to g by following zero or more parent links. In this case, x is descendent

• x is ancestor/descendent of itself
• all an/de expect itself are called proper an/de

subtree: an arbitrary node in the tree, its subtree is a (root) + a's descendent and all the edges linking these nodes.

M-ary Tree

An m-ary tree allows each node to have up to m children

full m-ary tree: each node has either zero or m nodes

complete m-ary tree: all leaves are at the same height

A full m-ary tree with i internal nodes has mi + 1 nodes total

nodes = parent + not parent

node with no parent = 1

node with parent: mi

total = mi + 1

Height and number of nodes

when the height of the binary tree is h, the nodes sum is equal to

$$ \sum^{h}_{L=0}2^L $$

which has the close form:

$$ 2^{h+1}-1 $$

Therefore, the height of the tree with n node is

$$ log_2n $$

Grammar

terminals: symbols that are allowed to appear on the leaf nodes.

start symbols: allowed to appear on the root node

Recursion trees

we can visualizing the behavior of certain recursive definitions by using tree

S(1) = c

S(n) = 2S(n/2) + n, ∀n ≥ 2 (n a power of 2)

• top node represent S(n)
• two node represent two copies of the computation of S(n/2)
• The value of S(n) is then the sum of the values in all the nodes in the recursion tree

Tree induction

• prove by induction of height
• it’s tempting to think that if the full tree has height h, the child subtrees must have height h − 1

Let T be a binary tree, with height h and n nodes. Then $n ≤ 2^{h+1} − 1.$

Base case: the tree consisting of a single node with no edges. It has h = 0 and n =1. then, we work out that $2^{h+1}-1=2^1-1=1=n$

Induction: Suppose that the claim is true for all binary trees of height < h. Let T be a binary tree of height h (h > 0).

Case 1: T consists of a root plus one subtree X. X has height $h − 1$. So X contains at most $2^h − 1$ nodes. T only contains one more node (its root), so this means T contains at most $2^h$ nodes, which is less than $2^{h+1} − 1$.

Case 2: T consists of a root plus two subtrees X and Y . X and Y have heights p and q, both of which have to be less than h, i.e. ≤ h − 1. X contains at most $2^{p+1 }− 1$ nodes and Y contains at most $2^{q+1} − 1$ nodes, by the inductive hypothesis. But, since p and q are less than h, this means that X and Y each contain ≤ $2^h − 1$ nodes.

So the total number of nodes in T is the number of nodes in X plus the number of nodes in Y plus one (the new root node). So the total number of nodes in T is $≤ 2^{h+1} − 1$, which is what we needed to show

Heap property

Refer to Howdy's lesson

for every node X in the tree, the value in X is at least as big as the value in each of X’s children.

If a tree has the heap property, then the value in the root of the tree is at least as large as the value in any node of the tree

Base: h = 0. A tree of height zero contains only one node, so obviously the largest value in the tree lives in the root

Induction: Suppose that the claim is true for all full binary trees of height < h. Let T be a tree of height h (h > 0) which has the heap property. Since T is a full binary tree, its root r has two children p and q. Suppose that X is the subtree rooted at p and Y is the subtree rooted at q.

Both X and Y have height < h. Moreover, notice that X and Y must have the heap property, because they are subtrees of T and the heap property is a purely local constraint on node values.

Suppose that x is any node of T. We need to show that v(r) ≥ v(x). There are three cases:

Case 1: x = r. This is obvious.
Case 2: x is any node in the subtree X. Since X has the heap
property and height ≤ h, v(p) ≥ v(x) by the inductive hypothesis.
But we know that v(r) ≥ v(p) because T has the heap property.
So v(r) ≥ v(x).
Case 3: x is any node in the subtree Y . Similar to case 2.
So, for any node x in T, v(r) ≥ v(x).