2

ランダム-BST/赤黒木と他のいくつかの木の高さを知るようになりましたO(log n)。

どうしてこれができるのだろうか。私はこのような木を持っているとしましょう

二分木

木の高さは基本的に木の深さであり、この場合は4（親の深さを残して）なります。O(log n)しかし、高さは概念で表すことができると人々はどのように言うことができますか？

私はアルゴリズムに非常に興味があり、この点は私を非常に混乱させています。私はどこでポイントを逃していますか？

4

2 に答える 2

2

アルゴリズムの複雑さでは、変数nは通常、コレクション内のアイテムの総数、または何らかの計算に関与するアイテムの総数を指します。この場合、nはツリー内のノードの総数です。だから、あなたが投稿した写真でn=31。木の高さがである場合、それは木O(log n)の高さがの対数に比例することを意味しますn。これは二分木なので、ログベース2を使用します。

⌊log₂(31)⌋ = 4

したがって、木の高さは約4にする必要があります。これは、この例の場合とまったく同じです。

于 2012-09-09T04:06:08.203 に答える
1

コメントで説明したように、二分木には複数のケースがあります。

  • 縮退した場合、二分木は単なるチェーンであり、その高さはO（n）です。
  • 最良の場合（ほとんどの検索アルゴリズムの場合）、完全な二分木には、どのノードでもサブツリーの高さが同じであるという特性があります。この場合、長さはlog（n）のフロアになります（kブランチの場合は基数2、または基数k）。これは、ツリーのサイズの帰納法（コンストラクターでの構造的帰納法）によって証明できます。
  • 一般的なケースでは、これらが混在し、ノードに高さが異なる可能性のあるサブレスがある場所にツリーが構築されます。
于 2012-09-09T04:14:16.557 に答える