Data Structure Questions and Answers-Weight Balanced Tree
What is a weight balanced tree?
A binary tree that stores the sizes of subtrees in nodes
A binary tree with an additional attribute of weight
A height balanced binary tree
A normal binary tree
Question 1 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?
dynamic sets, dictionaries, sequences, maps
Question 2 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
key, left and right pointers, size
Question 3 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.
The size value of various nodes in a weight balanced tree are
leaf - zero
internal node - size of it's two children
is this true?
Question 4 Explanation:
Size of a node k is size[k] = size[k.left] + 1 + size[k.right] and based on this the weight will be given as weight[k] = size[k] + 1.
What is the condition for a tree to be weight balanced. where a is factor and n is a node?
weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].
weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].
weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].
weight[n] is a non zero
Question 5 Explanation:
The tree is said to be a-balanced if the condition is satisfied. and 'a' value will be determined during tree formation. large value of 'a' is more effective.
There are 5 questions to complete.