现在我总是听说二进制搜索树比随机选择的数据更快地构建,而不是有序数据,因为有序数据需要显式重新平衡以保持树高最小.
最近我实现了一个不可变的treap,一种特殊的二叉搜索树,它使用随机化来保持自己相对平衡.与我的预期相反,我发现我可以持续建立一个快速约2倍的treap,并且通常比有序数据更好地平衡 - 而且我不知道为什么.
这是我的treap实现:
这是一个测试程序:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static Random rnd = new Random();
const int ITERATION_COUNT = 20;
static void Main(string[] args)
{
List<double> rndTimes = new List<double>();
List<double> orderedTimes = new List<double>();
rndTimes.Add(TimeIt(50, RandomInsert));
rndTimes.Add(TimeIt(100, RandomInsert));
rndTimes.Add(TimeIt(200, RandomInsert));
rndTimes.Add(TimeIt(400, RandomInsert));
rndTimes.Add(TimeIt(800, RandomInsert));
rndTimes.Add(TimeIt(1000, RandomInsert));
rndTimes.Add(TimeIt(2000, RandomInsert));
rndTimes.Add(TimeIt(4000, RandomInsert));
rndTimes.Add(TimeIt(8000, RandomInsert));
rndTimes.Add(TimeIt(16000, RandomInsert));
rndTimes.Add(TimeIt(32000, RandomInsert));
rndTimes.Add(TimeIt(64000, RandomInsert));
rndTimes.Add(TimeIt(128000, RandomInsert));
string rndTimesAsString = string.Join("\n", rndTimes.Select(x …任何人都可以提供真正的例子,说明何时存储数据的最佳方式是什么？
我想了解哪种情况下treap会比堆和树结构更好.
如果可能的话,请提供一些实际情况的例子.
我试图在这里搜索使用treaps的情况,并通过谷歌搜索,但没有找到任何东西.
谢谢.
有一个名为treap的数据结构:这是一个随机二进制搜索树,它也是随机生成的所谓"优先级"的堆.
这种结构存在一种变体,其中键是隐式的,它们不存储在树中,但我们将树中节点的有序索引视为此节点的键.我们需要在每个节点中存储子树的大小而不是密钥.这种技术使我们能够像某种数组一样思考treap,它在O(log N)时间内支持大量操作:子数组的插入,删除,恢复,间隔的变化等等.
我对这种结构有点了解,但没有那么多.我试图谷歌它,但我发现很多关于treap本身的文章,但没有关于这个"隐含的treap"/"索引列表".我甚至不知道它的名字,因为我的母语不是英语,我听过的讲座使用的是结构的本土术语,而不是英文原始术语.这个原生术语可以直接用英语翻译为"隐式键上的Treap"或"隐式键上的笛卡尔树".
任何人都能指出我关于这个结构的文章或告诉我它的原始名称吗？谢谢.
PS对不起,如果我的英语不够容易理解.
UPD:关于我正在寻找的结构的一些额外解释.
考虑使用随机选择的优先级和密钥的常用treap,它们是存储在树中的实际用户数据.然后让我们假设我们在每个节点中都存储了一些其他用户信息,而键只是搜索键.下一步是计算和维护每个节点中的子树大小:我们必须在每次合并/拆分/添加/删除后更新此参数,但它允许我们在O(log N)中查找树的第K个元素时间.
当我们在每个节点中有子树大小时,我们可以抛弃键并想象treap表示inorder遍历中的用户数据数组.可以从子树大小容易地计算每个元素的数组索引.现在我们可以添加/删除数组中间的元素或拆分此数组 - 所有这些都在O(log N)时间内完成.
我们也可以进行"多重"操作 - 例如,为我们的"数组"的所有元素添加一个常量值.为了实现这一点,我们必须延迟此操作,在每个节点中添加一个参数,该参数表示延迟常量,必须"稍后"添加到此节点的子阵列的所有元素,并将更改"推"到必要.向子阵列添加常量或绘制(标记)子阵列可以通过这种方式延迟,因为反转子阵列(此处节点中的延迟信息位"子阵列必须反转"),依此类推.
UPD2:这是代码片段 - 我发现的一小部分信息.不要注意西里尔语:)单词"снеявнымключом"的意思是直接翻译"with implicit key".
我必须编写一个字典程序作为数据结构和算法本科课程的学期项目,我期望找到最合适的问题解决方案(数据结构).
我考虑过使用哈希表或者trie.有人建议我使用treaps,但还没有能够查看它们.
我的数据库有大约10万个不同的单词及其含义.该程序预期提供的基本功能是插入,更新,删除和搜索单词/定义.如果我设法挤压自动完成和拼写纠正,这将是一个额外的奖励.
所以,我的问题是,牢记我的要求,哪种数据结构最适合我的目的.当我说'最好'时,我要求的数据结构具有最佳的运行时复杂性和低成本(内存要求).
此外,我希望能够有一个算法,它返回以给定前缀开头的所有单词.例如,说我做一个函数调用dictionary.getWordsStartingWith("fic")它应该返回的,与开始的所有单词的列表fic,例如fiction,fictitious,fickle等我知道我能做到这一点,如果我实现了我的字典作为一个线索,我能做到这一点,但是这是可能的用哈希表做到这一点？
在什么样的情况下，treap 是使用的最佳数据结构？我一直在寻找这方面的答案，但还没有真正找到任何具体的东西。
还有另一个stackoverflow问题询问何时使用 treap 但那里没有给出真实世界的例子。
最常见的优点似乎是它们比例如红黑树更容易实现，但几乎每个人都使用预先编写的实现，所以它似乎并不相关。