e***r
发帖数: 68 | 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****u
发帖数: 118 | 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一点的解释。
|
|
