スプレイツリー最悪検索時間

Question

スプレー木がアンバランスな二分探索木（brilliant.org/wiki/splay-tree）の一種であるので、それはほとんどのO（（n）を対数）での高さを保証することはできません。したがって、O（log（n））の最悪の場合の検索時間を保証することはできないと考えています。

しかしbigocheatsheet.comに従って：

スプレイツリーはO（ログ（N））の最悪の場合の検索時間を持っています？

Answer 1

正しいですか。スプレイツリー内のルックアップのコストは、不均衡なツリーの場合、Θ（n）に達する可能性があります。

big-Oチートシートのような多くのリソースは、仮定を単純化するか、事実上間違ったデータを持つだけです。ここで間違っているのか、償却された最悪の場合など話しているのかは不明です。

ランタイムがどこから来たのか理解できるように、作業しているデータ構造の内部を知ることが常にベストです。