1
$\begingroup$

Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree. I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as

(x > curr.key) && (x > curr.parent.key)

I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.

The claim is that the worst case complexity is always $O(\log k)$, for any $k$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $k > {n\over 2}$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find x in depth of $O(\log k)$.

Am I looking at this the wrong way?

Improve this question
$\endgroup$
3
  • $\begingroup$ "The claim is that ...". Can you add a url or reference to the place of that claim? $\endgroup$
    – John L.
    Dec 6 '18 at 19:44
  • $\begingroup$ It looks like you have understood the whole situation correctly except a minor glitch somewhere. By the way, if $n\ge k>n/2$, then $O(\log n)$ is $O(\log k)$ $\endgroup$
    – John L.
    Dec 6 '18 at 19:47
  • $\begingroup$ @Apass.Jack The claim was from my class... and no further information on that topic is provided, either. I understand your note, but still - climbing up the tree isn't done in a constant time, the height from the minimum is still $O (\log n)$. The technicality for bigger k's doesn't hold, it seems. So you're saying there's no way to achieve $O(\log n)$ without comparing with the root first? $\endgroup$
    – gbi1977
    Dec 6 '18 at 20:57
0
$\begingroup$

Yes, you might be looking it the wrong way.

If $x$ is larger than the tree's root's key (the median, or equivalently $k>n/2$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find $x$ in depth of $O(\log k)$.

First, let us be accurate. The root's key may not be the median, although it sits roughly in the middle.

Let $r$ be the root node. Let $n$ be the number of nodes in the whole tree and $n_l$ be the number of nodes in the left subtree of $r$. Let $h_l$ be the height of that subtree and $h$ be the height of the tree, so $h\le h_l+2$ since an AVL tree is height balanced.

Suppose $x$ is larger than the root's key. That means $$n_l < k \le n.$$ We also have, according to the properties of an AVL tree. $$\log_2 (n+1)\le h \le h_l+2 \le c\log_2(n_l+2)+b +2\lt c\log_2(k+2)+b +2$$ where $c\approx 1.44$, $b\approx -0.328$. So, for all $k\ge3$, $$\log_2(n)\le2\log_2(k)$$

So if you have traversed the entire (height) of the left branch in order find the $k$-th smallest element, you will use $O(\log n) = O(\log k)$ steps.

In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $k$-th smallest element, we have just proved that the worst case complexity is always $O(\log k)$

Improve this answer
$\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.