如何以迭代方式在不递归的情况下按顺序遍历 BTree？

Question

我需要B-Tree LNR遍历（按顺序）。我找到了一个 B-Tree 遍历算法 here。如何在不以迭代方式递归的情况下实现它？我找到了 this question 但没有答案，而且问题中的代码非常不清楚并且似乎不正确。至少，这不是LNR，也不适合我。我也找到了很多简单的二叉树遍历的例子，但我需要的正是 B-Tree。

我使用 Rust，但我很乐意看到任何语言或伪代码的答案。

Answer 1

正如评论中已经提到的那样：如果您不想使用递归——这是可行的方法——那么您将不得不使用堆栈来模仿它。

该堆栈上的条目将是一对，包括：

对节点的引用，并且
该节点内的当前索引 (0...m-1)，其中 m 是该节点的分支数节点

例如，我将使用以下 B-tree:

...并使用 JSON 表示：

{
    "keys": [29],
    "children": [{
        "keys": [15, 21],
        "children": [{
            "keys": [11, 12]
        }, {
            "keys": [18, 20]
        }, {
            "keys": [23, 25, 27]
        }]
    }, {
        "keys": [35, 42],
        "children": [{
            "keys": [31, 33]
        }, {
            "keys": [36, 39]
        }, {
            "keys": [45, 47, 50, 55]
        }]
    }]
}

这是 JavaScript 中 iterate 函数的实现，其中 returns 是按 LNR 顺序对键进行的迭代器：

function * iterate(node) {
    let stack = []; // stack of [node, child-index] pairs
    
    stack.push([node, 0]);
    while (stack.length > 0) {
        let [node, i] = stack.pop();
        if (!("children" in node)) { // bottom level has no "children" member
            for (let key of node.keys) {
                yield key;
            }
        } else if (i < node.children.length) {
            if (i > 0) {
                yield node.keys[i-1];
            }
            stack.push([node, i+1]);
            stack.push([node.children[i], 0]);
        }
    }
}

// The example B-tree:
const btree = {"keys": [29],"children": [{"keys": [15, 21],"children": [{"keys": [11, 12]}, {"keys": [18, 20]}, {"keys": [23, 25, 27]}]}, {"keys": [35, 42],"children": [{"keys": [31, 33]}, {"keys": [36, 39]}, {"keys": [45, 47, 50, 55]}]}]};

// Consume the iterator and output
console.log(...iterate(btree));

Answer 2

虽然 stack/recursion 是有效的，但它需要 O(log n) space。如果想同时拥有两个或更多迭代器（至少在堆中），这会很复杂。另一种方法是以时间为代价使其采用 O(1) space，前提是一个有 独特的条目 （严格单调。）在 pseudo-code:

iterator { tree root; { node; height; idx; } pos; };

boolean pin(iterator it) {
    if(!it.root) return false;
    /* Special case: off the left. */
    if(!it.pos.node) it.pos.node = it.root.node,
        it.pos.height = it.root.height, it.pos.idx = 0;
    /* Descend the tree. */
    while(it.pos.height) it.pos.height--,
        it.pos.node = it.pos.node.child[it.pos.idx], it.end.idx = 0;
    if(it.end.idx < it.end.node.size) return true; /* Likely. */
    if(!it->end.node->size) return false;
    /* Go down the tree again and note the next. */
    next.node = 0, x = it.pos.node.x[it.pos.node.size - 1];
    for(s = it.root; s.height; s.node = s.node.child[a0], s.height--) {
        a1 = s.node.size; a0 = 0;
        while(a0 < a1) {
            m = (a0 + a1) / 2;
            if(x > s.node->x[m]) a0 = m + 1; else a1 = m;
        }
        if(a0 < s.node.size)
            next.node = s.node, next.height = s.height, next.idx = a0;
    }
    if(!next.node) return false; /* Off the right. */
    it.pos = next;
    return true; /* Jumped nodes. */
}
iterator begin(tree tree) {
    iterator it;
    it.root = tree.root, it.pos.node = 0;
    return it;
}
entry next(iterator it) {
    return pin(it) ? it.pos.node[it.pos.idx++].to_entry() : null;
}

在 pin 函数中，它需要 out-of-bounds 访问 height-zero 节点并从根节点重新启动。它查找返回的最后一个值，但在降序节点中保留 next-key 的记录。它发现 next-key 的 minimum-height 节点是逻辑 next-key。如果它没有找到任何 next-key，则迭代完成。这样比较慢，O(n log n)完成整个迭代，但可能更方便。

如何以迭代方式在不递归的情况下按顺序遍历 BTree？

How to traverse BTree in-order without recursion in iterative style?

algorithm

tree

iteration

tree-traversal

b-tree