w szkole uczymy się, jak balansować drzewo AVL po wstawieniu lub usunięciu.

W jaki sposób ten rodzaj wiedzy będzie przydatny w prawdziwym świecie? Czy ktoś może podać przykład, kiedy ten rodzaj wiedzy byłby rzeczywiście przydatny?

Z tego, co widziałem, w miejscu pracy takie szczegóły rzadko się pojawiają ...

Widzę, jak szczegółowa wiedza na temat algorytmów i niektórych struktur danych może być ważna, ale nie takie szczegóły, jak rotacje drzewa AVL (i podobne szczegółowe pojęcia).

dzięki!

Badanie drzew AVL może być pomocne z następujących powodów:

• To świetna praktyka do wnioskowania o danych abstrakcyjnych. Nie musisz myśleć o jednym konkretnym drzewie, musisz rozważyć każdą możliwość. Ćwiczenie z tego rodzaju rozumowaniem może pomóc w prostszych przypadkach.

• To świetna praktyka do zrozumienia predykatów i umów. Zapewnienie, że drzewo jest zrównoważone, a narzędzia używane do udowodnienia zachowania każdej operacji zachowały równowagę, można np. Zastosować do problemów bezpieczeństwa i do kodu równoległego.

• Umożliwia pisanie własnych wariantów, a nawet tworzenie całkowicie nowych typów struktur danych.

• Być może będziesz musiał zaimplementować drzewo AVL dla nowej biblioteki lub platformy.

Możesz omówić szczególne zalety uczenia się każdego rodzaju algorytmu sortowania lub każdego rodzaju zrównoważonego drzewa. Tak naprawdę nie ma znaczenia, które z nich kończysz się uczyć, ale powinieneś mieć pewność, że uzyskasz pełne omówienie najważniejszych tematów.

Jeśli chcesz zobaczyć, jak ważna jest znajomość algorytmów w prawdziwym świecie, przeczytaj „ How Kill a Great Idea! ”, Artykuł w Inc o upadku Friendstera i jak najmniejsze zastosowanie podstawowych zasad w celu poprawy wydajności mogło im pomóc.

Oprócz punktów Macneils ...

Czerwono-czarne drzewa mogą być bardziej bezpośrednio przydatne, ponieważ istnieją przydatne wydajne operacje, które nie są szeroko obsługiwane w standardowych implementacjach bibliotek, takich jak C ++ std::map(przynajmniej AFAIK). Czerwono-czarne drzewa mogą obsługiwać „podział” (cięcie drzewa na dwa, jeden zawierający klucze mniejsze niż określony klucz, a drugi zawierający klucze większe) i „łączyć” (odwrotnie, łącząc drzewo dużych kluczy z drzewem małych klucze) można wykonać zarówno w czasie O (log n), ale jeśli są one obsługiwane w standardowych bibliotekach kontenerów, wydaje się, że jest to dobrze ukryta rzecz.

Jednak „rozszerzanie” struktur danych jest powszechne. Prostym przykładem jest dodanie informacji o rozmiarze poddrzewa do węzłów w prawie każdej strukturze danych drzewa w celu obsługi indeksowania O (log n). Bardziej zaawansowane przykłady obejmują drzewa interwałów.

Gdy wpadniesz na pomysł rozszerzenia struktur danych, istnieje wiele odmian, które mogą być przydatne w określonych aplikacjach - a bardzo niewiele jest dostępnych w pakiecie jako biblioteka. Istniejących struktur danych biblioteki standardowej (np. Takich jak std::map) nie można rozszerzyć poza kopiowaniem kodu źródłowego i modyfikowaniem go bezpośrednio - nie można go rozszerzyć za pomocą parametrów szablonu.

Oczywiście, aby opracować rozszerzoną strukturę danych, musisz zrozumieć leżącą u jej podstaw nie rozszerzoną strukturę danych.

Drzewa AVL mogą być szybsze niż drzewa czerwono-czarne, jeśli wykonujesz dużo więcej operacji wyszukiwania niż wstawianie / usuwanie (i pod warunkiem, że nie potrzebujesz tych operacji dzielenia / łączenia), więc w zależności od aplikacji mogą być bardzo dobrą bazą dla powiększanie.

Nie

To naprawdę nie jest przydatne w prawdziwym świecie ...

Z wyjątkiem tego, żebyś myślał .

W prawdziwym świecie występują znacznie trudniejsze problemy , z których wiele nie ma jeszcze dobrze znanych rozwiązań.