必要なバランスの取れたツリーの種類を指定していません。たとえば、AVLツリーを使用できます
ノードの高値をカウントすると、ノード 13 の値が -2 で、18 の値が 1 でバランスが崩れていることがわかります。そのため、ノード 18 で右回転を行い、ノード 13 で左回転を行う必要があります。その後、ノードはバランスが取れた状態になります。
右回転後：
13
/ \
8 14
\
18
/ \
15 19
左回転後：
14
/ \
13 18
/ / \
8 15 19
あなたの値は8 13 14 15 18 19であるため、これらの値を持つバランスの取れたツリーは次のようになります。
15
/ \
13 19
/ \ /
8 14 18
このツリーを取得するために、値をカウントしてツリーの一般的な形状 (レイヤーを左から右、上から下に塗りつぶす) を取得し、値を並べ替えて、ツリー内で左から右に配置しました。
これは、ツリーのバランスを 1 回とる場合は優れたパフォーマンスを発揮しますが、挿入/削除のたびにツリーのバランスを取るために使用しないでください。
実際には、AVLツリーは挿入時にバランスが取られ、ノードがバランスを取る必要があるかどうかを確認し、末尾再帰を使用して挿入から戻る途中ですべてのバランスを取ります。ウィキペディアのAVL記事には、実際にはいくつかのまともなイラストもあります。
私は学生でもあり、avl ツリーを勉強しています。この質問では、ノード 13 の残高は -2 であり、これは avl 条件の違反です。この違反は、新しいノード 15 の挿入が原因で発生します。現在、avl に違反しているノード条件はそれを alpha と呼びましょう。ここで、挿入のケースを識別する必要があります。挿入のケースは次のとおりです。1) alpha の右側の子の右側のサブツリーへの挿入 (alpha は、バランス係数が avl 条件に違反しているノードです)。この場合、1 回の左回転が必要です。2) alpha の右側の子の左側のサブツリーへの挿入。この場合、右左回転である二重回転を行う必要があります。3) alpha の左側の子の右側のサブツリーへの挿入。この場合、左右の回転である二重回転を行う必要があります。4) alpha の左の子の左のサブツリーへの挿入。
あなたの質問では、これはケース 2 です。ツリーのバランスを取り直すために、右左回転を行う必要があります。alpha の右の子とその左のサブツリーの親の間で右の回転を行います。この後、アルファとアルファの新しい右の子 (アルファの右の子の左のサブツリーの親) との間で左の回転を行う必要があります。この左の回転の後、ルートが 14 のツリーができます。 13 は 13 の左の子は 8. 14 の右の子は 18 18 の左の子は 15 18 の右の子は 19 です。彼が投稿した図を見てください。これが役立つことを願っています。