所以我给AVL树。和IM试图找出至少伪code，以找到在所有的两个值k1和k2键的最小数据值的关键。这是假设存储在每个节点的字段的数据是一个整数。我想确保我的伪code在O（LOGN）时间运行。

So I'm given an AVL tree. And im trying to figure out at least the pseudocode to find the key with the minimum data values among all of the keys between two values k1 and k2. This is assuming that the field data stored in each node is an integer. I want to make sure that my pseudocode runs in O(logn) time.

我知道我可以通过存储额外的字段中节点structure..and显示如何这一领域可以在更新过程中可以保持做到这一点，但我不知道从那里走了。

I know that I can do it by storing an extra field in the node structure..and showing how this field can be maintained during updates, but I don't know where to go from there.

推荐答案

假设节点结构看起来像这样（JAVA）。

Let's assume that the node structure looks like this (Java).

class Node {
    Node left;
    Node right;
    int key;
    int value;
    int tree_max;
}

复发的 tree_max 是

node.tree_max == max(node.value, node.left.tree_max, node.right.tree_max),

在由滥用的符号，我们省略 node.left.tree_max 在 node.left 为null，并且省略 node.right.tree_max 在 node.right 为空。我们写一个节点每一次，我们可能需要更新其所有的祖先。我不会写假code，因为没有一个编译器，我会最有可能搞错了。

where by abuse of notation we omit node.left.tree_max when node.left is null and omit node.right.tree_max when node.right is null. Every time we write to a node, we may have to update all of its ancestors. I'm not going to write the pseudocode, because without a compiler I'll most likely get it wrong.

要找到按键之间的最大 K1 和 2 包容性，我们首先找到这些节点的最低共同祖先

To find the max between keys k1 and k2 inclusive, we first locate the least common ancestor of those nodes.

Node lca = root;
while (lca != null) {
    if (lca.key < k1) { lca = lca.left; }
    else if (k2 < lca.key) { lca = lca.right; }
    else { break; }
}

现在，如果 LCA 为null，则范围为空，我们应该返回负无穷大或抛出异常。否则，我们需要找到最大超过三个范围： K1 包容 LCA 独家， LCA 本身，而 LCA 独占 2 的包容性。我给了$ C $下 K1 包容 LCA 排斥;其他两个范围是微乎其微的，对称的分别。我们移动手指那棵树就像我们正在寻找 K1 ，累计最高为 left_max 。

Now, if lca is null, then the range is empty, and we should return minus infinity or throw an exception. Otherwise, we need to find the max over three ranges: k1 inclusive to lca exclusive, lca itself, and lca exclusive to k2 inclusive. I'll give the code for k1 inclusive to lca exclusive; the other two ranges are trivial and symmetric respectively. We move finger down the tree as though we're searching for k1, accumulating the maximum into left_max.

int left_max = /* minus infinity */;
Node finger = lca.left;
while (finger != null) {
    if (k1 <= finger.key) {
        left_max = max(left_max, finger.value);
        if (finger.right != null) { left_max = max(left_max, finger.right.tree_max); }
        finger = finger.left;
    } else { finger = finger.right; }
}