Crear un árbol binario de auto ordenación

20

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 .

OghmaOsiris
fuente

Respuestas:

12

Solo dos punteros:

  1. Si realmente desea combinar las ideas de colas de prioridad y árboles de búsqueda binarios, piense en combinar el montón y BST en una estructura.
  2. Existe el concepto de listas autoorganizadas . La idea es mover el elemento al que se accedió recientemente (o hacia el frente) para acelerar los futuros accesos al mismo elemento, "aprendiendo" la distribución del elemento a lo largo del tiempo (con una calidad que depende de la implementación particular). ¿Quizás puedas adaptar esto a los árboles?

Spoiler: siga los enlaces a continuación solo si no ha podido encontrar algo usted mismo.

1. Esto se llama un tratamiento .
2. Los árboles extendidos implementan esta idea.

Rafael
fuente
2

Eche un vistazo a los árboles extendidos, realmente son lo que necesita. Tendría que modificar la función splay, no mover cada nodo al que se accede al árbol, sino lentamente hacia arriba

Bober02
fuente
2
Por qué iba a tener que hacer este cambio? Cualquiera de las estrategias es viable , y hay otras. Además, esta es / era una pregunta de tarea, por lo que las sugerencias son preferibles a las soluciones (no comentadas). Por último, esta respuesta es redundante como es; ¿Tal vez pueda cambiarlo para dirigir el OP hacia su solución propuesta?
Raphael
Bueno, un par de sugerencias para usted: 1. Eche un vistazo a la función splay y vea qué hace, lea la pregunta y descubra, según lo que dice, si modifica la función splay o no. Y no, no todas las estrategias son viables ya que tiene ciertos requisitos que cumplir en función de la prioridad, por lo que cambiar al frente todo el tiempo no es válido 2. ¿Solución no comentada? ¿Cómo es mi respuesta y solución no comentada? 3. "Redundante como es" ... No veo cómo su respuesta, oops, lo siento, las sugerencias son lo último y mi "solución no comentada" trae nota a la mesa
Bober02