What is a weight balanced tree?
a) A binary tree that stores the sizes of subtrees in nodes
b) A binary tree with an additional attribute of weight
c) A height balanced binary tree
d) A normal binary tree
Explanation: Unlike AVL and redblack trees which uses height and color as book keeping information, weight balanced trees use the size of subtrees.
What are the applications of weight balanced tree?
a) dynamic sets, dictionaries, sequences, maps
b) heaps
c) sorting
d) storing strings
Explanation: They are a type of self-balancing trees which are mostly used in storing key-value pairs, which is mostly used in functional programming languages. they are very useful to maintain big set of ordered objects.
A node of the weight balanced tree has
a) key, left and right pointers, size
b) key, value
c) key, size
d) key
Explanation: As a weight balanced tree stores height of the subtrees, we need to use size as an additional attribute to every node. Also value(for mappings) may be an optional attribute.
What is the special property of red-black trees and what root should always be?
a) a color which is either red or black and root should always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black
Explanation: An extra attribute which is a color red or black is used. root is black because if it is red then one of red-black tree property which states that number of black nodes from root to null nodes must be same, will be violated.
Which algorithm is used in the top tree data structure?
a) Divide and Conquer
b) Greedy
c) Backtracking
d) Branch
Explanation: Top tree is a type of data structure which is based on unrooted dynamic binary tree and is used to solve path related problems. It allows an algorithm called divide and conquer.
For how many vertices in a set, is top tree defined for underlying tree?
a) 3
b) 4
c) 5
d) 2
Explanation: Top tree is defined for a set having a maximum of 2 vertices for its underlying tree. Those sets having at maximum 2 vertices are called External Boundary Vertices.
