如何实现最后执行 zig 操作而不是首先执行 zig 操作的展开树？

Question

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

1. 如果要展开的节点是根，则返回未改变的树。
2. 如果要展开的节点距离根只有一层，则执行 zig 操作并返回结果树。
3. 如果要展开的节点距离根有两级或以上，则将从该节点开始展开子树的结果执行zig-zig或zig-zag操作，并返回结果树。

根据我的老师的说法，这是有效的。然而，维基百科对展开树的描述说zig步骤“仅作为展开操作中的最后一步完成”，而在我的算法中，它是展开操作中的第一步。

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

我如何在 Haskell（或其他函数式语言）中实现这个？

示例

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

我的算法（zig 作为第一步）

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

维基百科算法（zig 作为最后一步）

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

两棵树都是有效的，但它们具有不同的结构。我想用函数式语言实现第二个，最好是 Haskell。

Answer 1

关键是构建一条通往要展开的值的路径，然后从底部重建树，如果可能的话一次两层（以便可以做出 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中找到此代码以及可运行的单元测试和快速检查。

Answer 2

您确定您正确阅读了维基百科的描述吗？步法有“zig”、“zig-zig”和“zig-zag”三种。 “zig”步骤被定义，仅当

x

是根的子节点时才会发生。尽管有这些名称，但“zig-zig”和“zig-zag”步骤没有“zig”步骤作为第一个组件。

在我看来，您的实现在这方面遵循了维基百科的描述。

Answer 3

您可以参考本课程，其中有一个非常好的讲稿，其中包含用于 Splay 树的 OCaml 代码。