Find the minimum gap between two numbers in an AVL tree

Question

I have a data structures homework, that in addition to the regular AVL tree functions, I have to add a function that returns the minimum gap between any two numbers in the AVL tree (the nodes in the AVL actually represent numbers.)

Lets say we have the numbers (as nodes) 1 5 12 20 23 21 in the AVL tree, the function should return the minimum gap between any two numbers. In this situation it should return "1" which is |20-21| or |21-20|.

It should be done in O(1).

Tried to think alot about it, and I know there is a trick but just couldn't find it, I have spent hours on this.

There was another task which is to find the maximum gap, which is easy, it is the difference between the minimal and maximal number.

Oh, I am very sorry! It should be |21-20| or |20-21| = 1, the function should return 1! Very sorry for the mistake! — TheNotMe, Sep 08 '12 at 12:27
When I draw a balanced binary tree with those numbers then 20 is the root node and 21 is the deepest and left-most leaf node in the right subtree of the root. I have a feeling you have to take the difference between the root and a very deep leaf. I'd have to read up on AVL trees again to see if you can 'abuse' this characteristic of those trees. — Simeon Visser, Sep 08 '12 at 12:29
I am quite sure there is a trick of this sort. What stunned me is that I should do it in O(1) - I could think of no algorithm to do that! Besides I should mention, that all the basic functions of the AVL tree like Init, Search, Insert, Delete should still be O(log(n)) - So I am sure I should not add anything to the basic functions! This question had me scratching my head for hours! — TheNotMe, Sep 08 '12 at 12:33
Take a look at this link: http://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree it seems that really exist that algorithm, but requires a preprocess in O(n) — raven1981, Sep 08 '12 at 13:09
O(n) is not an option for me. I -must- do it in O(1). Perhaps there is something I need to add in the Insert function of the AVL that will help me with this but will not change the complexity of the Insert of logn ? — TheNotMe, Sep 08 '12 at 13:20

pangon · Accepted Answer · 2012-09-08T20:34:12.643

You need to extend the data structure otherwise you cannot obtain a O(1) search of the minimum gap between the numbers composing the tree.

You have the additional constrain to not increase the time complexity of insert/delete/search function and I assume that you don't want to increase space complexity too.

Let consider a generic node r, with a left subtree r.L and a right subtree r.R; we will extend the information in node r additional number r.x defined as the minimum value between:

(only if r.L is not empty) r value and the value of the rightmost leaf on r.L
(only if r.L is deeper than 1) the x value of the r.L root node
(only if r.R is not empty) r value and the value of the leftmost leaf on r.R
(only if r.R is deeper than 1) the x value of the r.R root node

(or undefined if none of the previous condition is valid, in the case of a leaf node)

Additionally, in order to make fast insert/delete we need to add in each internal node the references to its leftmost and rightmost leaf nodes.

You can see that with these additions:

the space complexity increase by a constant factor only
the insert/delete functions need to update the x values and the leftmost and rightmost leafs of the roots of every altered subtree, but is trivial to implement in a way that need not more than O(log(n))
the x value of the tree root is the value that the function needs to return, therefore you can implement it in O(1)

The minimum gap in the tree is the x value of the root node, more specifically, for each subtree the minimum gap in the subtree elements only is the subtree root x value.

The proof of this statement can be made by recursion: Let consider a tree rooted by the node r, with a left subtree r.L and a right subtree r.R. The inductive hypothesis is that the roots of r.L and r.R x values are the values of the minimum gaps between the node values of the subtree. It's obvious that the minimum gap can be found considering only the pairs of nodes with values adjacent in the value sorted list; the pairs formed by values stored by the nodes of r.L have their minimum gap in the r.L root x value, the same is true considering the right subtree. Given that (any value of nodes in r.L) < value of L root node < (any value of nodes in r.R), the only pairs of adjacent values not considered are two:

the pair composed by the root node value and the higher r.L node value
the pair composed by the root node value and the lower r.R node value

The r.L node with the higher value is its rightmost leaf by the AVL tree properties, and the r.R node with the lower value is its leftmost leaf. Assigning to r x value the minimum value between the four values (r.L root x value, r.R root x value, (r - r.L root) gap, (r - r.R root) gap) is the same to assign the smaller gap between consecutive node values in the whole tree, that is equivalent to the smaller gap between any possible pair of node values. The cases where one or two of the subtree is empty are trivial. The base cases of a tree made of only one or three nodes, it is trivial to see that the x value of the tree root is the minimum gap value.

I did not understand two things. Will we be assigning this field (x) and the value of it when we do Insert? Plus, what do you mean by r value and the value of the rightmost leaf on r.L? You mean the minimum gap is between the two numbers "r value" and "rightmost leaf on r.L"? — TheNotMe, Sep 08 '12 at 14:37
Yes, the field "x" take extra space, but the additional space complexity is O(n) (a int for every of each n nodes) and giving that the standard AVL tree needs O(n) already, the space complexity doesn't increase (yes, undoubtedly it is needing more space, but the order of complexity is the same, O(n+n)=O(n)). The same for insert/delete time complexity: if you add computations for up to O(lon(n)) then the original O(lon(n)) time complexity will be the same. An implementation will surely take longer to execute, but only by a constant factor: the structure is not losing it scalability. — pangon, Sep 08 '12 at 14:42
The x values are added when the node is inserted in the tree and will, when needed, be updated by insert/delete of the other nodes. Yes, by "node value" I'm referring to the numbers from which you are building the tree. — pangon, Sep 08 '12 at 14:45
Very fantastic way. Thank you. But I am curious, how did you know that if (in this condition)->(min gap is between those two values) ? Is there a proof? — TheNotMe, Sep 08 '12 at 16:15
One thing though, this algorithm did not give me the what is the "minimum gap" possible between two numbers o.O — TheNotMe, Sep 08 '12 at 16:17
the minimum gap in the tree is the x value of the root node, more specifically, for each subtree the minimum gap in the subtree elements only is the subtree root x value. The proof is made by recursion, I'm going to add it in the answer — pangon, Sep 08 '12 at 20:13
Fantastic way, this shows that I have alot to learn. Thank you so much, and thanks alot for the proof! — TheNotMe, Sep 09 '12 at 14:26

score 0 · Answer 2 · answered Nov 07 '17 at 14:04

This function might be helpful for you:

int getMinGap(Node N)
    {
        int a = Integer.MAX_VALUE ,b = Integer.MAX_VALUE,c = Integer.MAX_VALUE,d = Integer.MAX_VALUE;
        if(N.left != null) {
            a = N.left.minGap;
            c = N.key - N.left.max;
        }

        if(N.right != null) {
            b = N.right.minGap;
            d = N.right.min - N.key;
        }

        int minGap = min(a,min(b,min(c,d)));

        return minGap;
    }

Here is the Node data structure:

class Node
{
    int key, height, num, sum, min, max, minGap;
    Node left, right;

    Node(int d)
    {
        key = d;
        height = 1;
        num = 1;
        sum = d;
        min = d;
        max = d;
        minGap = Integer.MAX_VALUE;
    }
}

Find the minimum gap between two numbers in an AVL tree

2 Answers2