Search code examples
rankavl-tree

Finding biggest integer smaller than max key but not in AVL tree

Given AVL tree T, I need to find the maximal integer which is smaller than maximal key in tree, but is not in tree.

I've written auxiliary functions to get the biggest node, yet my thoughts are stuck.

I tried looking at the rank of the maximal node and the rank of it's successor yet that doesn't do any help.

Any ideas would be really helpful!

Solution

  • The general idea is: initialize a variable crawl with the max (crawl <- max). Search the second maximum. If it's smaller than crawl-1, your answer is crawl-1. Else, there are two possibilities:

    1. The second maximum is equal to crawl-1: assign crawl <- crawl-1.
    2. The second maximum is equal to crawl.

    In any of the cases, search the third maximum. If it's smaller than crawl-1, your answer is crawl-1. Else, there are two possibilities:

    1. The third maximum is equal to crawl-1: assign crawl <- crawl-1.
    2. The third maximum is equal to crawl.

    ...

    Did you notice the recursion structure ?

    Either you will find the answer at some step or you will achieve the smallest element without answer. In this case the answer will be crawl-1 (which will store min-1 at this step).

    To find the successive maximums, you can iteratively remove the maximum. For example, to find the second maximum, remove the maximum and find the maximum in the new AVL tree.

    The time complexity would be O(n * log n). Each removal operation takes O(log n) and you do at most n removals.