title: Special Augmented Red-Black Tree
body: <p>I'm looking for some help on a specific augmented Red Black Binary Tree. My goal is to make every single operation run in <code>O(log(n))</code> in the worst case. The nodes of the tree will have an integer as there key. This integer can not be negative, and the tree should be sorted by a simple compare function off of this integer. Additionally, each node will also store another value: its power. (Note that this has nothing to do with mathematical exponents). Power is a floating point value. Both power and key are <em>always</em> non-negative. The tree must be able to provide these operations in <code>O(log(n))</code> runtime.:</p>
  
  <ol>
  <li><p>insert(key, power): Insert into the tree. The node in the tree should also store the power, and any other variables needed to augment the tree in such a way that  all other operations are also <code>O(log(n))</code>. You can assume that there is no node in the tree which already has the same key.</p></li>
  <li><p>get(key): Return the power of the node identified by the key.</p></li>
  <li><p>delete(key): Delete the node with key (assume that the key does exist in the tree prior to the delete.</p></li>
  <li><p>update(key,power): Update the power at the node given by key.</p></li>
  </ol>
  
  <p>Here is where it gets interesting:</p>
  
  <ol start="5">
  <li><p>highestPower(key1, key2): Return the maximum power of all nodes with key <code>k</code> in the range key1 &lt;= <code>k</code> &lt;= key2. That is, all keys from key1 to key2, inclusive on both ends.</p></li>
  <li><p>powerSum(key1, key2): Return the sum of the powers of all nodes with key <code>k</code> in the ragne key1 &lt;= <code>k</code> &lt;= key2. That is, all keys from key1 to key2, inclusive on both ends.</p></li>
  </ol>
  
  <p>The main thing I would like to know is what extra variables should I store at each node. Then I need to work out how to use each one of these in each of the above functions so that the tree stays balanced and all operations can run in <code>O(log(n))</code> My original thought was to store the following: </p>
  
  <ol>
  <li>highestPowerLeft: The highest power of all child nodes to the right of this node. </li>
  <li>highestPowerRight: The highest power of all child nodes to the right of this node.</li>
  <li>powerSumLeft: The sum of the powers of all child nodes to the left of this node.</li>
  <li>powerSumRight: The sum of the powers of all child nodes to the right of this node.</li>
  </ol>
  
  <p>Would just this extra information work? If so, I'm not sure how to deal with it in the functions that are required. Frankly my knowledge of Red Black Tree's isn't great because I feel like every explanation of them gets convoluted really fast, and all the rotations and things confuse the hell out of me. Thanks to anyone willing to attempt helping here, I know what I'm asking is far from simple.</p>