2
$\begingroup$

For example, consider an AVL tree:

enter image description here

Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, and their absolute difference will always be greater or equal to that of the result:

$|c_1-c_2|\leq |o_1-o_2|$, where $c_i$ are the two closest elements, and $o_i$ are any other two elements in the three.

I'm trying to think of an algorithm for this that can be done is O(log n). I can modify the nodes to store additional information, but not sure what I could use.

Specifically the algorithm, I am not sure about. Visually its evident, but algorithm wise I would like a hint.

$\endgroup$
1
$\begingroup$

In most common models of computation, it cannot be ensured to find the two closest elements in a binary search tree (BST) in $O(\log n)$ time or, in fact, in $o(n)$ time. Here $n$ is the number of elements in BST and $o(n)$ is the little $o$-notation.

The idea is simple. There must be enough running time for an algorithm to access at least about half of the elements.

Here is an detailed explanation. It is not rigorous; to make it rigorous we will need an explicit adversary argument as well as a more detailed formal specification of the model of computation.


Let us fix some model of computation $M$ in which at most $c$ elements can be accessed in a unit time of computation for some constant $c$. In fact, $c$ is usually 1 or 2.

For the sake of contradiction, suppose algorithm $Alg$ can find the two closest elements in a BST of $n$ element in $o(n)$ time. So for constant $\dfrac1{3c}$, there exists a constant $n_0>0$ such that $A$ can find the two closest element in no more than $\dfrac1{3c}n$ time for all $n>n_0$.

Now let $n_1>\max(n_0, 6)$. Let $Alg$ runs on a BST with $n_1$ nodes for some time that is no more than $\dfrac1{3c}n_1$. Then $A$ has accessed at most $\dfrac{1}{3c}n_1\cdot c=\dfrac {n_1}3$ elements. Let $a_1, a_2, \cdots, a_{n_1}$ be the elements in the BST in nondecreasing order. There must be at least 2 adjacent elements in that nondecreasing list of all elements none of which have been accessed by the algorithm. Those two elements mights be closer to each other than any pair of elements among the elements that have been accessed by $Alg$. That means, $Alg$ may not have found the two closest elements. This is a contradiction.


Exercise. Find the two closest elements in a binary search tree with left-child pointers, right-child pointers and parent pointers in $O(1)$ working space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.