【BZOJ2733】【HNOI2012】永无乡

平衡树启发式合并

又get了新知识:set/tree中++的效率是\(O(1)\)的

另外好像本来平衡树的遍历就是\(O(n)\)的

2
说点什么

1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

红黑树单次查前驱后继的效率是$O(log_n)$的!!!
遍历整棵树是$O(n)$。

红黑树具体参见:http://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html
找前驱/后继是一个贪心的过程。以找后继为例,求某个非叶子节点的后继,先走到自己的右儿子,然后不停地往左边走,走到叶节点即为后继。

由于树高$O(log_n)$,所以单次查前驱后继O(log_n)。

然而遍历整棵树是$O(n)$的。因为直接中序遍历一番。