算法笔记 - streap

  • Streap是一种简单的平衡树实现
  • 主要操作只用左旋和右旋
  • 它同时也是一个堆的结构
  • 概率分布是一个非常有趣的东西，这是我第一个接触到的，通过随机来维护的数据结构（利用随机来退伙或者避免局部最优不算
  • 利用随机值，避免了大量的深度的维护，减少了代码的实现复杂度
  • 时间复杂度是不会被刻意制造的数据导致退化的，和spaly和快排不一样
  • 堆是一个非常优雅的算法，但是删除操作需要非常小心地维护和实现
  • 现在使用高级算法实现的时候，我喜欢直接用指针，而不是特定的数组下标关系。下标的计算看起来节省了代码的实现复杂度和提升了效率，但是它损害了代码的可读性
  • 我觉得这是一个优雅的算法，就是实现简单，道理清晰，脆弱性低
  • 但是Streap还是有局限。对于树的合并，需要重新构建。并且，有极小的概率会导致树的深度非常大。和splay比，不能最大化提高实际中的效率
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容