# 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).

本文作者：TwinIsland

版权声明：所有文章除特别声明外均系本人自主创作，转载及引用请注明出处

ZhuGut

TwinIsland回复@Zhuzbc

野兽后辈Nice CS173 note bruh

TwinIsland回复@野兽后辈Thanks bro