inserción árbol biselado

Question

El ir a través de algunos ejercicios para perfeccionar mis habilidades de árboles binarios, decidí poner en práctica un árbol biselado, como se indica en Wikipedia:. Splay árbol

Una cosa que no recibo es la parte de inserción.

Se dice:

  

En primer lugar, buscamos x en el árbol biselado. Si x no existe, entonces no vamos a encontrar, pero su nodo padre y. En segundo lugar, se realiza una operación de ensanchamiento de y que se trasladará a la raíz y del árbol biselado. En tercer lugar, insertamos el nuevo nodo x como root de una manera apropiada. De esta manera, ya sea y se deja o hijo derecha de la nueva raíz x.

Mi pregunta es la siguiente: El texto anterior parece demasiado escueta en comparación con los otros ejemplos en el artículo, ¿por qué es esto? Parece que hay algunos aspectos críticos que quedan aquí. Por ejemplo, después extendiendo el nodo y hasta la raíz, no puedo simplemente reemplazar ciegamente raíz con x, y la pegajosidad y en x, ya sea como hijo izquierdo o derecho.

Vamos a suponer que el valor no existe ya en el árbol.

Tengo este árbol:

           10
          /  \
         5    15
        / \    \
       1   6    20

y quiero insertar 8. Con la descripción anterior, lo haré hasta encontrar la 6-nodo, y en un árbol binario normal, 8 se añadiría como un hijo derecho del nodo-6, sin embargo aquí primero tengo a splay la 6-nodo hasta root:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

A continuación, cualquiera de estos dos son claramente errónea:

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

Me parece que la única manera de hacer el ensanchamiento primero, y luego añadir correctamente el nuevo valor como raíz, significa que tenga que comprobar los siguientes criterios (para agregar el nodo abocinada como el hijo izquierdo de la nueva raíz) :

1. el nodo I extendidos a la raíz es menor que la nueva raíz (6 <8)
2. el niño más a la derecha del nodo I extendidos a la raíz es también menos de la nueva raíz (20 8)

Sin embargo, si tuviera que dividir el nodo I abocinada, tomando el hijo derecho y añadiendo como el hijo derecho del nodo nuevo, me sale esto:

                        8
                       / \
                      6   10
                     /     \
                    5       15
                   /         \
                  1           20

Sin embargo, es esta simple alteración siempre me va a dar un árbol correcto? Estoy teniendo dificultades para dar con un ejemplo, pero ¿Puede esto conducir a lo siguiente:

• El nuevo valor que quiero añadir es más alta que la raíz temporal (el nodo que splayed a la raíz), pero también más alto que el niño más a la izquierda del botón derecho del niño de la raíz temporal?

Ie. un árbol que, básicamente, tener este aspecto después de ensanchamiento, pero antes de que se sustituye la raíz?

                        10
                       /  \
                      5    15
                          /  \
                        11    20

y yo quiero agregar 13, lo que haría que el nuevo árbol de la siguiente manera:

                        13
                       /  \
                     10    15
                     /    /  \
                    5   11    20  <-- 11, on the wrong side of 13

o puede que esto nunca sucederá?

Mi segunda pregunta es la siguiente: ¿No sería mucho más fácil simplemente reescribir la operación de la siguiente manera:

  

En primer lugar, buscamos x en el árbol biselado. Si x no existe, entonces no vamos a encontrar, pero su nodo padre y. A continuación, añadimos el nuevo nodo ya sea como un hijo izquierdo o derecho del nodo padre. En tercer lugar, se realiza una operación de ensanchamiento en el nodo añadimos , que se moverá el nuevo valor a la raíz del árbol biselado.

énfasis es mío para mostrar lo que he cambiado.

Answer 1

No veo cómo el problema que usted describe podría suceder. Si desea insertar 13 en este árbol primero tiene que encontrar dónde sería:

                    10
                   /  \
                  5    15
                      /  \
                    11    20

A partir de 10 se ve a la derecha, desde el 15 de ir a la izquierda, del 11 vas a la derecha ... y luego tienes que hay más elementos. Si 13 habían estado en el árbol, nos habríamos encontrado como un niño derecha de 11. Así que de acuerdo a la regla que realizar una operación de ensanchamiento de 11 que moverá 11 a la raíz del árbol biselado:

                    11
                   /  \
                  10   15
                 /       \
                5         20

A continuación, añadimos 13 como la nueva raíz, con el 11 como el hijo izquierdo:

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

Ahora no hay ningún problema.

  

En primer lugar, buscamos x en el árbol biselado. Si x no existe, entonces no vamos a encontrar, pero su nodo padre y. A continuación, añadimos el nuevo nodo ya sea como un hijo izquierdo o derecho del nodo padre. En tercer lugar, se realiza una operación de ensanchamiento en el nodo añadimos que moverá el nuevo valor de la raíz del árbol biselado.

Esto me suena como que iba a funcionar también, pero si yo fuera usted, me acaba de tratar de implementar la versión como se describe en Wikipedia ya muchas personas han probado eso y que ya está bien documentada.

Answer 2

"Splay árbol" de inmediato me hizo recordar un artículo en CUJ que leí hace un tiempo, es posible encontrar una cierta penetración existe: Ejecución Splay Árbol en C ++ .

  

En tercer lugar, insertar el nuevo nodo x como root de una manera apropiada. De esta manera, ya sea y se deja o hijo derecha de la nueva raíz x.

Sí, pero esta nueva raíz x tiene que tener 2 hijos, es por eso que esta frase puede sonar confuso.

Answer 3

el nuevo nodo se añade al árbol como un árbol binario de búsqueda normal. A continuación, el nuevo nodo se extendió hasta la raíz o el primer nivel de la raíz. Además, cuando insertamos un nuevo nodo, tenemos que encontrar la ubicación de decirlo, por lo que hacemos un hallazgo. Y todas las operaciones incluyendo hallazgo en un árbol biselado desencadenar una operación de ensanchamiento. Puede ser que por eso el artículo de Wikipedia lo describe así. Me basta con insertar el nuevo nodo y el ensanchamiento hacia arriba. De cualquier manera el árbol se vuelve más equilibrado de lo que era. funciona bien aquí