树结构

可持久化数据结构 可持久化数据结构上的运算在修改自身时(比如插入、删除这样的运算)，会先记录一个改变前的状态作为历史版本，这个历史版本往往是可继续查阅和修改的。可持久化数据结构按“持久化程度”可分2大类： 1) 部分持久化数据结构：所有历史版本都可供查询，但只能基于最新版本修改数据； 2) 完全可持久化数据结构：所有历史版本都可查询修改； 通常来说设计可持久化数据结构的主要思想是“拷贝部分原有内容+复用部分原有内容”。所以可持久化数据结构的空间复杂度会介于“非可持久化数据结构”和“每次修改前完整克隆当前版本”这两种情况之间。下面就来讨论如何基于Treap构建可持久化的平衡树，这里需要引入一个称为无旋Treap的数据结构，因为“可持久化+旋转”比较难一起处理。   无旋Treap  (a)   (b)… 阅读全文