Page 161 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 6.9 Self Assessment

State whether the following statements are true or false:

1. A binary search tree is not a binary tree which may be full, and every node contains an
identifi er.
2. A dictionary is an ordered list which is required to be searched frequently, and is also
required to be updated frequently.
3. AVL Tree invented by Adelson, Velskii and Landis.
4. Implementations of AVL tree insertion rely on deleting an extra attribute – the balance
factor – to each node.

5. Identifier of any node in the right sub-tree is greater than the identifier of the root and the
left sub-tree as well as right sub-tree both are binary search trees.
Fill in the blanks:
6. A binary search tree is basically a binary tree, and therefore it can be traversed is inorder,
preorder, and .................................

7. To create a .................................. we use a procedure named insert which creates a new node
with the data value supplied as a parameter to it, and inserts into an already existing tree
whose root pointer is also passed as a parameter.

8. To ................................... from a binary search tree the method to be used depends on
whether a node to be deleted has one child, two children, or has no child.
9. To search the binary tree for a particular node, we use procedures similar to those we used
when .................................... to it.
10. A more efficient implementation of a dynamic dictionary involves considering a key to be

a sequence of .....................................
6.10 Review Questions

1. Describe binary search tree. Also explain how will you create binary search tree.
2. How will counting the number of nodes in a binary search tree? Explain
3. Describe deletion of a node with one child.
Question 4-6 are based on the following binary search tree. Answer each question independently,
using the original tree as the basis for each part.

156 LOVELY PROFESSIONAL UNIVERSITY