java - 最大高度 2-3 树

Question

要找到一棵 2-3 树的最大高度，你能不能一直从根节点遍历到它的左子节点，一直向下直到遇到叶子？

这是事实：由于所有叶节点的高度相同，因此任何点的最低叶都是树的最大高度。（所有叶节点都在同一级别）。

如果你继续向左走，你总是到达底部吗？

Answer 1

请注意，2-3 棵树是平衡的，这意味着每个子树（左、中、右）将包含接近相同数量的数据——考虑到这个陈述，我们可以假设遍历到叶节点（在任何sub-tree) 将为您提供 2-3 树的高度。

由于树的平衡，我们也可以说所有的操作都趋向于O(lg n)。

更新：

2-3 树是空树（零节点）或单节点树（只有一个节点）或具有以下属性的多节点树：

1. 每个内部节点有两个或三个孩子
2. 从根到叶子的每条路径都具有相同的长度。

来自 CS 部门，IISc： http: //lcm.csa.iisc.ernet.in/dsa/node118.html