¿Cómo puedo implementar un árbol biselado que realiza la operación de zig pasado, no el primero?

Question

Para mi clase de Algoritmos y Estructuras de Datos, he estado la tarea de implementar un árbol biselado en Haskell. Mi algoritmo para la operación de ensanchamiento es el siguiente:

1. Si el nodo que se va extendidas es la raíz, se devuelve el árbol inalterada.
2. Si el nodo que se va extendidas es un nivel de la raíz, una operación que se realiza en zig y se devuelve el árbol resultante.
3. Si el nodo para ser extendidas es de dos o más niveles de la raíz, un zig-zig u operación en zig-zag se realiza en el resultado de extendiendo el subárbol que comienza en ese nodo, y se devuelve el árbol resultante.

Esto es válido de acuerdo a mi maestro. Sin embargo, la descripción de Wikipedia de un árbol biselado dice que el paso de zig "se llevará a cabo únicamente como último recurso paso en una operación de ensanchamiento", mientras que en mi algoritmo es el primer paso en una operación de ensanchamiento.

Quiero poner en práctica un árbol biselado que realiza la operación de zig último lugar de la primera, pero no estoy seguro de cómo sería mejor hacerse. Me parece que este tipo de algoritmo podría ser más compleja, ya que la forma en que uno necesita para encontrar el nodo que se extendió antes de que se pueda determinar si una operación de zig debe ser realizado o no.

¿Cómo puedo aplicar esto en Haskell (o algún otro lenguaje funcional)?

Ejemplo

En este ejemplo buscamos el valor de 4, nos impulsa a splay a la parte superior del árbol.

Mi algoritmo (zig como el primer paso)

1             1                   4
 \             \                 /
  2      zig    2    zig-zig    2
   \     -->     \   ------>   / \
    3             4           1   3
     \           /
      4         3

Wikipedia algoritmo (zig como el último paso)

1                   1           4
 \                   \         /
  2      zig-zig      4  zig  1
   \     ------>     /   -->   \
    3               3           3
     \             /           /
      4           2           2

Ambos árboles son válidas, pero tienen estructuras diferentes. Quiero poner en práctica la segunda en un lenguaje funcional, preferiblemente Haskell.

Answer 1

La clave es construir un camino para el valor a ser extendidas, luego reconstruir el árbol de la parte inferior, dos niveles a la vez si es posible (de modo que el zig-zip vs zig-zag determinación se puede hacer):

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Eq, Show)

data Direction = LH | RH
    deriving (Eq, Show)


splay :: (Ord a) => a -> Tree a -> Tree a
splay a t = rebuild $ path a t [(undefined,t)]
    where path a Empty ps = ps
          path a n@(Node b l r) ps =
              case compare a b of
                  EQ -> ps
                  LT -> path a l $ (LH, l) : ps
                  GT -> path a r $ (RH, r) : ps

          rebuild :: (Ord a) => [(Direction,Tree a)] -> Tree a
          rebuild ((_,n):[]) = n
          rebuild ((LH,x):(_,p):[]) = zigL x p
          rebuild ((RH,x):(_,p):[]) = zigR x p
          rebuild ((LH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzigL x p g):ps
          rebuild ((RH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzigR x p g):ps
          rebuild ((RH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzagL x p g):ps
          rebuild ((LH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzagR x p g):ps

          zigL (Node x a b) (Node p _ c) = Node x a (Node p b c)
          zigR (Node x a b) (Node p c _) = Node x (Node p c a) b

          zigzigL (Node x a b) (Node p _ c) (Node g _ d) =
              Node x a (Node p b (Node g c d))

          zigzigR (Node x a b) (Node p c _) (Node g d _) =
              Node x (Node p (Node g d c) a) b

          zigzagL (Node x b c) (Node p a _) (Node g _ d) =
              Node x (Node p a b) (Node g c d)

          zigzagR (Node x b c) (Node p _ a) (Node g d _) =
              Node x (Node g d b) (Node p c a)

Puede encontrar este código, junto con las pruebas unitarias ejecutables y comprobaciones rápidas en mi repo .

Answer 2

¿Está seguro de que está leyendo la descripción de Wikipedia correctamente? Hay tres tipos de medidas: "zig", "zig-zig", y "zig-zag". El paso de "zig" es definido a ser algo que ocurre sólo cuando x es un hijo de la raíz. A pesar de los nombres, el "zig-zig" y "en zigzag" pasos no tienen "zig" pasos como un primer componente.

Me suena igual que su aplicación sigue la descripción de Wikipedia al respecto.

Answer 3

Puede ref este curso , que tiene una muy buena conferencia nota con código en OCaml para el árbol biselado.