Data Structures and Algorithm-Unit 3

P. A. COLLEGE OF ENGINEERING AND TECHNOLOGY
POLLACHI, COIMBATORE – 642 002.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

ME – DEGREE COMPUTER SCIENCE AND ENGINEERING

DATA STRUCTURES AND ALGORITHMS_Unit3

Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.

UNIT III – SEARCH STRUCTERS

1. What is binary search?

Binary search is a remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the arrays middle element A[m]. if they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if K < A[m] and the second half if K > A[m].

                                        K  

A[0]………A[m-1] A[m] A[m+1]………A[n-1]

                      search here if K<A[m]                           search here if K>A[m]

2. What is a binary tree extension and what is its use?

 The binary tree extension can be drawn by replacing the empty subtrees by special nodes in a binary tree. The extra nodes shown as little squares are called external & the original nodes shown as little circles called internal. The extension of a empty binary tree is a single external node. The binary tree extension helps in analysis of tree algorithms.

3. What are the classic traversals of a binary tree?

 The classic traversals are as follows

i. Preorder traversal: the root is visited before left & right subtrees 

ii. Inorder traversal: the root is visited after visiting left subtree and before visiting right subtree

iii. Postorder traversal: the root is visited after visiting the left and right subtrees

4. Mention an algorithm to find out the height of a binary tree.

ALGORITHM

Height(T) //Compares recursively the height of a binary tree

//Input: A binary tree T //Output: The height of T

            if T = Φ

return –1

else

return max{Height(TL),

 Height(TR)}+1

5. What are binary search trees and what is it mainly used for?

 Binary search trees is one of the principal data structures for implementing dictionaries. It is a binary tree whose nodes contain elements of a set of orderable items, one element per node, so that all elements in the left subtree are smaller than the element in the subtree’s root and all elements in the right subtree are greater than it.

6. Define AVL trees and who was it invented by?

An AVL tree is a binary search tree in which the balance factor of every node, which is defined as the difference between the heights of the node’s left and right subtrees, is either 0 or +1 or –1. the height of an empty subtree is defined as –1. AVL trees were invented in 1962 by two Russian scientists, G.M.Adelson-Velsky and E.M.Landis, after whom the data struture is named. 

7.  Define AVL Tree.

An empty tree is height balanced. If T is a non-empty binary tree with TL and

TR as its left and right subtrees, then T is height balanced if

i) TL and TR are height balanced and

ii) │hL - hR│≤ 1

Where hL and hR are the heights of TL and TR respectively.

8. What are the various transformation performed in AVL tree?  

                   1.single rotation   - single L rotation  - single R rotation 

                   2.double rotation  -LR rotation          -RL rotation

9. What are the categories of AVL rotations?

Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±2. Then the rotations can be classified into the following four categories:

Left-Left: The newly inserted node is in the left subtree of the left child of A.

Right-Right: The newly inserted node is in the right subtree of the right child of  A.

Left-Right: The newly inserted node is in the right subtree of the left child of A.

Right-Left: The newly inserted node is in the left subtree of the right child of A.

10. What do you mean by balance factor of a node in AVL tree?

The height of left subtree minus height of right subtree is called balance factor of a node in AVL tree.The balance factor may be either 0 or +1 or -1.The height of an empty tree is -1.

11. Write about the efficiency of AVL trees?

As with any search tree , the critical characteristic is the tree’s height. The tree’s height is bounded above and below by logarithmic functions. The height ‘h’ of any AVL tree with ‘n’ nodes satisfies the inequalities

log2 n ≤ h < 1.4405 log2(n+2) – 1.3277

The inequalities imply that the operations of searching and insertion are θ(log n) in the worst case. The operation of key deletion in an AVL tree is more difficult than insertion, but it turns out to have the same efficiency class as insertion i.e., logarithmic

12. What is the minimum number of nodes in an AVL tree of height h?

The minimum number of nodes S(h), in an AVL tree of height h is given

by S(h)=S(h-1)+S(h-2)+1. For h=0, S(h)=1.

13. What are 2-3 trees and who invented them?

A 2-3 tree is a tree that can have nodes of two kinds:2-nodes and 3-nodes. A 2-node contains a single key K and has two children, the left child serves as the root of a subtree whose keys are less than K and the right child serves as the root of a subtree with keys greater than K.  A 3-node contains two ordered keys K1 & K2 (K1<K2). The leftmost child serves as the root of a subtree with keys less than K1, the middle child serves as the root of a subtree with keys between K1 & K2 and the rightmost child serves as the root of a subtree with keys greater than K2. The last requirement of 2-3 trees is that all its leaves must be on the same level, a 2-3 tree is always height balanced. 2-3 trees were introduced by John Hopcroft in 1970.

14. What do you mean by 2-3-4 tree?

A B-tree of order 4 is called 2-3-4 tree. A B-tree of order 4 is a tree that is not

binary with the following structural properties:

• The root is either a leaf or has between 2 and 4 children.

• All non-leaf nodes (except the root) have between 2 and 4 children.

• All leaves are at the same depth.

14. Define B-tree of order M.

A B-tree of order M is a tree that is not binary with the following structural

properties:

• The root is either a leaf or has between 2 and M children.

• All non-leaf nodes (except the root) have between ┌M/2┐ and M children.

• All leaves are at the same depth.

15. What are the applications of B-tree?

• Database implementation

• Indexing on non primary key fields

 

16. Definition of a red-black tree

A red-black tree is a binary search tree which has the following red-black properties:

Every node is either red or black. Every leaf (NULL) is black. If a node is red, then both its children are black. Every simple path from a node to a descendant leaf contains the same number of black nodes.

	A basic red-black tree
	Basic red-black tree with the sentinel nodes added. Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node. They are the NULL black nodes of property 2.

17. Define splay tree.

A splay tree is a binary search tree in which restructuring is done using a scheme called splay. The splay is a heuristic method which moves a given vertex v to the root of the splay tree using a sequence of rotations.

18. What is the idea behind splaying?

Splaying reduces the total accessing time if the most frequently accessed node is moved towards the root. It does not require to maintain any information regarding the height or balance factor and hence saves space and simplifies the code to some extent.

19. List the types of rotations available in Splay tree.

Let us assume that the splay is performed at vertex v, whose parent and

grandparent are p and g respectively. Then, the three rotations are named as:

i. Zig: If p is the root and v is the left child of p, then left-left rotation at p would

suffice. This case always terminates the splay as v reaches the root after this

rotation.

ii. Zig-Zig: If p is not the root, p is the left child and v is also a left child, then a left-

left rotation at g followed by a left-left rotation at p, brings v as an ancestor of g

as well as p.

iii. Zig-Zag: If p is not the root, p is the left child and v is a right child, perform a

left-right rotation at g and bring v as an ancestor of p as well as g.

20. Define brute force string matching.

The brute force string matching has a given string of n characters called the text and a string of m characters called the pattern, find a substring of the text that matches the pattern. And find the index I of the leftmost character of the first matching substring in the text.

21. What are the advantages of brute force technique?

The various advantages of brute force technique are

i. Brute force applicable to a very wide variety of problems. It is used for many elementary but important algorithmic tasks 

ii.For some important problems this approach yields reasonable algorithms of at least some practical value with no limitation on instance size

iii.The expense to design a more efficient algorithm may be unjustifiable if only a few instances of problems need to be solved and a brute force algorithm can solve those instances with acceptable speed

iv. Even if inefficient in general it can still be used for solving small-size instances of a problem

v. It can serve as a yardstick with which to judge more efficient alternatives for solving a problem

22. What are the properties of binary heap?

i) Structure Property

ii) Heap Order Property