- 博客(132)
- 收藏
- 关注
RSS订阅
1原创 五、平衡二叉树——伸展树Splay
treep伸展树由于数据存在局部性原理，刚刚访问过的数据有很大可能在短时间内被再次访问，其相邻结点被访问的可能性也会提高。为了提高局部性查询的效率，伸展树诞生了。伸展树的原理伸展树在每次查询完一个数据后就将该数据对应的结点旋转至树根，在旋转的同时保持树的搜索性不变（中序遍历不变）。于是下次在查询相同的数据或是相邻的数据时，时间就会大大缩短。伸展树在总体上的均摊效率为O(logn)，m次查询的复杂度为O(mlogn)实现细节由于无需保持整棵树的平衡，伸展树的结点只需要记录左右子树和父结点的信息即
2022-07-27 10:33:52
267
原创 凑零钱（动态规划）
题面：韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。
2022-07-06 17:19:55
455
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人