# finger search on a red black tree

I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree.

Even Wikipedia has a very short page about that, could you refer me or explain what kind of search is that.

• Trying using a search engine. – Yuval Filmus Sep 13 '13 at 17:26
• You could help by adding what you know about finger search in general. – Raphael Sep 16 '13 at 7:29

One of the basic operations supported by trees is searching for elements. A balanced binary tree (for example, a red-black tree) supports search in $O(\log n)$ time, where $n$ is the number of elements. In some scenarios, the elements we are searching for are close to one another, and finger search allows taking advantage of that. After having just searched the $j$th largest element, searching the $i$th largest elements only takes time $O(\log |i-j|)$. So scanning through all the elements in order would only take $O(n)$ time rather than $O(n\log n)$.
• That's the same thing: $d = |i-j|$ is the distance between the current item and the previous one. – Yuval Filmus Sep 15 '13 at 4:02