# Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input integer of VALUE and i'm required to insert it into an AVL tree. So i created an AVL tree, where each node contains a key that equals the original value of the node plus the global variable. (key = Value + Glob) I input n number of objects into the AVL tree (I assume each one has a unique key)

The question is: I want to increase GLOB by a certain amount, and therefor increase the KEY of each node by that amount. Will this happen in a run time of O(1) or O(n) since i need to "update" all of the nodes, even though they simply contain pointers to GLOB?

• If every key must share GLOB can I do it with runtime of $O(1)$ ? – BAM May 26 '16 at 5:04
• Each node has a unique Value, but they share the same GLOB. So for example I'd like to increase all the nodes' key by 5, I would just increase GLOB by 5. However I'm not sure if this will update all of their keys in a constant time or O(n). – BAM May 26 '16 at 9:14

Assuming that the $GLOB$ variable is consistent under any operations, the update time is $O(1)$, where the variable is changed and all inserts are made without adding it to the key value. Search is done by subtracting the $GLOB$ variable from the input, so there is no need to update every key. If the real key value is needed the addition actually occurs returning the sum $Value + GLOB$ instead if reading just the inserted key.