AVLツリーが常にO（log（n））検索を保証できる方法

Question

私はそれが愚かな質問であれば申し訳ありません。 AVLツリーには検索のためのO（log（n））があると聞きましたが、どのようにしてlog（n）検索が常に保証されるのか理解できません。

Answer 1

AVLツリーは、すべてのノードの子サブツリー間に常に最大1つのレベル差がある自己均衡ツリーです。 BSTの高さは検索時間に影響します。線形のn個のノードを持つBSTがあるとします。 log（n）ではなくnの高さを持ちます。この場合、探索時間の複雑さはO（n）である（不均衡な木の最悪の場合）。つまり、木の高さをlog（n）として制御することでlog（n）検索時間を保証する木を作ることもできるということです。