Q. Consider a weight balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as

View solution

Q. What does the below definations convey?

i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

View solution

Q. Elements in a tree can be indexed by its position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency.

View solution

Q. What is the special property of red-black trees and what root should always be?

View solution

Q. Why do we impose restrictions like
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black

View solution

Q. Cosider the below formations of red-black tree. All the below formations are incorrect for it to be a redblack tree. Then what may be the correct order?

View solution

Q. What are the operations that could be performed in O(logn) time complexity by red-black tree?

View solution

Q. Which of the following is an application of Red-black trees and why?

View solution

Q. When it would be optimal to prefer Red-black trees over AVL trees?

View solution

Q. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

View solution

Q. How can you save memory when storing color information in Red-Black tree?

View solution

Q. When to choose Red-Black tree, AVL tree and B-trees?

View solution

Q. After the insertion operation, is the resultant tree a splay tee?

View solution

Q. What is inefficient with the below threaded binary tree picture?

View solution

Q. If we implement heap as min-heap , deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the root at start.

View solution

Q. If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree . What value will be at leaf nodes of the right subtree of the heap.

View solution

Q. Binary trees can have how many children?

View solution

Q. Disadvantage of using array representation for binary trees is?

View solution

Q. What must be the ideal size of array if the height of tree is ‘l’?

View solution

Q. What are the children for node ‘w’ of a complete-binary tree in an array representation?

View solution