AVL ツリーはバランス型二分探索ツリーです。この投稿では二分探索ツリーが紹介されました。バイナリ ツリーの検索、挿入、削除にかかる時間は、ツリーの高さによって異なります。最悪の場合、高さは O(n) になります。木が 完全にバランスがとれている、つまり完全な二分木である場合、その高さは log n です。完璧にバランスの取れた木を維持できるでしょうか?はい、しかしそうするとコストがかかります。妥協案は、バランスのとれたツリーを維持することです。つまり、すべてのノードの 2 つのサブツリーの高さがほぼ同じになります。

AVL ツリー はバランスが取れています。 AVL ツリーは、1962 年に 2 人のロシアのコンピューター科学者、G. M. Adelson-Velsky と E. M. Landis によって発明されました (そのため AVL という名前が付けられました)。 AVL ツリーでは、すべてのノードの 2 つのサブツリーの高さの差は 0 または 1 です。 AVL ツリーの最大の高さは O(log n).

AVL ツリーで要素を挿入または削除するプロセスは、挿入または削除操作の後にツリーのバランスを再調整する必要がある場合があることを除いて、通常の二分探索ツリーと同じです。ノードの バランス係数 は、右側のサブツリーの高さから左側のサブツリーの高さを引いたものです。バランス係数が -1、0、または 1 の場合、ノードは バランスであると言われます。ノードは、バランス係数が -1 の場合は left-heavy とみなされ、バランス係数が 1 の場合は right-heavy とみなされます。