Balanced Trees and AVL Questions and Answers

Q: Some differences between B tree and B+ tree approaches are :(i) In a B tree, search keys and data are stored in internal or leaf nodes. But, in B+ tree, data are stored only in leaf nodes.(ii) A link is maintained among all the nodes so that one can move from the left-most node to right-most node in B+ tree.

Both (i) and (ii) are correct.In a B tree, keys and their data (or record pointers) are stored in internal nodes as well as leaves. In a B+ tree, internal nodes hold only keys to guide the search, and all data lives in the leaves (i).The leaves of a B+ tree are also linked together in key order, so after reaching the left-most leaf one can scan sequentially to the right-most, which makes range queries efficient (ii). So neither statement alone is the full picture.

Q: AVL tree is used :

An AVL tree is used to avoid formation of skew trees.An ordinary binary search tree can become skewed, degenerating into a linked list when keys arrive in sorted order, so search takes O(n) time. An AVL tree keeps the balance factor (height of left subtree minus height of right) of every node at -1, 0 or +1, restoring it with rotations after each insertion or deletion, so its height stays O(log n).It does not save memory (each node stores extra balance information), does not speed up memory access itself, and does not simplify storage, since rotations make insertion more complex.

Q: B+ trees are considered BALANCED because :

B+ trees are balanced because the lengths of the paths from the root to all leaf nodes are all equal.A B+ tree grows and shrinks only at the root: inserts split nodes upwards and deletes merge them, so all leaves always stay at the same depth. That guarantees every search, from root to leaf, takes the same number of steps, logarithmic in the number of keys.Paths differing by at most 1 is the AVL tree's notion of balance, not the B+ tree's. B+ tree nodes only need to be at least half full, so sibling nodes can differ in their number of children or records by more than 1.

Q: The maximum number of children that a B-tree of order m can have :

A B-tree of order m has at most m children per node.In the usual (Knuth) definition, the order is the maximum number of children. Each node then holds at most m - 1 keys, and every internal node other than the root has at least \(\lceil m/2 \rceil\) children.m - 1 is the maximum number of keys, not children. m + 1 and 2m exceed the definition, though 2m appears in the older convention in which 'order' means the minimum degree.

Some differences between B tree and B⁺ tree approaches are :

(i) In a B tree, search keys and data are stored in internal or leaf nodes. But, in B⁺ tree, data are stored only in leaf nodes.
(ii) A link is maintained among all the nodes so that one can move from the left-most node to right-most node in B⁺ tree.

A.only (i) is correct
B.only (ii) is correct
C.Both (i) and (ii) are correct
D.Both (i) and (ii) are incorrect

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

Both (i) and (ii) are correct.

In a B tree, keys and their data (or record pointers) are stored in internal nodes as well as leaves. In a B⁺ tree, internal nodes hold only keys to guide the search, and all data lives in the leaves (i).

The leaves of a B⁺ tree are also linked together in key order, so after reaching the left-most leaf one can scan sequentially to the right-most, which makes range queries efficient (ii). So neither statement alone is the full picture.

Discuss in Forum

AVL tree is used :

A.to save memory
B.to attain faster memory access
C.to avoid formation of skew trees
D.to simplify storing

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

An AVL tree is used to avoid formation of skew trees.

An ordinary binary search tree can become skewed, degenerating into a linked list when keys arrive in sorted order, so search takes O(n) time. An AVL tree keeps the balance factor (height of left subtree minus height of right) of every node at -1, 0 or +1, restoring it with rotations after each insertion or deletion, so its height stays O(log n).

It does not save memory (each node stores extra balance information), does not speed up memory access itself, and does not simplify storage, since rotations make insertion more complex.

Discuss in Forum

B⁺ trees are considered BALANCED because :

A.The lengths of the paths from the root to all leaf nodes are all equal
B.The lengths of the paths from the root to all leaf nodes differ from each other by at most 1
C.The number of children of any two non-leaf sibling nodes differ by at most 1
D.The number of records in any two leaf nodes differ by at most 1.

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: A

B⁺ trees are balanced because the lengths of the paths from the root to all leaf nodes are all equal.

A B⁺ tree grows and shrinks only at the root: inserts split nodes upwards and deletes merge them, so all leaves always stay at the same depth. That guarantees every search, from root to leaf, takes the same number of steps, logarithmic in the number of keys.

Paths differing by at most 1 is the AVL tree's notion of balance, not the B⁺ tree's. B⁺ tree nodes only need to be at least half full, so sibling nodes can differ in their number of children or records by more than 1.

Discuss in Forum

The maximum number of children that a B-tree of order m can have :

A.m + 1
B.m - 1
C.m
D.2m

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: C

A B-tree of order m has at most m children per node.

In the usual (Knuth) definition, the order is the maximum number of children. Each node then holds at most m - 1 keys, and every internal node other than the root has at least \(\lceil m/2 \rceil\) children.

m - 1 is the maximum number of keys, not children. m + 1 and 2m exceed the definition, though 2m appears in the older convention in which 'order' means the minimum degree.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Balanced Trees and AVL Questions and Answers || Balanced Trees and AVL MCQ Questions and Answers || Balanced Trees and AVL GK Questions and Answers || Balanced Trees and AVL GK MCQ Questions || Balanced Trees and AVL Multiple Choice Questions and Answers || Balanced Trees and AVL GK || GK on Balanced Trees and AVL || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Balanced Trees and AVL Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications