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

您将按大小对您的 AVL 树进行键控，并存储（并维护）可以在节点的子树中找到的最大权重，同时考虑节点自身的权重。

这将允许：

找到从根到可以插入大小为 v 的节点的路径（实际上 没有这样做）。就大小而言，这条路径中的最后一个节点将是该潜在未来节点最接近的前任或后继节点。
从该路径（从根到找到的节点），您可以过滤没有更大尺寸的节点，并查看存储在其左子节点中的最大权重以及路径本身上节点的权重。在这些候选者中选择权重最大的节点或最大权重的子树。如果它是子树，则沿着该节点的子树向下走，以找到具有此最大权重的实际节点。所有这一切都包括一次向下（寻找最大尺寸的节点）和一次向上（沿着路径）和另一次向下（沿着最大权重相等的路径）。所以它表示对数时间复杂度。

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

执行

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

我在具有和属性的基本Node类上定义了以下方法：sizeweightmaxWeight

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

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

显然，该代码段包含一些用户界面代码，但核心在上述Node类的方法中。

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>

为了更好地欣赏此片段，请确保在运行后使用“整页”链接将其放大。

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

问题描述

例子

解决方案

执行

推荐阅读