haskell - 如何实现最后执行zig操作而不是首先执行zig操作的splay树？

对于我的算法和数据结构类，我的任务是在Haskell中实现展开树。我的splay操作算法如下:

如果要展开的节点是根，则返回未更改的树。

如果要展开的节点离根节点只有一个级别，则执行zig操作并返回结果树。

如果要展开的节点距离根节点有两个或多个级别，则对从该节点开始展开子树的结果执行zig-zig或zig-zag操作，并返回结果树。

根据我的老师，这是有效的。但是，the Wikipedia description of a splay tree说，之字形步骤“只会作为展开操作的最后一步完成”，而在我的算法中，它是展开操作的第一步。

我想实现一个展开树，在最后而不是首先执行zig操作，但是我不确定如何最好地完成它。在我看来，这种算法会变得更加复杂，因为在确定是否应该执行zig操作之前，需要如何找到要扩展的节点。

如何在Haskell(或其他功能语言)中实现此功能？

例子

在此示例中，我们搜索值4，促使我们将其展开到树的顶部。

我的算法(zig作为第一步)

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

Wikipedia算法(最后一步是Zig)

1 1 4
\
2曲折曲折4曲折1
\------>/->\
3 3 3
\//
4 2 2

两种树都是有效的，但是它们具有不同的结构。我想用一种功能语言(最好是Haskell)实现第二种。

最佳答案

关键是要建立一条要散布的值的路径，然后从底部重建树，如果可能的话，一次建两个层次(这样就可以确定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)

您可以在repo中找到此代码以及可运行的单元测试和快速检查。

关于haskell - 如何实现最后执行zig操作而不是首先执行zig操作的splay树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2861817/