KEMBAR78
M.Tech CS Test: AVL & BST Algorithms | PDF | Algorithms | Computer Data
Scribd
Upload
68 views1 page

M.Tech CS Test: AVL & BST Algorithms

This document contains a class test for a Data Structures course with 5 questions. Question 1 asks for an algorithm to find the 3rd smallest element in a binary min-heap in constant time. Question 2 defines the AVL property of a node and asks about the height of an AVL tree. Question 3 provides an in-order and pre-order traversal of a binary search tree and asks several questions about it. Question 4 asks for pseudocode for a range query on a binary search tree where each node stores the size of its subtree. Question 5 asks for a routine to perform a single right rotation at a node in a binary search tree and adjust all pointers.

Uploaded by

yuzurihainori10121996
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
68 views1 page

M.Tech CS Test: AVL & BST Algorithms

This document contains a class test for a Data Structures course with 5 questions. Question 1 asks for an algorithm to find the 3rd smallest element in a binary min-heap in constant time. Question 2 defines the AVL property of a node and asks about the height of an AVL tree. Question 3 provides an in-order and pre-order traversal of a binary search tree and asks several questions about it. Question 4 asks for pseudocode for a range query on a binary search tree where each node stores the size of its subtree. Question 5 asks for a routine to perform a single right rotation at a node in a binary search tree and adjust all pointers.

Uploaded by

yuzurihainori10121996
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

INDIAN STATISTICAL INSTITUTE

CLASS TEST
M.TECH(CS) IYEAR
DATA STRUCTURES

Date: 14.11.2022 Maximum marks: 40 Duration: 1hour.

1. Give an algorithm to find the 3rd smallest clement in a binary min-hcap in constant
time 3)
2. State what you mean by AVL property ofa node. Show that an
AVL tree withn nodes should
have O(lg n) height.
2+5=7]
3. Consider a binary search tree whOse nodes are labeled by A, B, C, D, E, F,G, H.
and pre-order travaersal of the tree yeilds the following sequence of
The in-order
nodes:
In-order: H, D, I, B, E, J, A, F, C, G, K
Pre-order: A, B, D, H, I, E, J,C, F, G, K
Answer the following questions. You need not provide explanations.
(a) Draw the tree.
(b) Assume that the tree is a valid binary search tree. What is the successor of node A.
(c) Is the tree an AVL tree?
(d) Re-draw the tree after deleting node C.
(e) Is this new tree an AVL tree?

5+1+1 +2 +l= 10)


4. Consider a binary search tree, in which in addition to the standard fields (data, left and right)
cach node has an integer field called size, which storcs the number of clements in the subtree
rooted at this node. In a range query we are given two key values T], T2, Where z; < T2x
and wish to return a count of the number of nodes in the tree whose key value zsatisfies
Z <r< T), Give pseudocode for this operation, and briefly explain how your algorithm
works. Your algorithmshould run in O(h) time, where his the height of the tree.
|10)
5. Consider a binary search tree implementat ion where each node have a key, a parent pointer
and left and right child pointers. Given a node X in the tree, write a routine which does
single right rotation at X. Adjust all pointers (including the parent pointers) appropriately.
|10)
(8 -12) (21)

You might also like