Как я могу реализовать splay-дерево, которое выполняет операцию zig последним, а не первым?

Question

Для моего класса Algorithms & Data Structures мне было поручено реализовать Splay Tree в Haskell. Мой алгоритм операции splay выглядит следующим образом:

1. Если расширяемый узел является корнем, возвращается неизмененное дерево.
2. Если развертываемый узел находится на один уровень от корня, выполняется операция zig и возвращается результирующее дерево.
3. Если развертываемый узел находится в двух или более уровнях от корня, выполняется операция зигзага или зигзага по результату расширения поддерева, начинающегося с этого узла, и возвращается результирующее дерево.

Это верно в соответствии с моим учителем. Тем не менее, описание википедии для дерева сплайнов говорит, что шаг зигзага "будет выполнен только как последний шаг в операции сплайна", тогда как в моем алгоритме это первый шаг в операции сплайна.

Я хочу реализовать Splay Tree, который выполняет операцию zig последним, а не первым, но я не уверен, как это лучше всего сделать. Мне кажется, что такой алгоритм станет более сложным, так как нужно найти узел, который нужно развернуть, прежде чем можно будет определить, следует ли выполнять операцию zig или нет.

Как я могу реализовать это в Haskell (или другом функциональном языке)?

Пример

В этом примере мы ищем значение 4, побуждая нас развернуть его к вершине дерева.

Мой алгоритм (первый шаг - zig)

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

Алгоритм Википедии (последний шаг - zig)

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

Оба дерева допустимы, но имеют разную структуру. Я хочу реализовать второй на функциональном языке, предпочтительно на Haskell.

Answer 1

Ключ в том, чтобы построить путь к значению, которое нужно отобразить, а затем перестроить дерево снизу, по возможности, на два уровня за раз (чтобы можно было определить зигзаг против зигзага):

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)

Вы можете найти этот код вместе с работающими модульными тестами и быстрыми проверками в моем репо .

Answer 2

Вы можете сослаться на этот курс , в котором есть очень хорошая лекционная заметка с кодом в OCaml для Splay Tree.

Answer 3

Вы уверены, что правильно читаете описание Википедии? Существует три вида шагов: «зиг», «зиг-зиг» и «зигзаг». Шаг "zig" определен как нечто, что происходит, только когда x является дочерним элементом корня. Несмотря на названия, шаги "zig-zig" и "zig-zag" не имеют шагов "zig" в качестве первого компонента.

Мне кажется, что ваша реализация следует описанию Википедии в этом отношении.