Thursday, 16 November 2017

Non-Linear Data Structure

What do you mean by binary search tree. Why it is preferred over sorted linear array and linked list?

Binary search tree is a binary tree in which key values of the left sub trees are lesser than the root value and the key values of the right sub tree are always greater than the root value. In linear array or linked list the values are arranged in the form of increasing or decreasing order. If we want to access any element means, we have to traverse the entire list. But if we use binary search tree, the element to be accessed is greater or smaller than the root element means we can traverse either the right or left sub tree and can access the element irrespective of searching the entire tree.

What do you mean by a complete binary tree?
A binary tree is known as a complete binary tree only if all of its levels, except possibly the last level have the maximum number of nodes. 

What do you mean by an AVL trees?
An AVL tree is a binary search tree with a balancing condition to balance the height of left sub-tree and height of right sub-tree. For every node in the tree the height of the left and right sub-trees can differ at most by 1.The height of an empty tree is defined to be -1.It ensures that the depth of the tree is O(log N)


Thanks 
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput