Exercise 3.6: Skiena Algorithm Design Manual

I am preparing for interview and try to solve the exercise problems of the book.

3-6. [5] Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take O(log n) time each, but successor and predecessor now take O(1) time each. Which operations have to be modified to support this?

Solution: Maintain extra pointers to the successor and predecessor. Update the pointers on insert and delete.

Nothing else right? Or is there some other trick involved.

Thanks

The typical operations on a tree are insertion, deletion and traversal - including successor and predecessor. When a tree is balanced there would be an internal rebalancing operation, so the answer on what operations need to be modified depends on whether you want to interpret "operation" with respect to the external or the internal interface.

The answer, generally is affirmative - you'd need to keep a pointer to the successor (the next element greater than the current one) and the predecessor.

What the question is really about though, is how do you keep these newly proposed pointers up to date given insertions, deletions and rebalance. You can reason about this by induction - given a balanced tree `T` such that the conditions given in the question apply with respect to `T`, how inserting a new node `V` will affect all the other nodes of the tree, and especially those for whom `V` will become the new successor and predecessor. You will have to show that only `O(log n)` nodes will be affected, located and modified, otherwise you cannot keep the operations discussed within this scope of the necessary complexity.

• Thanks. Got it. Basically the additional work of maintaining the successor and predecessor should be O(log n) on each operation. – gudge May 19 '14 at 12:49
• But then this question truly is outside the contents of the chapter. To show my theory is correct I need to implement a balanced tree data structure and show that maintain pointers does not effect the complexity of the operation. – gudge May 19 '14 at 12:57
• You don't need to implement the tree - you need to show how you modify the data-structure and the algorithmic pseudo-code for the operations (including any pre and post-processing) such that with your changes the operations remain `O(log n)` and succ/pred become `O(1)` respectively. – mockinterface May 19 '14 at 13:01
• So the arguments can go like this. At every step in the insertion or deletion process I may be required to change the pointers (successor/predecessor). So if insertion or deletion require log n steps originally, now they would require log n + log n + log n. Which is still O(log n). Hence proved. Correct ? – gudge May 19 '14 at 13:07
• Strictly speaking, that answer doesn't look satisfactory or rigorous enough to me (what is the cost of "changing the pointers"? What "steps" and what about nodes untouched by the "steps"?), but I don't think it is the right place to have this discussion. I suggest that you write it up, show how you change the pseudo-code, and post it as a separate question for commentary and answers. – mockinterface May 19 '14 at 13:13
```````void delete( root, val )
{
node = findNode( root, &par );
nodePred = node->pred;
nodeSucc = node->succ;
if ( nodeSucc )
nodeSucc->pred = nodePred;
if( nodePred )
nodePred->succ = nodeSucc;
// Node delete the node as usual as only parent child relation changes and
// succ pred relation will still remain intact
}

void insert( root, node )
{
if ( root == NULL ) {
root = node;
node->succ = node->pred = NULL;
return;
}
curr = root;
while ( curr ) {
par = curr;
curr = node->val < curr->val ?  curr->left : curr->right;
}
if ( node->val < par->val ) {
par->left = node;
parPred = par->pred;
node->succ = par;
node->pred = parPred;
par->pred = node;
if ( oldPred )
oldPred->succ = node;
} else {
par->right = node;
oldSucc = par->succ;
node->pred = par;
node->succ = oldSucc;
par->succ = node;
if ( oldSucc )
oldSucc->pred = node;
}
}`
``````
• Don't just dump a load of code into an answer; that's no help at all. At the very least explain what the time complexity is of the operations and if the OP got it right or if they 'missed something'. – Martijn Pieters Sep 19 '14 at 6:17
• In other words; this isn't about showing that you can code this up but about the theory behind the algorithms. – Martijn Pieters Sep 19 '14 at 6:18