- Streap是一种简单的平衡树实现
- 主要操作只用左旋和右旋
- 它同时也是一个堆的结构
- 概率分布是一个非常有趣的东西，这是我第一个接触到的，通过随机来维护的数据结构（利用随机来退伙或者避免局部最优不算
- 利用随机值，避免了大量的深度的维护，减少了代码的实现复杂度
- 时间复杂度是不会被刻意制造的数据导致退化的，和spaly和快排不一样
- 堆是一个非常优雅的算法，但是删除操作需要非常小心地维护和实现
- 现在使用高级算法实现的时候，我喜欢直接用指针，而不是特定的数组下标关系。下标的计算看起来节省了代码的实现复杂度和提升了效率，但是它损害了代码的可读性
- 我觉得这是一个优雅的算法，就是实现简单，道理清晰，脆弱性低
- 但是Streap还是有局限。对于树的合并，需要重新构建。并且，有极小的概率会导致树的深度非常大。和splay比，不能最大化提高实际中的效率
网友评论