Как я могу реализовать косое дерево, которое выполняет операцию крутого поворота в последний раз, не сначала?
Для моего класса Алгоритмов и Структур данных для меня определили задачу с реализацией косого дерева в Haskell. Мой алгоритм для косой операции следующие:
- Если узел, который вывихнется, является корнем, неизменное дерево возвращается.
- Если узел, который вывихнется, является одним уровнем от корня, операция крутого поворота выполняется, и получающееся дерево возвращается.
- Если узел, который вывихнется, является двумя или больше уровнями от корня, крутой поворот крутого поворота или зигзагообразная операция выполняются на результате вывиха поддерева, запускающегося в том узле, и получающееся дерево возвращается.
Это допустимо по словам моего учителя. Однако в описании Википедии косого дерева говорится, что шаг крутого поворота "будет сделан только как последний шаг в косой операции", тогда как в моем алгоритме это - первый шаг в косой операции.
Я хочу реализовать косое дерево, которое выполняет операцию крутого поворота в последний раз вместо первого, но я не уверен, как она была бы лучше всего сделана. Мне кажется, что такой алгоритм стал бы более сложным, видя как, как нужно найти, что узел вывихивается, прежде чем можно будет определить, должна ли операция крутого поворота быть выполнена или нет.
Как я могу реализовать это в 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.
3 ответа
Ключ состоит в том, чтобы построить путь к значению, которое будет развернутый, а затем перестроить дерево снизу, если возможно, по два уровня за раз (чтобы можно было определить зигзагообразный или зигзагообразный зигзаг):
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.