Con respecto a los árboles de extensión

Question

Estoy leyendo sobre árboles de entregas en estructuras de datos y algoritmos de Mark Allen Wesis

La estrategia de extinción es similar a la idea de rotación, excepto que somos un poco más selectivos sobre cómo se realizan las rotaciones. Todavía giraremos abajo a lo largo de la ruta de acceso. Sea x un nodo (no root) en la ruta de acceso en la que estamos rotando. Si el padre de X es la raíz del árbol, simplemente giramos X y la raíz. Esta es la última rotación a lo largo de la ruta de acceso. De lo contrario, X tiene un padre (P) y un abuelo (G), y hay dos casos, más simetrías, a considerar. El primer caso es el caso Zig-Zag, aquí X es un niño derecho y P es un niño izquierdo (o viceversa). Si este es el caso, realizamos una doble rotación, exactamente como una doble rotación AVL. De lo contrario, tenemos un caso Zig-Zig: X y P son niños izquierdos o ambos niños correctos.

En el texto anterior, ¿qué significa el autor siguiendo la declaración "Hay dos casos más simetrías"? Se dan dos casos, pero ¿qué son los simmetirires aquí?

¡Gracias!

Answer 1

Creo que es una simetría axial bastante básica:

Ejemplo para un caso zig zag, aquí hay 2 árboles simétricos:

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b

Answer 2

Por ejemplo, digamos que un caso es "cuando el nodo en las preguntas es el hijo derecho de su padre y el padre es el hijo izquierdo del abuelo" En este caso, hace una rotación izquierda y luego una rotación derecha. Entonces el nodo se acercará al gran padre.

La parte simétrica de este caso es "cuando el nodo en preguntas es el hijo izquierdo de su padre y el padre es el hijo derecho del abuelo" En este caso, hace una rotación derecha y luego una rotación izquierda. Entonces el nodo se acercará al gran padre.

Reemplace a la izquierda con la derecha y la derecha con la izquierda obtendrá la caja simétrica.

Solo hay 3 casos de rotación en un árbol de mantequilla. Lo enumeró aquíPuede ver la diferencia de tiempo de ejecución en la búsqueda con y sin extinción.