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

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

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

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

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

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

пример

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

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

1 1 4
 \ \ /
  2 зиг 2 зиг зиг 2
   \ ->     \   ------>   / \
    3             4           1   3
     \           /
      4         3

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

1 1 4
 \ \ /
  2 зиг-зиг 4 зиг 1
   \     ------>     / ->   \
    3               3           3
     \             /           /
      4           2           2

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

Источник

3 ответа

Решение

Ключ заключается в том, чтобы построить путь к значению, которое нужно отобразить, а затем перестроить дерево снизу, по возможности, на два уровня за раз (чтобы можно было определить zig-zip или 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)

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

Источник

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

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

Источник

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

Источник
Другие вопросы по тегам