Lab 13 -- Trees

Exercise 1

Observe the following trees and answer the indicated questions related to each tree.

a) Answer the following as related to Tree1		b) Answer the following as related to Tree2
Height =		Height =
Root Node =		Root Node =
Children of R =		Degree of node D =
Parent of K =		Level of node E =
c) Fill in blanks
Which trees are binary trees?
Which trees are full binary trees?
Which trees are binary search trees?
Which trees are complete?

Exercise 2

Fill in the blanks.

a) A full binary tree of height = 1 will have 20 =		node/s.
b) A full binary tree of height = 2 will have 21 + 20 =		nodes.
c) A full binary tree of height = 3 will have 22 + 21 + 20 =		nodes.
d) A full binary tree of height = 4 will have		nodes.
e) A full binary tree of height = 5 will have		nodes.
f) A full binary tree of height = k will have		nodes.
g) How many leaves are there in a full binary tree of height 5?
h) How many leaves are there in a full binary tree of height k?

Exercise 3

Approximately how many comparisons will be required, in the worst case, to locate a value in a relatively balanced BST with 1000 nodes? Give a numeric answer.
1,000,000 nodes?

Exercise 4

{ Script }

Exercise 5

Why is the tree in (b) not an AVL-tree? Be specific.

Exercise 6

Imagine that the node containing 60 has just been inserted in the tree below. Note that before the 60 was inserted it was an AVL-tree. Look at the nodes along the path from the root to where the 60 was inserted : 95, 75, 55, 65.
a) Of the trees rooted at these four nodes, which one(s) is(are) not exactly balanced?

b) Which non-balanced node on this path is "closest" to where the 60 was inserted?

c) On which side (left or right) of 75 did the 60 go?

Exercise 7

Give the right rotation at 75 to rebalance the tree below after 45 is inserted. Think about where the 65 should go after the rotation. Redraw the tree, on the printed answer sheet, after the insertion and right rotation.

Before	After