[Solved]: finger search on a red black tree

Problem Detail: 

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.

Asked By : aviran

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14291

 Ask a Question

 Download Related Notes/Documents