(29 # _ )
/ \
/ \
/ \
(21 # _) (37 # 50 )
/ \ / | \
/ \ / | \
(7,9,11) (21,23) (29,30) (37,49) (50,100)
If we were to search for the node 100, we would do the following:
1. check 100 vs 29, clearly larger, on to next key 2. but there is no key, so go to last child 3. check 100 vs 37, clearly larger, on to next key 4. check 100 vs 50, clearly larger, on to next key 5. there is no key, so go to last child 6. check 100 vs 50 (in the leaf now), larger, on to next key 7. check 100 vs 100, success!We could write a short hand trace of this search like this: 29, 37, 50, 50, 100, success.
On the other hand, the search for 22 might look like:
1. check 22 vs 29, less than, go to prior child 2. check 22 vs 21, greater than, on to next key 3. no key available, go to last child 4. check 22 vs 21 (in leaf), greater than, go on to next key 5. check 22 vs 23, less than, return unsuccesful!This trace would be: 29,21,21,23, unsuccessful.
For the tree:
(37 # _ )
/ \
/ \
/ \
(21 # 29) (50 # _ )
/ | \ / \
/ | \ / \
(7,9,11) (21,23) (29,30) (37,49) (50,100)
Write the trace for 30 and 48.