Proszę o pomoc w następującym zadaniu:
Zaproponuj algorytm badania, czy dane etykietowane drzewo binarne jest drzewem AVL. Koszt algorytmu powinien być liniowy względem liczby wierzchołków w drzewie.
[Algorytmy] Drzewo AVL
[Algorytmy] Drzewo AVL
Ostatnio zmieniony 5 gru 2012, o 17:55 przez Afish, łącznie zmieniany 1 raz.
Powód: Taguj tematy.
Powód: Taguj tematy.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Drzewo AVL
-sprawdzamy czy to drzewo BST, rekurencyjnie, pamiętając w każdym momencie z jakiego przedziału powinny być napotkane klucze
-wyznaczamy rekurencyjnie wysokości poddrzew i porównujemy
-wyznaczamy rekurencyjnie wysokości poddrzew i porównujemy