Tag: treap

为什么在排序输入上比随机输入更快插入我的树？

现在我总是听说二进制搜索树比随机数据更快地构建，而不是有序数据，因为有序数据需要显式重新平衡以保持树高最小。 最近我实现了一个不可变的treap ，一种特殊的二叉搜索树，它使用随机化来保持自己相对平衡。 与我的预期相反，我发现我可以持续建立一个快速约2倍的treap，并且通常比有序数据更好地平衡 – 而且我不知道为什么。 这是我的treap实现： http://pastebin.com/VAfSJRwZ 这是一个测试程序： 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 rndTimes = new List(); List orderedTimes = new List(); rndTimes.Add(TimeIt(50, RandomInsert)); rndTimes.Add(TimeIt(100, RandomInsert)); rndTimes.Add(TimeIt(200, RandomInsert)); […]