ウィキペディアの記事を信じる: http://en.wikipedia.org/wiki/AVL_tree
AVL ツリーは高さのバランスがとれていますが、一般に、重みのバランスも μ のバランスもありません [4]。つまり、兄弟ノードは、非常に異なる数の子孫を持つことができます。
ただし、AVL ツリーは次のとおりです。
自己均衡二分探索木[...]。AVL ツリーでは、任意のノードの 2 つの子サブツリーの高さの差は最大で 1 です。
AVLツリーの定義をよく理解していれば、すべての兄弟は同じ高さ+/- 1であるため、ほぼ同じ数の子を持つことになるため、AVLがどのように重みの不均衡になるかわかりません。
アンバランスな AVL ツリーの例を教えてください。私はそれを見つけることができませんでした。したがって、またはAVL/重み付けされていないツリーの定義を誤解したか、ウィキペディアの記事が間違っています...
ありがとう
兄弟ノードは、非常に異なる数の子孫を持つことができます。
私はこれと、私の AVL 実装が最終的に偏っていないツリーを生成したという事実について、頭を悩ませていました。
私は自分自身を安心させるためにこれをスケッチしました：
赤のノードのバランスは 1、緑のノードは -1、黒のノードは 0 です。これは、2 つの兄弟サブツリー間の高さの差が 1 を超えることはないという点で有効な AVL ツリーですが、(ほぼ) 2 倍あります。右側のサブツリーの多くのノードを左側のサブツリーとして。
AVL ツリーはエッジ ノードのほぼ均一な高さによって定義されるという理解は正しいですが、ノードの位置とエッジの重みの違いについて混乱しているようです。
つまり、AVL ツリーでは、エッジ ノードの深さは同じ +/- (両方ではない!) になります。これは、ノード間のエッジに関連するコストについて主張するものではありません。ルート ノードと 2 つの子を持つ AVL ツリーの場合、左側のパスは右側のパスの 2 倍のコストがかかる可能性があります。これにより、ツリーの重みがアンバランスになりますが、AVL ツリーの定義は維持されます。
このページにはより多くの情報があります: Weight-balanced tree - wikipedia
ウィキペディアから:
バイナリ ツリーは μ-balanced と呼ばれ
、ノード N ごとに次の不等式があります。
が成立し、μ はこの性質で最小になります。|N| は、N をルート (ルートを含む) とするツリーの下のノードの数であり、Nl は N の左側のサブツリーです。
基本的に、これは、AVL ツリーの子がツリーの最下位レベルに均等に分散されているとは限らないことを意味します。ツリーのルート ノードを示す N を使用すると、ルートの右側よりも左側に多くの子を持つ有効な AVL ツリーを構築できます。非常に深いツリーでは、この最下位レベルに多くのノードが存在する可能性があります。
AVL ツリーの定義では、すべてが最も深いポイントの 1 つに含まれている必要がありますが、ノード N に関してどのノードの子であるかは保証されません。
