查找具有最大权重且大小不大于给定限制的节点

Question

我正在看这个：

Suggest a Data Structure to handle shipping boxes where each box has: special ID, weight and size.

From all boxes which have a maximum size of v (i.e. size <= v) find the heaviest one in O(log(n)) time, where n is the number of total saved boxes.

You may assume that all weights are different.

我想将这些框保存在 AVL 树中。

我知道解决方案是根据大小对框进行排序并在每个节点中保存一些额外的数据，但我不确定哪些数据会有帮助。

每个节点中保存的额外数据示例：

右子树中最重框的 ID。

例子

考虑下面的 AVL 树，我们在其中寻找尺寸小于 25 的最重的盒子：

什么样的信息可以帮助决定从根开始向右还是向左？

_{* 树是使用以下方法构建的：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html*}

Answer 1

您将按大小为您的 AVL 树设置密钥，并存储（并维护）可以在节点子树中找到的最大权重，同时考虑节点自身的权重.

这将允许：

找到一条从根到可以插入大小为 v 的节点的路径（实际上并没有这样做）。此路径中的最后一个节点将是该潜在未来节点在大小方面最接近的前驱或后继节点。
从那个路径（从根节点到找到的节点）你可以过滤没有更大尺寸的节点，并查看存储在它们左边的 maximum 权重 child 和路径本身上节点的权重。在这些候选者中选择具有最大权重的节点或具有最大最大权重的子树。如果它是一棵子树，则在该节点处沿着子树向下走，以找到具有该最大权重的实际节点。所有这一切都包括一次向下走（找到最大尺寸的节点）和一次向上走（沿着路径）和另一次向下走（遵循相同最大权重的路径）。所以它代表了一个对数时间复杂度。

需要扩展对 AVL 树的操作，以确保正确维护最大权重。例如，当插入一个节点时，只要该权重确定存储在祖先节点中的最大权重，它的权重就应该冒泡。应该更新删除和轮换的算法，以便以合理的方式维护这些额外信息。但在不影响相关时间复杂度的情况下，这一切都是可能的。

实施

此实现将只专注于寻找所需的节点。它不实现 AVL 平衡，也不实现删除操作。所以它是一个普通的二叉树，只有插入和查找功能。

我在具有 size、weight 和 maxWeight 属性的基本 Node class 上定义了以下方法：

pathToSize(size)：这将找到可以插入给定大小的节点作为叶子的插入点。它 return 是一个祖先节点数组，构成从根到 parent 的路径，在该路径下可以插入这样的节点。
findHeaviest()：这将从当前节点获取 maxWeight 信息和 return 此节点子树中匹配该权重的节点。存在三种可能：
- 当前节点的权重与其maxWeight相匹配：return它
- 节点的左边child相同maxWeight: 使用递归在该子树中查找节点。
- 结点的右边child也一样maxWeight:用递归在那个子树中找结点
findHeaviestWithMaxSize(size)：这实现了实际的算法。它调用 pathToSize(size) 来获取路径。然后它将在该路径上寻找大小不大于给定大小的节点。否则：这些是路径右转的节点（除非它是路径上的最后一个节点）。对于这些节点，我们需要检查两个事情：
- 那个节点本身的权重是否比我们目前发现的更大
- 该节点的左子树是否承载了一个比我们目前发现的权重更大的节点。我们不必搜索那个子树，因为我们可以检查左边 child 的 maxWeight.
在这次扫描之后，我们知道去哪里找：要么我们有节点本身，要么我们有一个子树，我们应该在其中找到一个节点 maxWeight。对于后一种情况我们可以使用上面的方法findHeaviest。

下面我在 JavaScript 中提供了一个片段，它允许您定义一个带有数据对输入的二叉树，或者只得到一个有 10 个节点的随机树。然后，您可以更改 size 参数的值，并直观地（使用一个小箭头）查看选择了哪个节点，该节点的大小不大于该节点并使权重最大化。

显然该片段有一些 user-interface 的代码，但核心在 Node class.

的上述方法中

