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

Question

Для моих алгоритмов и класса структур данных я был настроен на реализацию дерева Splay в Haskell. Мой алгоритм для операции Splay выглядит следующим образом:

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

Это действительно в соответствии с моим учителем. Однако, Википедия Описание дерева Splay Говорят, что этап зига «будет сделан только в качестве последнего шага в операции SPLAY», тогда как в моем алгоритме это первый шаг в операции SPLAY.

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

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

Пример

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

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

1 1 4   / 2 ZIG 2 ZIG-ZIG 2  ->  ------> /  3 4 1 3  / 4 3

Википедия алгоритм (зиг как последний шаг)

1 1 4  / 2 ZIG-ZIG 4 ZIG 1  -------> / ->  3 3 3  / / 4 2 2

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

Answer 1

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

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)

Вы можете найти этот код, наряду с тестами Runnable Build и быстрые чеки в моем репо.

Answer 2

Вы уверены, что вы правильно читаете описание Википедии? Есть три вида шагов: «зиг», «зиг-зиг» и «зигзаг». Шаг «Зиг» определенный быть чем-то, что происходит только когда x это ребенок корня. Несмотря на имена, шаги «Zig-Zig» и «Zig-Zag» не имеют «зиг» шагов в качестве первого компонента.

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

Answer 3

Вы можете реф этот курс, который имеет очень хорошую лекцию с кодом в Ocaml для дерева Splay.