アンバランスなAVLツリーの種類を見つける方法は？

Question

私はAVLツリーコードを書いていますが、私のツリーがアンバランスであるかどうかを調べるコードを書いて、アンバランスなタイプを見つけ出すにはどうすればいいですか？左から左、右から左、右から右に右か？

Answer 1

通常はDFS traversalを、各ノードではmax height of the left subtreeとmax height of the right subtreeを見つけることができます。

次に、ノードがすべてabs(height_left - height_right) <= 1の場合、ツリーのバランスが取れます。

不均衡なツリーのタイプ（ツリーを修正するために必要な回転のタイプを意味すると思います）を見つけるには、左右の子ポインタを使用して回転のタイプを推測する必要があります。