Data Structures - Programming Assignment 7

1. Show the results of inserting 30, 28, 34, 36, 44, 32, 38, 40 into an initially empty AVL tree. Draw the tree after each step.                        [10]

Insert (30)

Insert (28)

Insert (34)

 

Insert (36)

Insert (44)

Here tree is not remain balance at node ‘34’ so we do left rotation

Insert (32)

 

Here tree is again become unbalance at node ‘30’ so we do left-right rotation.

 

Insert (38)

Here the tree is become unbalance at node ‘36’ so we again do right-left rotation.

 

 

                          

Inserting (40)

 

                                                              

2. How many levels would a fully balanced BST need to represent an English dictionary containing 15,000 words?                                                [5]

Answer:

The total no. of node in the tree = 15,000

The formula to calculate the total no. of level of a tree is:

 d = log₂ (n+1) -1       where n = total no. of node in a tree.

So by putting the value of n= 15,000

= log₂ (15,000 + 1) -1

= log₂ (15,001) -1

= log (15,001)

   ---------------  - 1

        log 2

= 13.872771056 -1

=12.872771056

= 13 levels approximately.

3. Given input {23, 46, 12, 59, 78, 87, 2, 3} and a hash function h(x)=x mod 11,show the resulting:

·         Chaining hash table.

·         Open addressing hash table using linear probing.

·         Open addressing hash table using quadratic probing.

Chaining hash table.

1
2
3
4
5
6
7
8
9
10

Linear Probing:

1
2
3
4
5
6
7
8
9
10

23
46
12
59
78
2
3
87

Quadratic probing:

1
2
3
4
5
6
7
10
11
12

23
46
2
59
12
3
78
87