[Algorytmy] Drzewo AVL

fly92 · Post autor: **fly92** » 4 gru 2012, o 15:50

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.

Kartezjusz · Post autor: **Kartezjusz** » 4 gru 2012, o 15:57

Jak rozumiesz drzewo etykietowane.

Zordon · Post autor: **Zordon** » 4 gru 2012, o 18:19

-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