Erstellen eines selbst bestellten Binärbaums

Question

Ich habe eine Aufgabe, bei der ich einen binären Suchbaum verwenden und sie an sich selbst ändern muss, so dass auf Elemente, auf die am meisten zugegriffen werden (eine höhere Priorität) .

Der Professor gab mir die BST- und Knotenstruktur, mit der ich arbeiten konnte, aber der Versuch, meinen Kopf durch den Algorithmus zu bringen, um den Baum zu aktualisieren, wenn die Dinge eingefügt werden, verwirrt mich.

Ich weiß, dass der Einsatz bei der Einführung überprüft, ob die Daten des aktuellen Knotens weniger oder größer als der aktuelle Knoten sind, und dann rekursiv in die richtige Richtung geht, bis er einen Nullzeiger findet und sich dort einfügt. und nachdem es eingefügt wurde, 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 ordnet, so dass der aktuelle Knoten (der einem bereits vorhandenen Knoten entspricht) den vorhandenen Knoten findet, die Priorität dieses Knoten Wurzel hat eine niedrigere Priorität.

Ich glaube, ich habe die Idee, dass die AVL -Logik funktionieren würde, und wenn eine Verschiebung stattfinden würde, wäre sie eine einzige Drehung rechts oder eine einzige Drehung nach links.

Hier bin ich verwirrt, weiß nicht wirklich, wo ich mit der Erstellung eines Algorithmus anfangen soll, um das Problem zu lösen. Da der AVL -Algorithmus mit der Verfolgung des Gleichgewichts eines Baumes und dann nach links oder rechts rotierender Knoten entsprechend gedreht wird .

Answer 1

Nur zwei Zeiger:

1. Wenn Sie tatsächlich die Ideen von Prioritätswarteschlangen und binären Suchbäumen kombinieren möchten, denken Sie daran, Haufen und BST in einer Struktur zu kombinieren.
2. Da ist das Konzept von selbstorganisierende Listen. Die Idee ist, kürzlich zugegriffen auf Element zu (oder in Richtung) vorne zu verschieben, um den zukünftigen Zugriff auf dasselbe Element zu beschleunigen und damit die Elementverteilung im Laufe der Zeit zu "lernen" (mit Qualität abhängig von der jeweiligen Implementierung). Vielleicht können Sie dies an Bäume anpassen?

---

Spoiler: Folgen Sie den folgenden Links nur, wenn Sie selbst nichts einfallen lassen konnten.

1. Dies wird a genannt Treap.
2. Spreizbäume Implementieren Sie diese Idee.

Answer 2

Schauen Sie sich Spreizbäume an, sie sind wirklich das, was Sie brauchen. Sie müssten die Spreizfunktion ändern, um nicht jeden zugänglichen Knoten bis zum Baum zu bewegen, sondern langsam nach oben, sondern nach oben, sondern nach oben, sondern nach oben, sondern nach oben