ウィキペディアのアンバランスAVLツリーの例は、実際にどのようにアンバランスですか？

Question

上記の画像は、＆quot; WikipediaのAVLツリーに関するエントリ＆quot; からのものです。不均衡。 このツリーはすでにバランスが取れていませんか？ 記事からの引用です：

  

ノードのバランス係数は、その右サブツリーの高さから左サブツリーの高さを引いたもので、バランス係数1、0、または-1のノードはバランスが取れていると見なされます。他のバランス係数を持つノードはアンバランスであると見なされ、ツリーのバランスを再調整する必要があります。バランス係数は、各ノードに直接保存されるか、サブツリーの高さから計算されます。

左と右のサブツリーの両方の高さは4です。左のツリーの右のサブツリーの高さは3ですが、それでも1だけ4未満です。

Answer 1

バランスをとるには、ツリー内のすべてのノードがどちらかである必要があります。

• 子を持たない（＆quot; leaf＆quot;ノードになる）
• 2人の子供がいます。

• または、子が1つしかない場合、その子は葉でなければなりません。

  投稿したグラフでは、9、54＆amp; 76最後のルールに違反しています。

適切にバランスが取れていれば、ツリーは次のようになります。

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

更新：（ほぼ9年後、 draw.io ）

Answer 2

ノード76は、たとえば、右のサブツリーの高さが0で、左の高さが3であるため、バランスが取れていません。

Answer 3

直感的に、それは可能な限り小さくないからです。たとえば、12は9と14の親である必要があります。現状では、9には残りのサブツリーがないため、バランスが取れていません。ツリーは階層的なデータ構造であるため、「balanced」などのルールは、多くの場合、ルートノードだけでなくすべてのノードに適用されます。

ルートノードはバランスが取れていますが、ツリーのすべてのノードがバランスしているわけではありません。

Answer 4

これを見る別の方法は、ノードの高さ h が次のように与えられることです：

h = 1 + max（left.height、right.height）

ノードは次の場合に不均衡になります：

abs（left.height-right.height）＆gt; 1

上のツリーを見る：

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

ノード9のバランスが取れているかどうかを判断するには、その子の高さを確認します。

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

ノード9のバランスが取れていないことを示すために解決します。

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

他のすべてのノードに対して同様の計算を行うことができます。