class Node {
    constructor(size, weight) {
        this.size = size;
        this.weight = weight;
        this.left = null;
        this.right = null;
        this.maxWeight = weight;
    }
    pathToSize(size) {
        // Find a path to a node that would be the parent if 
        //   a new node were added with the given size.
        let child = size < this.size ? this.left : this.right;
        if (child === null) return [this];
        // Use recursion to add the rest of the path
        return [this, ...child.pathToSize(size)];
    }
    findHeaviest() {
        // Find a decendant that has a weight equal to the maxWeight of this node
        if (this.weight === this.maxWeight) return this;
        // As it is not this node that has that weight, it must be found
        // in the left or the right subtree:
        if (this.left !== null && this.left.maxWeight === this.maxWeight) {
            return this.left.findHeaviest();
        } else if (this.right !== null && this.right.maxWeight === this.maxWeight) {
            return this.right.findHeaviest();
        }
        throw "tree is inconsistent";
    }
    findHeaviestWithMaxSize(size) {
        let path = this.pathToSize(size);
        // All nodes that have a size up to the given size are represented by this path, as follows:
        // If a node on the path has a size that is not greater, then: 
        //    that node itself and its complete left subtree is in that collection.
        // The union of those collections has all nodes with a size up to the given size.
        // So we will now find where in those collections we have the heaviest node.
        let maxWeight = -Infinity; // The greatest weight we can find among valid nodes
        let bestTree = null; // subtree with heaviest node
        for (let node of path) {
            if (node.size > size) continue; // skip this node
            // Check the weight(!) of the current node:
            if (node.weight > maxWeight) {
                maxWeight = node.weight; // not its maxWeight!!
                bestTree = node;
            }
            // Check the maxWeight(!) of the left subtree
            node = node.left;
            if (node !== null && node.maxWeight > maxWeight) {
                maxWeight = node.maxWeight;
                bestTree = node;
            }
        }
        if (bestTree === null) return null; // there is no such node
        // Get the node with that maxWeight in the identified node/subtree 
        if (bestTree.weight === maxWeight) return bestTree;
        return bestTree.findHeaviest();
    }
    toString(node) {
        // Provide a string representation of this tree
        let left = [];
        let right = [];
        if (this.left !== null) left = this.left.toString(node).split("\n");
        if (this.right !== null) right = this.right.toString(node).split("\n");
        let leftWidth = left[0]?.length || 0;
        let rightWidth = right[0]?.length || 0;
        let width = leftWidth + 5 + rightWidth;
        let lines = Array.from({length: Math.max(left.length, right.length)}, (_, i) =>
            (left[i] || " ".repeat(leftWidth)) + "     " + (right[i] || ""));
        if (lines.length) {
            lines.unshift(
                (leftWidth ? left[0].replace(/\S.*/, "┌").padEnd(leftWidth+2, "─") : " ".repeat(leftWidth+2))
                 + "┴┘└"[!leftWidth * 2 + !rightWidth]
                 + (rightWidth ? right[0].replace(/.*\S/, "┐").padStart(rightWidth+2, "─") : " ".repeat(rightWidth+2))
            );
            lines.unshift("│".padStart(leftWidth+3).padEnd(width));
        }
        lines.unshift((String(this.weight).padStart(4, "0") + "g").padStart(leftWidth+5).padEnd(width));
        lines.unshift((String(this.size).padStart(4, "0") + "m").padStart(leftWidth+5).padEnd(width));
        lines.unshift((node === this ? "▼" : "│").padStart(leftWidth+3).padEnd(width));
        return lines.join("\n");
    }
}

class Tree {
    constructor() {
        this.root = null;
        // Only needed for this demo:
        // for exporting the insertions that are made
        this.array = []; 
    }
    add(size, weight) {
        this.array.push([size, weight]);
        if (this.root === null) {
            this.root = new Node(size, weight);
            return;
        }
        let path = this.root.pathToSize(size);
        let parent = path.pop();
        if (size < parent.size) {
            parent.left = new Node(size, weight);
        } else {
            parent.right = new Node(size, weight);
        }
        // Adjust weight of ancestors
        while (parent !== undefined && parent.maxWeight < weight) {
            parent.maxWeight = weight;
            parent = path.pop();
        }
    }
    toString(markedNode) {
        if (this.root === null) return "";
        return this.root.toString(markedNode);
    }
    findHeaviestWithMaxSize(size) {
        if (this.root === null) return null;
        return this.root.findHeaviestWithMaxSize(size);
    }
    static from(arr) {
        let tree = new Tree;
        for (let pair of arr) {
            tree.add(...pair);
        }
        return tree;
    }
}

let tree = new Tree;

// I/O handling below:

let inpJson = document.getElementById("json");
let inpSize = document.getElementById("size");
let inpWeight = document.getElementById("weight");
let btnCreate = document.getElementById("create");
let output = document.querySelector("pre");

function refresh() {
    let node = tree.findHeaviestWithMaxSize(+inpSize.value);
    output.textContent = tree.toString(node);
    json.value = JSON.stringify(tree.array);
}

function load() {
    let array;
    try {
        array = JSON.parse(json.value);
    } catch {
        return;
    }
    tree = Tree.from(array);
    refresh();
}

inpJson.addEventListener("input", load);
inpSize.addEventListener("input", refresh);

btnCreate.addEventListener("click", function() {
    tree = randomTree();
    refresh();
});

function randBetween(a, b) {
    return Math.floor(Math.random() * (b - a + 1) + a);
}

function randPair() {
    return [randBetween(0, 10), randBetween(0, 10)];
}

function randomTree() {
    let array = Array.from({length: 10}, randPair);
    return Tree.from(array);
}

load();

#json { width: 100% }
#size { width: 3em }

JSON with [size, weight] pairs, in insertion order:<br>
<input id="json" value="[[6,8],[4,1],[8,10],[5,5],[7,5],[9,6],[5,9],[6,7],[8,6]]"><br>
<button id="create">Randomise</button><br>
<hr>
Find heaviest node with size at most: <input id="size" type="number" value="5">m<br>
<pre>
</pre>

为了更好地欣赏此片段，请务必使用“整页”link 将其放大，一旦您拥有它运行。

查找具有最大权重且大小不大于给定限制的节点

Finding node with max weight that has a size not greater than given limit

algorithm

data-structures

tree

binary-tree

avl-tree

例子

实施