Loading page…
Master the fundamental concepts of b-trees through this focused micro-challenge.
B-tree search starts at the root, binary-searches keys in the current node to pick a child pointer, and repeats until a leaf returns a value or reports missing. Height stays O(log n) because each node holds many keys.
For each node, find the first key greater than target; follow the left child of that key. On leaf, scan or binary search for exact match.
cLoading…
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will implement B-tree search from root to leaf and return the value or NOT_FOUND. This exercise asks you to trace one lookup path printing visited keys.
Search a B-tree (MAX_KEYS = 3). The starter builds this tree, where each key's value is ten times the key:
cLoading…
Point search: start at the root. In each node, scan the keys left to right until the first key >= the target. If that key equals the target, the search is done; this can happen in the root, since 20 and 50 live there. Otherwise follow child i, where i is the position of that key (or n if every key is smaller). Failing at a leaf means the key is absent. In the root, a key below 20 goes to child 0, from 21 to 49 to child 1, and above 50 to child 2.
Range search: list every key in [lo, hi] in ascending order with an in-order walk: child 0, key 0, child 1, key 1, ... Skip any child whose keys are all outside the range.
Commands until the end of input:
get Kpath Krange LO HIget: found key=30 value=300 or not_found key=99 value=-1.path: the nodes visited, then the outcome:cLoading…
The result is -1 when the key is absent.
range: range 15..60: 15=150 20=200 25=250 30=300 40=400 50=500 60=600, then count=7. An empty range prints range 41..49: and count=0.Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it works