Tài liệu Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 4

Faculty of Computer Science and Engineering

Department of Computer Science

1/3

DATA STRUCTURES & ALGORITHMS

Tutorial 4 Questions

AVL Tree and Heap

Part 1. AVL Tree

Required Questions

Question 1.

For each of the following key sequences determining the AVL tree obtained when the keys are inserted

one-by-one in the order given into an initially empty tree:

a) 1, 2, 3, 4, 5, 6, 7.

b) 4, 2, 1, 3, 6, 5, 7.

c) 1, 6, 7, 2, 4, 3, 5.

d) 45, 9, 2, 17, 84, 92, 71, 18, 30, 62, 55, 20, 27

Question 2.

For each of the AVL trees obtained in Question 1 determine the tree obtained when the root is withdrawn.

Question 3.

Write a global function in pseudo code to generate an AVL tree from an input list by insert elements in the

list into an initial empty AVL. Refer to Question 1 for an example.

algorithm generateAVLfromList (val list <List>)

This algorithm generate a AVL from the input list

Pre

Post the AVL is built by inserting elements in the list into an initial

empty tree one-by-one from the beginning of the list.

Return the AVL

end generateAVLfromList

Question 4.

Devise an algorithm to test whether a given binary search tree is AVL balanced.

algorithm testAVL (val tree <BSTTree>)

Pre

Post.

Return true if tree is an AVL, otherwise return false

end testAVL

Advanced Questions

Question 5.

Devise an algorithm to merge the contents of two binary search trees into one. What is the running time of

your algorithm?