J'ai une affectation où je dois utiliser un arbre de recherche binaire et le modifier pour s'auto-ordonner de telle sorte que les éléments qui sont le plus consultés (ont une priorité plus élevée) soient en haut de l'arbre, la racine étant le nœud le plus consulté .
Le professeur m'a donné le BST et la structure des nœuds avec lesquels travailler, mais essayer de me familiariser avec l'algorithme pour mettre à jour l'arbre pendant que les choses sont insérées me déroute.
Je sais que pendant l'insertion, il vérifie si les données du nœud actuel sont inférieures ou supérieures au nœud actuel, puis va récursivement dans la bonne direction jusqu'à ce qu'il trouve un pointeur nul et s'y insère. et une fois inséré, il augmente la priorité de 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
}
Maintenant, je dois déterminer quand le nœud est égal, comment réorganiser l'arborescence afin que le nœud actuel (qui est égal à un nœud déjà existant) trouve le nœud existant, augmente la priorité de ce nœud, puis le déplace vers le haut si le root est une priorité inférieure.
Je pense que j'ai l'idée que la logique AVL fonctionnerait, et lorsqu'un changement aurait lieu, ce serait une seule rotation à droite ou une seule rotation à gauche.
Voici où je suis confus, je ne sais pas vraiment par où commencer avec la création d'un algorithme pour résoudre le problème. Étant donné que l'algorithme AVL fonctionne en gardant une trace de l'équilibre d'un arbre, puis en faisant pivoter les nœuds à gauche ou à droite en conséquence, cet arbre n'a pas à se soucier d'être équilibré, juste que les nœuds avec la priorité la plus élevée n'ont pas d'enfants avec une priorité plus élevée .
la source