AVL ツリー

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 の場合は 左ヘビー とみなされ、バランス係数が +1 の場合は 右ヘビー とみなされます。 .

以上がAVL ツリーの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。