Data Structure Questions and Answers – Weight Balanced Tree

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Weight Balanced Tree”.

1. What are the operations that can be performed on weight balanced tree?
A) all basic operations and set intersection, set union and subset test
B) all basic operations
C) set intersection, set union and subset test
D) only insertion and deletion

Explanation: A weight balanced tree’s unique feature is that, in addition to simple operations, we can perform collective operations such as set intersection, which aids rapid prototyping in functional programming languages.

2. 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
A) log2 n
B) log4/3 n
C) log3 n
D) log3/2 n

Explanation: Total number of nodes can be described by the recurrence T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1 T(1) = 1. height of the tree will be H(n) = H(2/3(n-1)) + 1, H(1). drawing a recurrence tree and the cost at each level is 1 and the height will be log(3/2)n.

3. Why the below pseudo code where x is a value, wt is weight factor and t is root node can’t insert?

WeightBalanceTreeNode insert(int x, int wt, WeightBalanceTreeNode k) :
 
           if (k == null)
                k = new WeightBalanceTreeNode(x, wt, null, null)
           else if (x < t.element) :
 
                k.left = insert (x, wt, k.left)
                if (k.left.weight < k.weight)
                    k = rotateWithRightChild (k)
 
            else if (x > t.element) :
 
                k.right = insert (x, wt, k.right)
                if (k.right.weight < k.weight)
                    k = rotateWithLeftChild (k)
A) when x>t. element Rotate-with-left-child should take place and vice versa
B) the logic is incorrect
C) the condition for rotating children is wrong
D) insertion cannot be performed in weight balanced trees

Explanation: Children's rotations must be switched around in the code.

4. 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.
A) weight balanced and height balanced tree definations
B) height balanced and weight balanced tree definations
C) definations of weight balanced tree
D) definations of height balanced tree

Explanation: They are the weight and height balance descriptors. Weight balance can not be conveyed by height balanced trees, but the reverse can be true.

5. 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.
A) true
B) false

Explanation: We can also store the key information as a key value pair in a weight balanced tree.

6. 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 keep track of height and colour, weight balanced trees keep track of subtree size.

7. 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 tree that is commonly used in functional programming languages for storing key-value pairs. They’re great for keeping track of a large number of well-organized things.

8. A node of the weight balanced tree has
A) key, left and right pointers, size
B) key, value
C) key, size
D) key

Explanation: We need to use size as an additional attribute to a node since a weight balanced tree stores the height of the subtrees. Also, value(for mappings) may be a non-mandatory attribute.

9. 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?

A) true
B) false

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.

10. What is the condition for a tree to be weight balanced. where a is factor and n is a node?
A) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].
B) weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].
C) weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].
D) weight[n] is a non zero

Explanation: If the condition is met, the tree is said to be a-balanced. During the creation of the tree, the ‘a’ value will be calculated. It is more effective to use a broad value of ‘a’.

WBTs are a type of self-balancing binary search tree that can be used to implement dynamic sets, dictionaries (maps), and sequences. Trees of bounded equilibrium, or BB[] trees, were introduced by Nievergelt and Reingold in the 1970s. Knuth is responsible for their more well-known moniker. WBTs, like other self-balancing trees, store balance bookkeeping information in their nodes and rotate to restore balance when it is disrupted by insertion or deletion operations.

Leave a Reply

Your email address will not be published. Required fields are marked *