上の画像は、ウィキペディアが不均衡であると示している「AVLツリーに関するウィキペディアのエントリ」からのものです。この木はどうしてまだバランスが取れていないのですか？記事からの引用は次のとおりです。
ノードのバランス係数は、右側のサブツリーの高さから左側のサブツリーの高さを引いたものであり、バランス係数が1、0、または-1のノードはバランスが取れていると見なされます。他のバランス係数を持つノードは不均衡と見なされ、ツリーのバランスを取り直す必要があります。バランス係数は、各ノードに直接格納されるか、サブツリーの高さから計算されます。
左と右の両方のサブツリーの高さは4です。左のツリーの右のサブツリーの高さは3ですが、それでも4より1つ少ないだけです。誰かが私が欠けているものを説明できますか？
たとえば、ノード 76 は、右側のサブツリーの高さが 0 で左側のサブツリーの高さが 3 であるため、バランスが取れていません。
バランスをとるために、ツリー内のすべてのノードは、次のいずれかでなければなりません。
または、子が 1 つしかない場合、その子はリーフでなければなりません。
あなたが投稿したチャートでは、9、54、76 が最後のルールに違反しています。
適切にバランスを取ると、ツリーは次のようになります。
Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76
更新: (ほぼ 9 年後、draw.ioでグラフ用のクールなオンライン チャートを作成しました)
直感的には、できるだけ小さくないためです。たとえば、12 は 9 と 14 の親であるべきです。このままでは、9 には左のサブツリーがないため、バランスが崩れています。ツリーは階層的なデータ構造であるため、「バランス」などのルールは多くの場合、ルート ノードだけでなくすべてのノードに適用されます。
ルート ノードのバランスが取れていることは間違いありませんが、ツリーのすべてのノードがバランスが取れているわけではありません。