Wprowadzenie

Drzewo wyszukiwań binarnych przechowuje wartości w uporządkowany sposób: lewe poddrzewo każdego węzła zawiera mniejsze wartości, a prawe — większe. Dzięki temu wyszukiwanie jest szybkie, ale tylko wtedy, gdy drzewo pozostaje w miarę zrównoważone. Wstawiaj wartości w posortowanej kolejności do zwykłego drzewa wyszukiwań binarnych, a jego struktura spłaszczy się do linii, zmieniając każde wyszukiwanie w powolne, liniowe przeszukiwanie.

Drzewo AVL rozwiązuje ten problem, automatycznie utrzymując równowagę. Po każdym wstawieniu lub usunięciu sprawdza, czy któryś węzeł nie stał się niezrównoważony, a jeśli tak, wykonuje niewielką lokalną korektę zwaną rotacją, aby przywrócić równowagę. Niezależnie od tego, jak je zbudujesz, drzewo AVL nigdy nie spłaszczy się do linii.

W tym kursie zbudujesz drzewo AVL od podstaw w wybranym przez siebie języku: węzły ze śledzoną wysokością, sprawdzanie równowagi, cztery przypadki rotacji oraz samorównoważące się wstawianie i usuwanie. Następnie użyjesz gotowej klasy, aby rozwiązać zestaw zadań do przećwiczenia.