Création d'un arbre binaire auto-ordonné

20

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 .

OghmaOsiris
la source

Réponses:

12

Juste deux pointeurs:

  1. Si vous voulez réellement combiner les idées de files d'attente prioritaires et d'arbres de recherche binaires, pensez à combiner tas et BST dans une seule structure.
  2. Il y a le concept de listes auto-organisées . L'idée est de déplacer l'élément récemment consulté vers (ou vers) le front afin d'accélérer les futurs accès au même élément, "apprenant" ainsi la distribution de l'élément dans le temps (avec une qualité en fonction de l'implémentation particulière). Peut-être pouvez-vous l'adapter aux arbres?

Spoiler: Suivez les liens ci-dessous uniquement si vous n'avez pas pu trouver quelque chose vous-même.

1. C'est ce qu'on appelle un treap .
2. Les arbres évasés mettent en œuvre cette idée.

Raphael
la source
2

Jetez un œil aux arbres évasés, ils sont vraiment ce dont vous avez besoin. Vous devrez modifier la fonction d'affichage, non pas pour déplacer chaque nœud accédé jusqu'à l'arborescence, mais lentement vers le haut

Bober02
la source
2
Pourquoi aurait - il avoir à faire ce changement? L'une ou l'autre stratégie est viable , et il y en a d'autres. En outre, c'est / était une question de devoirs donc les astuces sont préférées aux solutions (non commentées). Enfin, cette réponse est redondante telle quelle; peut-être pouvez-vous le changer pour diriger le PO vers votre solution proposée?
Raphael
Eh bien, quelques conseils pour vous alors: 1. Jetez un œil à la fonction splay et voyez ce qu'elle fait, lisez la question et déterminez, en fonction de ce qu'elle dit, si vous modifiez la fonction splay ou non. Et non, toutes les stratégies ne sont pas viables car il a certaines exigences à respecter en fonction de la priorité, donc passer tout le temps à l'avant n'est pas valable. 2. Solution non commentée? Comment est ma réponse et ma solution non commentée? 3. "Redondant comme il est" ... Je ne vois pas comment votre réponse, oups, désolé - les indices sont ultimes et ma "solution non commentée" apporte une note à la table
Bober02