はじめに

二分探索木は値を順序通りに保持します。すべてのノードの左側の部分木にはより小さい値が、右側の部分木にはより大きい値が保持されます。この順序付けにより検索が高速になりますが、それは木がおおよそバランスを保っている場合に限られます。通常の二分探索木にソートされた順序で値を挿入すると、木は直線状に劣化し、すべての検索が低速な線形探索になってしまいます。

AVL木は、自動的にバランスを維持することでこの問題を解決します。挿入や削除のたびに、ノードが偏っていないかを確認し、偏っている場合は回転と呼ばれる小さな局所的な修正を行ってバランスを回復します。どのように構築しても、AVL木が直線状に劣化することはありません。

このコースでは、お好みの言語でAVL木を一から構築します。高さを追跡するノード、バランスチェック、4つの回転ケース、そして自己バランス型の挿入と削除を実装します。その後、完成したクラスを使用して一連の練習問題に取り組みます。