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?

  • $\begingroup$ If every key must share GLOB can I do it with runtime of $O(1)$ ? $\endgroup$ – BAM May 26 '16 at 5:04
  • $\begingroup$ 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). $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.