2

私はRobert SedgewickによるC ++のアルゴリズムに取り組んでおり、次のステートメントに出くわしました:

内部ノードを持つ二分木の高さはN、最低lg N でも最高でもN-1です。最良のケースは2^i 、最下位レベルを除くすべてのレベルに内部ノードがあるバランスの取れたツリーで発生します。高さが「h」の場合、

         2^(h-1) < N+1 <= 2^h

N+1 個の外部ノードがあるためです。

不等式についてはあまり説明がなかったので、私の質問は次のとおりです。著者は不等式をどのように推定したのか、それは正確には何を示しているのでしょうか?

ありがとう！

4

2 に答える 2

2

この不等式2^(h-1) < N + 1 <= 2^hは、特定の高さに対して、最小の高さが共通hするノード量の範囲があることを示しています。hこれはプロパティを示しています。N 個のノードを含むすべてのバイナリ ツリーは、次の整数に切り上げられた少なくとも log( N ) の高さになります。

たとえば、いずれかの4, 5, 6 or 7ノードを持つツリーの最小の高さはせいぜい です3。この範囲より 1 つ小さいと、高さのツリーを持つことができます2。もう 1 つ、あなたができる最善のことは の高さです4。Nの 2 を底とする対数を使用してノードから3ノードへと成長するツリーの最小の高さをマッピングし、切り上げると、不等式が明らかになります。8

log(3) = 1.58 -> 2  [lower bound]

log(4) = 2    -> 3  [2^(h-1)]
log(5) = 2.32 -> 3
log(6) = 2.58 -> 3
log(7) = 2.81 -> 3

log(8) = 3    -> 4  [2^h | upper bound]

N+1範囲 (さまざまな量で構成される) は、特定のツリーの外部ノードの数に直接関係していることに注意してください。3ノードを持ち、高さがのツリーを取得し2ます。

     *
    / \
   *   *

このツリーにノードを 1 つ追加し、

    *          *          *          *
   / \        / \        / \        / \
  *   *  or  *   *  or  *   *  or  *   *
 /            \            /            \
*              *          *              *

配置場所に関係なく、高さは 1 ずつ増加します。その後、ツリーに合計 7 つのノードが含まれるまで、高さを変更せずにリーフ ノードを作成し続けることができます。この時点で、さらに追加すると、可能な最小の高さがもう一度増加します。 :

    *
   / \
  *   *
 / \ / \
*  * *  *

もともと、N3はノードに等しいことを意味し、共通の最小高さを持つ数量がN+1 = 4あることがわかりました。4

さらに詳しい情報が必要な場合は、完全でバランスのとれた二分木の特性を調べることをお勧めします。

于 2012-09-21T19:25:33.660 に答える
0

N二分木にノードを収めるのに必要な最小の高さを呼びましょうminheight(N)。

特定の数のノードに対するツリーの高さの下限を導き出す 1 つの方法はN、別の方向から作業hすることです。

この関数を height と呼びましょうmaxnodes(h)。明らかに、特定の高さのバイナリ ツリーのノード数は、ツリーがいっぱいになると最大になります。つまり、各内部ノードに 2 つの子がある場合です。誘導はすぐにそれを示しmaxnodes(h) = 2^h - 1ます。

したがって、Nノードがある場合、すべてhの formaxnodes(h) >= Nはの上限です。つまり、その高さの木にminheight(N)すべてのノードを収めることができます。Nこれらすべての上限のうち、最良の (最も厳しい) 上限が最小になります。したがって、私たちが見つけたいのはh、

N <= maxnodes(h) = 2^h - 1

では、 のこの最小の満足値を見つけるにはどうすればよいhでしょうか?

の重要な特性maxnodes(h)は、それが wrt に関して非減少であることですh(実際には厳密には増加していますが、非減少で十分です)。これが意味することは、高さを減らすことによって完全なバイナリ ツリーにノードを追加することは決してできないということです。(当たり前のことですが、ときどき詳しく説明すると役立つことがあります!) これにより、上記の式を並べ替えて の最小値をh簡単に見つけることができます。

2^h - 1 >= N
2^h >= N+1        # This is the RHS of your inequality, just flipped around
h >= log2(N+1)    # This step is only allowed because log(x) is nondecreasing

hhは整数でなければならないので、満たす最小値h >= log2(N+1)は ですRoundUp(log2(N+1))。

これは下限を説明する最も便利な方法だと思いますが、質問している不等式の LHS を導出するために使用できます。前のブロックの 2 番目の方程式から始めます。

2^h >= N+1

この不等式を満たす値のセットは、正の無限大からh始まり、h = log2(N+1)正の無限大まで伸びます。h = log2(N+1)はこのセットの最小満足値であるため、それより低い値は不等式を満たさないはずh-1です。>=2 つの実数 (無限でない) の間に不等式が成立しない場合、対応する<不等式が成立する必要があるため、次のようになります。

2^(h-1) < N+1
于 2012-09-22T07:24:56.413 に答える