在使用堆实现的二叉搜索树中，对于节点 P 找到其键立即小于 P 的键的节点

Question

在使用堆实现的二叉搜索树中（因此二叉树用向量表示），对于节点P，找到其键立即小于P的键的节点。

例如，这里的 p 键为 13，下一个较小的键是 11

我认为一旦你找到 p 你应该向左走一次，然后尽可能向右走

Answer 1

In a binary search tree implemented using a heap

堆具有不同的属性：

堆是一个完全二叉树。 BST 不必是完整的（如示例中所示）。数组表示取决于此属性。没有它，数组表示是不明确的：“差距”将如何表示？
堆节点的children的值不小于节点的值（当它是min-heap时），而BST节点的左child（如果有的话）的值不大于节点的值

最后看这题数据结构只是一个细节

I think once you find p you should go once to the left, then go as much to the right as you can

这是一种情况。当p有一个leftchild时确实是正确的。如果不是，你应该向上移动，直到你从右child向上移动。那么你就到了前面的节点了

代码

我假设表示为数组将具有以下特征：

数组会根据需要动态增长
未使用的数组条目将获得保留值 (undefined)

这是 JavaScript 中的一个实现：

class BST extends Array {
    add(value) {
        let i = 0;
        while (i < this.length && this[i] !== undefined) {
            let nodeValue = this[i];
            i = i * 2 + 1;
            if (value >= nodeValue) {
                i++;
            }
        }
        // Extend array ... although JS would do this automatically..
        while (this.length <= i) {
            this.push(undefined);
        }
        this[i] = value;
        return this;
    }
    predecessor(i) {
        // if has left child...
        let child = i * 2 + 1;
        if (child < this.length && this[child] !== undefined) {
            // then find right most descendent
            while (child < this.length && this[child] !== undefined) {
                i = child;
                child = child * 2 + 2;
            }
            return i;
        }
        // otherwise, while it is a left child, go up
        while (i % 2 == 1) {
            i = (i - 1) / 2; 
        }
        if (i > 0) { // not the root, but a right child of a parent
            return (i - 2) / 2;
        }
        // We reached the root... there is no predecessor
        return -1;
    }
}

// Demo
let bst = new BST();
// Load example tree
bst.add(16).add(7).add(6).add(13).add(10).add(8).add(11);
// Find node with value 16
let i = bst.indexOf(16);
// Keep walking to the node that precedes it...
while (i >= 0) {
    console.log(`bst[${i}] == ${bst[i]}`);
    i = bst.predecessor(i);
}

注意数组的使用索引是如何分散的：很多条目实际上是“间隙”，即未使用的条目。

在使用堆实现的二叉搜索树中，对于节点 P 找到其键立即小于 P 的键的节点

In a binary search tree implemented using a heap, for a node P find the node with the key that is immediately smaller than the key of P

algorithm

tree

binary-tree

binary-search-tree

heap

代码