A weight balanced tree is a binary tree in which for each node, the number of nodes in left subtree is at least half at most twice the number of nodes in the right subtree. The maximum possible height of such a tree on n nodes is best described by which of the following?
A weight balanced tree is a binary tree in which for each node, the number of nodes in left subtree is at least half at most twice the number of nodes in the right subtree. The maximum possible height of such a tree on n nodes is best described by which of the following?
The correct option is D log32n
A weight balanced tree is a binary tree in which for each node, the number of nodes in left subtree is at least half at most twice the number of nodes in the right sub tree. The maximum possible height of such a tree on n nodes is best described by log3/2n.
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.
A binary tree is a tree data structure in
which each node has at most two children, which are referred to as the left
child and the right child.
A weight balanced tree is a binary tree in which for each node, the number of nodes in left subtree is at least half at most twice the number of nodes in the right sub tree. The maximum possible height of such a tree on n nodes is best described by log3/2n.
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.
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
