Test by Bikram | Mock GATE | Test 2 | Question: 13

Question

Which of these statements is not true about a b-Tree $T$ with height $h$ and $n$ nodes, assuming that each node takes exactly $1$ $disk$ operation to read?

• A.  Finding a node in $T$ cannot require more than $O\left ( h \right )$ disk operations (in other words, $O\left ( h \right )$ time, if only disk reads and writes are counted).
• B. $h$ cannot exceed $\log t \left ( \left ( n+1 \right )/2 \right )$, where $t$ is the minimum node degree.
• C. If each node in $T$ is augmented with an integer showing the size of that node’s sub-tree, then $n$ additional nodes can be inserted into $T$ in a total of $O \left ( n \times h \right )$ CPU operations.
• D. Rotations may be required during insertion to keep $T$ balanced.

Comments

if degree of B Tree is 2, that is max child it can have is 2

then it'll behave as an AVL tree? (doubt 1) and suppose it will then

a full AVL tree of nodes n will have a height O(log n) which is > O(log [(n+1)/2]). B should be false as well? (doubt 2)

---

explain this

---

@Niharika 1 and @ritwik

please read my answer, hope it will be clear to you .

Answer 1

Statement  A    " Finding a node in T cannot require more than O(h) disk operations ( in other words, O(h) time, if only disk reads and writes are counted ). "

is  True.

Reason :  Let each node has a minimum of t children . Then searching for a node takes no more time than reading down the tree in O(h) steps and reading across each node in O(t) steps for a total of O(t * h) CPU operations and O(h) disk operations, where t is a constant .

Statement B says " h cannot exceed log_t ((n + 1)/2), where t is the minimum node degree. " 

is True .

Reason : Since each node has a minimum of t children, the height of the tree is O(log_t n) and h cannot exceed log_t ((n + 1) / 2) . 

Statement C  says " If each node in T is augmented with an integer showing the size of that node’s sub-tree, then n additional nodes can be inserted into T in a total of O(n * h) CPU operations. " 

is True .

Reason : Even though the tree may grow due to splits during insertion, an insertion still takes no more than O(t * h) CPU operations, so inserting n nodes takes O(n * t * h) = O(n * h) CPU operations.

Statement D  says : " Rotations may be required during insertion to keep T balanced. " 

is Not True .

Reason :   B-Trees are a generalization  form of a binary trees (which use a single key in each node to segregate children into two groups). 

In B Trees Nodes may be split during key insertion (beginning with the root, if necessary). This has the effect that younger nodes tend to appear near the top of the tree, whereas with binary trees, younger nodes appear near the bottom of the tree.

Thats why  Rotations are not used during insertion to keep that Tree balanced. 

Comments

Thankyou