Tengo una tarea en la que necesito hacer uso de un árbol de búsqueda binario y modificarlo para que se ordene a sí mismo de modo que los elementos a los que se accede más (tengan una prioridad más alta) estén en la parte superior del árbol, siendo la raíz el nodo más visitado .
El profesor me dio la estructura de nodo y BST para trabajar, pero tratar de entender el algoritmo para actualizar el árbol a medida que se insertan las cosas me confunde.
Sé que a medida que ocurre la inserción, comprueba si los datos del nodo actual son menores o mayores que el nodo actual, luego recursivamente va en la dirección correcta hasta que encuentra un puntero nulo y se inserta allí. y después de que se inserta, aumenta la prioridad en 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
}
Ahora necesito averiguar cuándo el nodo es igual, cómo reordenar el árbol para que el nodo actual (que es igual a un nodo existente) encuentre el nodo existente, aumente la prioridad de ese nodo y luego lo cambie si el la raíz es una prioridad más baja.
Creo que tengo la idea de que la lógica AVL funcionaría, y cuando se produciría un cambio, sería una sola rotación hacia la derecha o una rotación hacia la izquierda.
Aquí es donde estoy confundido, realmente no sé por dónde empezar creando un algoritmo para resolver el problema. Dado que el algoritmo AVL funciona para realizar un seguimiento del equilibrio de un árbol, luego girar los nodos hacia la izquierda o hacia la derecha en consecuencia, este árbol no necesita preocuparse por estar equilibrado, solo que los nodos con la prioridad más alta no tienen hijos con una prioridad más alta .
fuente