Erstellen eines selbstordnenden Binärbaums

20

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 .

OghmaOsiris
quelle

Antworten:

12

Nur zwei Hinweise:

  1. Wenn Sie die Ideen von Prioritätswarteschlangen und binären Suchbäumen kombinieren möchten, sollten Sie Heap und BST in einer Struktur kombinieren.
  2. Es gibt das Konzept selbstorganisierender Listen . Die Idee ist, das Element, auf das kürzlich zugegriffen wurde, nach vorne (oder nach vorne) zu verschieben, um künftige Zugriffe auf dasselbe Element zu beschleunigen und so die Elementverteilung über die Zeit zu "lernen" (mit einer Qualität, die von der jeweiligen Implementierung abhängt). Vielleicht können Sie dies an Bäume anpassen?

Spoiler: Folgen Sie den unten stehenden Links nur, wenn Sie selbst nicht auf etwas gekommen sind.

1. Dies nennt man einen Treap .
2. Spreizbäume setzen diese Idee um.

Raphael
quelle
2

Schauen Sie sich Spreizbäume an, sie sind genau das, was Sie brauchen. Sie müssten die Splay-Funktion ändern, um nicht jeden Knoten, auf den zugegriffen wird, bis zum Baum zu verschieben, sondern langsam nach oben

Bober02
quelle
2
Warum soll er hat diese Änderung vornehmen zu? Jede Strategie ist machbar , und es gibt andere. Außerdem ist / war dies eine Hausaufgabe, daher werden Hinweise (unkommentierten) Lösungen vorgezogen. Schließlich ist diese Antwort so wie sie ist überflüssig. Vielleicht können Sie es ändern, um das OP zu Ihrer vorgeschlagenen Lösung zu führen?
Raphael
Nun, dann ein paar Tipps für Sie: 1. Schauen Sie sich die Splay-Funktion an und sehen Sie, was sie tut. Lesen Sie die Frage und finden Sie heraus, basierend auf den Aussagen, ob Sie die Splay-Funktion ändern oder nicht. Und nein, nicht alle Strategien sind umsetzbar, da er bestimmte Anforderungen erfüllen muss, die auf der Priorität beruhen. Eine ständige Verlagerung nach vorne ist also nicht gültig. 2. Eine unkommentierte Lösung? Wie ist meine Antwort und unkommentierte Lösung? 3. "Redundant wie es ist" ... Ich verstehe nicht, wie Ihre Antwort, oops, sorry - Hinweise sind ultimativ und meine "unkommentierte Lösung" bringt
Notizen