AVL树：在O(logn)时间内找到两个值之间的键中数据值最小的键

所以我得到了一棵AVL树。我试图至少找出伪代码，以在两个值 k1 和 k2 之间的所有键中找到具有最小数据值的键。这是假设每个节点中存储的字段数据是整数。我想确保我的伪代码在 O(logn) 时间内运行。

我知道我可以通过在节点结构中存储一个额外的字段来做到这一点......并展示如何在更新期间维护该字段，但我不知道从哪里开始。

我们假设节点结构如下所示（Java）。

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

复发为tree_max is

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

由于滥用符号，我们省略了node.left.tree_max when node.left为空并省略node.right.tree_max when node.right一片空白。每次我们写入一个节点时，我们可能都必须更新它的所有祖先。我不会编写伪代码，因为如果没有编译器，我很可能会出错。

查找键之间的最大值k1 and k2包含在内，我们首先找到这些节点的最不共同的祖先。

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

Now, if lca为 null，则范围为空，我们应该返回负无穷大或抛出异常。否则，我们需要找到三个范围内的最大值：k1包含于lca独家的，lca本身，以及lca专属于k2包括的。我将给出代码k1包含于lca独家的;其他两个范围分别是平凡的和对称的。我们走finger就好像我们在寻找一样从树上下来k1，将最大值累加到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; }
}