B树中元素计数的大O是多少
例如，如果我有一棵树，其节点具有以下结构：
{ type: 'document' } or {type: 'note'}
如果我想要计算具有类型的所有节点的计数，请注意对于 B 树来说，计数大 O 是什么？
For example if I have a tree which nodes have a structure:
{ type: 'document' } or {type: 'note'}
If I wanted a count of all nodes that have type note what would be count big O for a B tree?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
可以在线性时间 -Ie
o（n）中完成b -tree的遍历。这是因为每个n个节点都应避开一次。
您将在每个节点中花费一个持续时间（检查节点的类型并增加计数器，不取决于树的大小） - 那是
o（1）。因此，总体复杂性应仍然是线性 -
o（n）。Traversal of a B-tree can be done in linear time - i.e.
O(n).This is because each of the n nodes should be visted once.
You will spend a constant time in each node (checking the type of the node and incrementing a counter, doesn't depend on the size of the tree) - that's
O(1).Therefore the overall complexity should be still linear -
O(n).