问个2-3-4树的问题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

问个2-3-4树的问题。

问个2-3-4树的问题。# Programming - 葵花宝典

e*r2008-03-27 07:03

1 楼

看到关于2-3-4树的一个property: "Searches in N-node 2-3-4 tree visit at most
lgN+1 nodes."
我可以理解2-3-4树的高度at most是lgN+1,但不肯定visit过的node数目，因为对一个3
node或者4-node, 查找的时候需要访问的node数目可能超过一个，这时候也许树高减
少了，此消彼长，然后还是保持了lgN+1的upper bound.
想请教前辈们一个更rigid一点的解释。

s*u2008-03-27 07:03

2 楼

觉得说的不一定是严格的lgN+1，是数量级
就像普通说的B+最多访问多少个节点一样
一个节点内定位下一个节点可以binary search的

most
个3

【在 e***r 的大作中提到】

: 看到关于2-3-4树的一个property: "Searches in N-node 2-3-4 tree visit at most
: lgN+1 nodes."
: 我可以理解2-3-4树的高度at most是lgN+1,但不肯定visit过的node数目，因为对一个3
: node或者4-node, 查找的时候需要访问的node数目可能超过一个，这时候也许树高减
: 少了，此消彼长，然后还是保持了lgN+1的upper bound.
: 想请教前辈们一个更rigid一点的解释。