Trees

Question 1

What is a ‘Tree’ and what is the main benefit of storing data in a tree?

Answer 1

Trees: A hierarchical/ nested structure.

Storing data in trees allows us to speed up O(N) algorithms to O(lgN). This is because if the tree is fully balanced we can eliminate half of it.

Question 2

Describe the Tree ADT and its basic operations.

Answer 2

Elements of a Tree:
r: root node
Non-Empty subtrees (T1, T2, …, Tn) each connected by a ‘directed edge’ from r.

Operations:
get(), size(), set(), add(), remove(), find()

Question 3

Tree Terminology:

Answer 3

Root: The top of the tree.

Internal Nodes: Nodes that have both a parent and a child.

Child: Bottom nodes, that are only connected to a parent.

Siblings: Nodes that share a common parent.

Question 4

Define the ‘Depth’ of a tree.

Answer 4

The total number of edges from the root node to the leaf node in the longest path.

Root Node Height : 0

Question 5

What is a ‘Binary Tree’?

Answer 5

A k-array (k=2) data structure where every node has at most two children.

Question 6

What is the typical runtime of a binary tree?

Answer 6

lg N

Question 7

What is a ‘Full’ binary tree?

Answer 7

A tree in which every node is a leaf or has two children

Question 8

What is a ‘Complete’ binary tree?

Answer 8

When all levels (except the last) are completely filled and every node is as far left as possible.

Question 9

What is the ‘Diameter’ of a binary tree?

Answer 9

The number of nodes on the longest path between any two nodes.

Question 10

What is the ‘Width’ of a binary tree?

Answer 10

The number of nodes on the level w/ the most node.

Question 11

What are the three most common types of tree traversals?

Answer 11

Preorder: Root L R
Inorder: L Root R
Postorder: L R Root

Question 12

What is a ‘Binary Search Tree” (BST) and what is its main advantage?

Answer 12

A binary tree where for each node on the tree:

1. All Nodes in the left subtree contain nodes that are < than the root.
2. All Nodes in the right subtree contain nodes that are > than the root.

Its main advantage is that it can be used as a tree map

Question 13

Describe the BST data type, its purpose, and its operations.

Answer 13

Its keys are unique, but its values are not.

Goal: Reduce finding an item to O(ln N)

Operations: insert(x), contains(x), findMin(), findMax(), remove(x).

Question 14

What is an ‘AVL Tree’?

Answer 14

A BST in which the following balance condition holds after each operation.

For all nodes, the height of the left subtree and the right subtree differs by at most 1.

Question 15

What is the height of an AVL Tree?

Answer 15

At most 0(lnN).

Question 16

What are the two types of AVL tree imbalances, and their corresponding rotations?

Answer 16

Outside Imbalance:
rotateWithLeftChild:
An insertion into the left subtree of the left child.

rotateWithRightChild:
An insertion into the right subtree of the right child

Inside Imbalance:

doubleWithLeftChild: LR
An insertion into the right subtree of the left child.

doubleWithRightChild: RL
An insertion into the left subtree of the right child.

Question 17

What is ‘Structural Induction Over Trees’ and what are its two forms?

Answer 17

Proof by structural induction is used to prove properties over trees.

Its two most common forms are:
1. Structural Induction over the height of a tree
@. Structural induction over the number of nodes in a tree

Question 18

What is the poof template for structural induction over trees?

Answer 18

Base Case: The property holds for a single node.

Inductive Step:
1. Assume the property holds for each possible subtree by proving K.
2. Show that it holds for all trees by combining the subtree w/ a parent. K+1

Question 19

Describe structural induction over ‘height’ proof?

Answer 19

Goal: Show a ‘perfect’ BT of height h has 2^(h+1) - 1nodes.

Base Case: A tree of height 0 has 2^(0+1) - 1 = 1 node.

Inductive Step:
1. Assume that a perfect binary tree of height k has 2(k+1) -1 nodes.

2. Show that any perfect BT of height K+1 has 2^(k+1)-1 nodes with a recursive construction.
3. Therefore a Binary tree…

Notes:

A perfect tree is an upper bound.

A BT of n nodes has at least height ln(n+1)-1.

Question 20

Describe structural induction over the ‘number of nodes’ in a tree.

Answer 20

Goal: Show a ‘full’ BT of N nodes has (N+1)/2 leaves.

Base Case: A tree w/ 1 node has (1+1)/2 = 1 leaf.

Inductive Step:
1. Assume a full tree 1/K nodes has (K+1)/2 leaves.
2. In a Full BT w/ K+2 noes, there must be at least 1 internal node w/ 2 leaves as children
- Removing these children yields a tree w/ K nodes
3. The new tree of k+2 nodes has [(k+2) + 1]/2 childrn