几何搜索树

文章介绍了G-trees，一种随机化的、与历史无关的搜索树数据结构。G-trees包含了几种独立发现的数据结构，如zip-trees、zip-zip-trees和dense skip-trees。G-trees家族还包含了新的arity大于2的树，它们在存在缓存层次结构或块存储的情况下比zip-trees效率更高。文章还介绍了用于操作G-trees的有效算法，包括插入、删除、zipping和unzipping。