AVL Tree：在O（logn）時間內的兩個值之間的鍵中查找具有最小數據值的鍵

Question

因此我得到一個AVL樹。我試圖找出至少僞代碼來找到兩個值k1和k2之間的所有密鑰中具有最小數據值的密鑰。這是假設每個節點中存儲的字段數據是一個整數。我想確保我的僞代碼在O（logn）時間運行。

我知道我可以通過在節點結構中存儲一個額外的字段來實現它。並顯示更新過程中如何維護這個字段，但我不知道該從哪裏去。

Answer 1

我們假設節點結構看起來像這樣（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爲空。每次我們寫入節點時，我們都可能需要更新其所有的祖先。我不會編寫僞代碼，因爲如果沒有編譯器，我很可能會誤解它。

要找到密鑰​​和k2之間的最大值，我們首先找到這些節點的最小公共祖先。

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，則範圍是空的，我們應該回到負無窮大或拋出異常。否則，我們需要查找超過三個範圍的最大值：​​（含），至lca（不含），lca本身以及lca（不含k2）。我會給代碼​​包括lca排他性;另外兩個範圍分別是平凡的和對稱的。我們將finger移動到樹上，好像我們正在搜索​​，將最大值累加到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; } 
}