Dynamic Binary Search

Note that I do not want any code for this problem, just any references or help about how this data structure really works so that I can do my task.

I want to execute the operations for finding and inserting a value in a set of n numbers. The whole point is to use dynamic binary search, and use more than one so开发者_开发百科rted arrays.Let's say k=[log(n+1)] and <n(k-1),n(k-2),...,n(0)> is the binary representation of n. We have k sorted arrays

A(0),A(1),...,A(k-1)

where for i=0,1,...k-1 of each A(i), the size of each array is 2^i.

Each array is full or empty whether n(i)=1 or n(i)=0. Although each array is sorted, there is not any relation between elements in different arrays.

If anyone has a clue about this, could you help me?

Again, I only want more info about this data structure, any links or references that could help me. I don't want any code.

---

Here is some suggested reading http://en.wikipedia.org/wiki/Splay_tree