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.

  • $\begingroup$ Trying using a search engine. $\endgroup$ – Yuval Filmus Sep 13 '13 at 17:26
  • $\begingroup$ You could help by adding what you know about finger search in general. $\endgroup$ – 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)$.

Finger search can be implemented using several different data structures. In particular, it can be implemented using balanced binary trees such as red-black trees.

For more on finger search, check out a research proposal by Maverick Woo and a book chapter by Gerth Stølting Brodal.

  • $\begingroup$ I think you're talking about selection, the 'finger search' I'm trying to understand involves traveling along the right/left most path of the tree and finding the node in O(log d) time. d supposed to be the distance... $\endgroup$ – aviran Sep 14 '13 at 5:38
  • 1
    $\begingroup$ That's the same thing: $d = |i-j|$ is the distance between the current item and the previous one. $\endgroup$ – Yuval Filmus Sep 15 '13 at 4:02

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.