Mam zadanie, w którym muszę skorzystać z drzewa wyszukiwania binarnego i zmienić je, aby samo uporządkować się tak, aby elementy, do których najczęściej uzyskiwano dostęp (mają wyższy priorytet), znajdowały się na szczycie drzewa, przy czym węzeł główny był najczęściej dostępnym węzłem .
Profesor dał mi BST i strukturę węzłów do pracy, ale próba obejścia algorytmu aktualizacji drzewa podczas wstawiania rzeczy mnie dezorientuje.
Wiem, że podczas wstawiania sprawdza, czy dane bieżącego węzła są mniejsze lub większe niż bieżący węzeł, a następnie rekurencyjnie idzie we właściwym kierunku, aż znajdzie wskaźnik zerowy i wstawi się tam. a po włożeniu zwiększa priorytet o 1.
template <class Type>
void BinarySearchTree<Type> :: insert( const Type & x, BinaryNode<Type> * & t )
{
if( t == NULL )
t = new BinaryNode<Type>( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
t->priority++; // Duplicate; do nothing for right now
}
Teraz muszę dowiedzieć się, kiedy węzeł jest równy, jak zmienić kolejność drzewa, aby obecny węzeł (który jest równy już istniejącemu węzłowi) znalazł istniejący węzeł, zwiększył priorytet tego węzła, a następnie przesunął go w górę, jeśli root ma niższy priorytet.
Myślę, że mam pomysł, że logika AVL będzie działać, a kiedy nastąpi zmiana, będzie to pojedynczy obrót w prawo lub pojedynczy obrót w lewo.
Tutaj jestem zdezorientowany, tak naprawdę nie wiem od czego zacząć od stworzenia algorytmu, aby rozwiązać problem. Ponieważ algorytm AVL działa w celu śledzenia bilansu drzewa, a następnie odpowiednio obracania węzłów w lewo lub w prawo, drzewo to nie musi się martwić o zrównoważenie, tylko że węzły o najwyższym priorytecie nie mają dzieci o wyższym priorytecie .
źródło