动态二进制搜索 [英] Dynamic Binary Search

问题描述

请注意，我不希望任何code对于这个问题，只是任何参考或
帮助这个数据结构如何工作，这样我可以做
我的任务。

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.

我要执行的操作的一组找到并插入值
n个数字。整点是使用动态二进制搜索，并使用
多个分类arrays.Let说 K = [日志（N + 1）] 和＆LT; N（K-1），N（K -2），...，N（0）＆GT;
为的二进制重新presentationñ。我们有 K 排序阵列

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 sorted 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)

其中的 I = 0,1，... K-1 每个 A（I）中，每个数组的大小是 2 ^ I 。

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

每个数组为满或空是否 N（I）= 1 或 N（I）= 0 。
尽管每个阵列进行排序，没有任何关系
在不同的数组中的元素。

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?

再次我只是想了解这种数据结构，任何链接更多信息
或引用，可以帮助我。我不希望任何code。

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

推荐答案

下面是一些建议的阅读的http：/ /en.wikipedia.org/wiki/Splay_tree

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

这篇关于动态二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！