java - 最大高さ2～3本の木

Question

2-3 ツリーの最大の高さを見つけるには、ルート ノードからその左側の子ノードまでトラバースし続け、葉に突き当たるまでずっと下っていくことができますか?

これは事実です。すべてのリーフノードが同じ高さにあるため、任意のポイントで最も低いリーフがツリーの最大の高さになります。(すべてのリーフノードは同じレベルにあります)。

左に進み続けると、必ず底に着きますか?

Answer 1

2 ～ 3 本のツリーはバランスが取れていることに注意してください。つまり、各サブツリー (左、中央、右) にはほぼ同じ量のデータが含まれます。このステートメントを考慮すると、葉ノード (いずれかのサブツリー) は、2-3 ツリーの高さを示します。

木のバランスにより、すべての操作が になる傾向があるとも言えますO(lg n)。

更新：

2-3 ツリーは、ヌル ツリー (ノードがゼロ)、単一ノード ツリー (ノードが 1 つだけ)、または次のプロパティを持つ複数ノード ツリーです。

1. 各内部ノードには 2 つまたは 3 つの子があります
2. ルートからリーフまでの各パスの長さは同じです。

IISc CS 部門から: http://lcm.csa.iisc.ernet.in/dsa/node118.html