Difficulty: Intermediate to Advanced | Prerequisites: 2-3 tree structure and properties, O-notation, tree traversal, induction proofs
This material covers algorithm design on 2-3 trees, one of the fundamental balanced search tree structures. The two problems here, finding the neighbours of an element and retrieving the k smallest elements, illustrate a recurring theme in this course: exploiting tree structure to achieve tight time bounds. The neighbours problem is a direct extension of search in a 2-3 tree. The top-k problem is more subtle and requires a careful counting argument to prove the O(k) bound. If you are not comfortable with 2-3 tree structure (internal nodes with 2 or 3 children, data stored at leaves, keys at internal nodes guiding search), review that material before working through these notes.
The Neighbors algorithm finds the largest element smaller than x and the smallest element larger than x by walking from root to leaf in a 2-3 tree, maintaining pointers to "left" and "right" sibling subtrees. It runs in O(log n) time. The Top-k algorithm retrieves the k smallest elements by recursively traversing children left to right, stopping as soon as k elements are found. A careful inductive argument shows the number of visited nodes is bounded by log n + 2k, giving O(k) time when k ≥ log n.
2-3 tree
A balanced search tree where every internal node has either 2 or 3 children, and all leaves are at the same depth. Data elements are stored at the leaves. Internal nodes store guide keys: l(v) is the largest key in the first child's subtree, m(v) is the largest in the second child's subtree.
Think of it as a search tree that stays perfectly balanced by allowing nodes to have 2 or 3 children, rather than forcing exactly 2 as in a binary tree.
l(v), m(v), h(v)
Guide values stored at an internal node v of a 2-3 tree. l(v) is the largest element in child1(v)'s subtree, m(v) is the largest in child2(v)'s subtree, and h(v) (when a third child exists) is the largest in child3(v)'s subtree. These guide the search downward.
Neighbors of x in a set S
The pair (y₁, y₂) where y₁ is the largest element in S strictly less than x, and y₂ is the smallest element in S strictly greater than x. The element x may or may not be in S.
In simple terms, find the two elements in S that sit immediately to the left and right of x on the number line.
Visited node (in the Top-k analysis)
A node v in the 2-3 tree is "visited" if the recursive call Topk(v) is made during execution. The total count of visited nodes determines the running time.
The idea: Walk from the root to a leaf, searching for x the same way a standard 2-3 tree search works. As you descend, maintain two pointers:
L: the subtree immediately to the left of your current search path (the "left sibling").
R: the subtree immediately to the right of your current search path (the "right sibling").
Why L and R matter: When you reach a leaf, x's predecessor is the maximum of the subtree on your left (Max(L)), and x's successor is the minimum of the subtree on your right (Min(R)). This avoids backtracking up the tree.
The descent logic at each internal node r:
If l(r) ≥ x: go to child1(r). The right sibling becomes child2(r).
Else if m(r) ≥ x or child3(r) does not exist: go to child2(r). The left sibling becomes child1(r). If child3(r) exists, the right sibling becomes child3(r).
Else (x is in the third child's range): go to child3(r). The left sibling becomes child2(r).
At the leaf:
If value(r) == x: y₁ = Max(L), y₂ = Min(R). (The element is in S; its neighbours are in the sibling subtrees.)
If value(r) < x: y₁ = r itself, y₂ = Min(R). (We landed on an element smaller than x; the predecessor is this leaf.)
If value(r) > x: y₁ = Max(L), y₂ = r itself. (We landed on an element larger than x; the successor is this leaf.)
Running time: The algorithm follows one root-to-leaf path (O(log n) steps) plus calls to Min or Max on subtrees (each also O(log n) in the worst case, since they walk down one side of a subtree). Total: O(log n).
The third case at step 3 of the algorithm (value(r) > x and the algorithm sets y₁ = Min(R)) appears to contain a small inconsistency in the original solution document. By the search logic, if value(r) > x, then y₂ should be the current leaf r and y₁ should be Max(L), not Min(R). The corrected reading is: else y₁ = Max(L); y₂ = r. This matches the logic described in the solution's prose and the structure of the algorithm.
The idea: Traverse the tree left to right, visiting children in order (child1, then child2, then child3). Use a global counter k that decrements each time an element is output. Stop as soon as k reaches 0.
Algorithm (Topk):
Base cases: if the tree is empty and k > 0, report "not enough elements." If at a leaf and k > 0, output the leaf's value and decrement k.
Recursive case: if k > 0, recurse on child1(r). If k is still > 0, recurse on child2(r). If k is still > 0 and a third child exists, recurse on child3(r).
Why this outputs the k smallest: The 2-3 tree stores elements at leaves in sorted order from left to right. The leftmost leaf holds the minimum. By visiting children strictly left to right and stopping at k, you output exactly the k smallest elements.
The O(k) time analysis (the hard part):
The key claim is: if Topk(r) is called on a node r of height hᵣ with the global variable k having value k₀, the total number of visited nodes in r's subtree is at most hᵣ + 2k₀.
Base case (leaf): Exactly 1 node is visited. The height is 0 and k₀ ≥ 1 (since we only call when k > 0), so 1 ≤ 0 + 2(1) = 2. The bound holds.
Inductive case, scenario 1: child1(r) has at least k₀ leaves. The recursive call on child1(r) outputs all k₀ elements and sets k = 0. No further children are visited. Visited nodes in child1(r)'s subtree: at most (hᵣ - 1) + 2k₀ by induction. Adding the root r gives hᵣ + 2k₀. Bound holds.
Inductive case, scenario 2: child1(r) has k₁ < k₀ leaves. All nodes in child1(r) are visited (at most 2k₁ nodes, since a subtree with k₁ leaves in a 2-3 tree has fewer than 2k₁ nodes). The algorithm then recurses on child2(r) with k = k₀ - k₁.
If child2(r) has at least k₀ - k₁ leaves, the recursion on child2(r) visits at most (hᵣ - 1) + 2(k₀ - k₁) nodes. Total: 2k₁ + (hᵣ - 1) + 2(k₀ - k₁) + 1 = hᵣ + 2k₀. Bound holds.
If child2(r) has k₂ < k₀ - k₁ leaves, all of child2(r) is visited (at most 2k₂ nodes). The algorithm recurses on child3(r) with k = k₀ - k₁ - k₂. By induction, child3(r) contributes at most (hᵣ - 1) + 2(k₀ - k₁ - k₂). Total: 2k₁ + 2k₂ + (hᵣ - 1) + 2(k₀ - k₁ - k₂) + 1 = hᵣ + 2k₀. Bound holds.
Conclusion: For the entire tree (height log n, initial k₀ = k), visited nodes ≤ log n + 2k. Since k ≥ log n, this simplifies to O(k). Each visited node takes constant time, so the algorithm runs in O(k).
2-3 tree height: h = O(log n) for a tree with n leaves
Node count in a 2-3 subtree: A subtree with k leaves has fewer than 2k nodes (since every internal node has at least 2 children)
Visited-node bound for Topk: Nodes visited ≤ hᵣ + 2k₀, where hᵣ is the height and k₀ is the initial value of k
Overall Top-k complexity: O(log n + 2k) = O(k) when k ≥ log n
The neighbours operation is the backbone of range queries in databases. When a database index is stored as a balanced tree (B-trees, which generalise 2-3 trees, are the standard), finding "the closest records to a given value" is exactly this operation. The top-k retrieval pattern appears everywhere from leaderboard queries ("show the 10 highest scores") to streaming algorithms that maintain the k smallest or largest items seen so far.
"The Neighbors algorithm needs to backtrack up the tree." It does not. By maintaining L and R pointers during the descent, all the information needed is available at the leaf. This is a common design pattern in balanced tree algorithms: carry context downward to avoid climbing back up.
"Top-k must be O(k log n) because you search k times." This would be true if you performed k independent searches, but the algorithm traverses the tree once, left to right, and exploits the sorted order of the leaves. The inductive argument shows the extra overhead from visiting internal nodes along the "frontier" is bounded by the tree height, not k times the tree height.
"A subtree with k leaves has exactly 2k - 1 nodes." That is true for a full binary tree, not a 2-3 tree. In a 2-3 tree, the count is strictly less than 2k because internal nodes can have 3 children, making the tree shallower and containing fewer internal nodes per leaf.
"The Top-k analysis is just about counting leaves." The subtle part is bounding the internal nodes visited along the boundary between fully explored subtrees and partially explored ones. The induction handles this by accounting for the "spine" of partially traversed subtrees.
⚠️ The Neighbors algorithm is a template for many 2-3 tree problems. Understand the L/R pointer technique; it may reappear in modified form (e.g., range counting, predecessor/successor queries).
⚠️ The Top-k inductive proof is the kind of argument the course expects you to reproduce. Practice stating the inductive hypothesis precisely: "the number of visited nodes in the subtree rooted at r is at most hᵣ + 2k₀."
⚠️ Know why the constraint k ≥ log n matters. Without it, the complexity would be O(log n + k), and you could not claim O(k) alone.
⚠️ Be ready to explain why the Top-k algorithm visits at most 2k₁ nodes when all leaves of a subtree with k₁ leaves are output. This relies on the structural property of 2-3 trees (internal nodes < 2 × leaves).
True or false: The Neighbors algorithm requires the element x to be in the set S.
A: False. The algorithm handles both cases, x ∈ S and x ∉ S, with different logic at the leaf.
Fill in the blank: In the Top-k analysis, the total visited nodes in a subtree of height hᵣ with initial k value k₀ is bounded by ___.
A: hᵣ + 2k₀
True or false: The Top-k algorithm runs in O(k) time even when k < log n.
A: False. The bound is O(log n + k). The O(k) simplification requires k ≥ log n.
Fill in the blank: In the Neighbors algorithm, when the search reaches a leaf whose value equals x, the predecessor y₁ is found by calling ___ and the successor y₂ by calling ___.
A: Max(L) and Min(R), respectively.
Q: In the Neighbors algorithm, what are the L and R pointers, and why do they eliminate the need for backtracking?
A: L points to the subtree immediately left of the current search path, and R points to the subtree immediately right. As the search descends, these are updated at each internal node to always reflect the closest subtrees on either side. When the search reaches a leaf, y₁ = Max(L) and y₂ = Min(R) can be computed by walking down these subtrees without ever going back up the main search path.
Q: Why does the Top-k algorithm run in O(k) rather than O(k log n)?
A: Because the algorithm traverses the tree left to right in a single pass rather than performing k independent searches. The inductive analysis shows that the "overhead" internal nodes visited along the boundary of partially explored subtrees total at most log n (the tree height). Since k ≥ log n, the total O(log n + 2k) simplifies to O(k).
Q: State the inductive claim used in the Top-k time analysis and explain the base case.
A: The claim is: if Topk(r) is called on a node of height hᵣ with global variable k = k₀, the total number of visited nodes in the subtree rooted at r is at most hᵣ + 2k₀. Base case: r is a leaf (hᵣ = 0). Exactly 1 node is visited. Since k₀ ≥ 1, we have 1 ≤ 0 + 2(1) = 2, so the bound holds.
Q: In the Neighbors algorithm, what happens if x is smaller than every element in S?
A: The search would descend to the leftmost leaf (the smallest element in S). Since value(r) > x, the algorithm sets y₂ = r and y₁ = Max(L). But L would be Nil (there is no subtree to the left of the leftmost path), so y₁ = Max(Nil) = Nil, indicating there is no predecessor.
The Neighbors algorithm is closely related to predecessor and successor queries in other balanced tree structures (AVL trees, red-black trees, B-trees). The same L/R tracking idea appears in augmented tree structures used for order-statistic queries. The Top-k analysis connects to output-sensitive algorithms more broadly: the running time depends on the size of the output, not just the input, which is a recurring theme in computational geometry and database query processing.
2-3 tree, balanced search tree, predecessor query, successor query, neighbours in sorted set, top-k retrieval, k smallest elements, output-sensitive algorithm, tree traversal, inductive proof, visited node counting, CSCE 629, analysis of algorithms, Texas A&M, B-tree, range query, decision tree, logarithmic search