Ich habe eine Aufgabe, bei der ich einen binären Suchbaum verwenden und ihn so ändern muss, dass sich die Elemente, auf die am häufigsten zugegriffen wird (mit höherer Priorität), am oberen Rand des Baums befinden. Dabei ist der Stamm der Knoten, auf den am häufigsten zugegriffen wird .
Der Professor gab mir das BST und die Knotenstruktur, mit denen ich arbeiten konnte, aber der Versuch, den Algorithmus zu verstehen, um den Baum zu aktualisieren, während Dinge eingefügt werden, verwirrt mich.
Ich weiß, dass beim Einfügen geprüft wird, ob die Daten des aktuellen Knotens kleiner oder größer als die des aktuellen Knotens sind. Anschließend wird rekursiv in die richtige Richtung gewechselt, bis ein Nullzeiger gefunden wird und sich dort einfügt. und nach dem Einfügen erhöht es die Priorität um 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
}
Jetzt muss ich herausfinden, wann der Knoten gleich ist, wie der Baum neu angeordnet werden kann, damit der aktuelle Knoten (der einem bereits vorhandenen Knoten entspricht) den vorhandenen Knoten findet, die Priorität dieses Knotens erhöht und ihn dann nach oben verschiebt, wenn der root hat eine niedrigere Priorität.
Ich denke, ich habe die Idee, dass die AVL-Logik funktionieren würde, und wenn eine Verschiebung stattfinden würde, wäre es eine einzelne Drehung nach rechts oder eine einzelne Drehung nach links.
Hier bin ich verwirrt und weiß nicht, wo ich anfangen soll, einen Algorithmus zu erstellen, um das Problem zu lösen. Da der AVL-Algorithmus die Balance eines Baums verfolgt und dann die Knoten entsprechend nach links oder rechts dreht, muss sich dieser Baum nicht darum kümmern, ausgeglichen zu werden, nur dass die Knoten mit der höchsten Priorität keine Kinder mit einer höheren Priorität haben .
quelle