How to locate immediate predecessor with O(log n) time complexity

Question

First, of all i would like to let anyone know that this is an assignment and i've finished the locate immediate predecessor with O(n), but i would like to do it with O(log n), i know it's possible since the tree is an AVL tree.

The way i've done it with O(n) is i divide the tree into 2 based on the key(record) and do a max search for the left tree and min search for the right tree. I know it's not log n since after i narrowed the solution, i still have to process all the nodes in the left or right tree so at best it's still 1/2n.

I can see the pattern of the solutions but still can't wrap my mind around it. i'm thinking about using root and node pointer but i'm still not sure of how to implement it.

Any pointers would be appreciated, i've googled and tried to solve this problem to no avail for several days now.

Answer 1

Given a node N in an AVL tree, there are three cases:

1. N has a left child L. Then the immediate predecessor of N must be the right-most deepest descendent of L. To locate it, you need to descend into the subtree of L, taking the right branch at each sub-node. There can be at most log n levels, so this is O(log n).

2. N has no left child, but is itself the right child of a parent P. Then P must be the immediate predecessor, located in O(1) time.

3. N has no left child and is the left child of a parent P. Then walk up the tree towards the root until you find a node that is the right child of an ascendent A. If there is no such A, N does not have any predecessor; otherwise A is the immediate predecessor of N. Again, there can be at most log n parent levels to check, so this is also O(log n).

Determining which of the three applies can obviously be done in O(1) time, so the total time complexity is O(log n).

Example AVL tree for reference (this is the same example as given on the Wikipedia page for AVL tree, but I've recreated the graph rather than copying the image; the source can be forked from here if anybody would like to make modifications):

Nodes 17 and 50 are examples of case 1; node 76 is an example of case 2; node 9 is an example of case 3 with no predecessor; node 19 is an example of case 3 with predecessors. If you think through each of the cases looking at examples from the tree above, you'll be able to confirm that the statements are true. This may be easier than going through a formal proof (which nevertheless could be given).

Answer 2

i actually figured out an easier way to solve this problem without using parent or child pointer.

Here's what i did: Save each node as i traverse the tree recursively and save all nodes that has record less than target.

if it's a leaf then return your temp pointer to the caller.