代码之家 › 专栏 › 技术社区 › Jakob

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

splay-tree functional-programming haskell

Jakob · 技术社区 · 15 年前

对于algorithms&data structures类,我的任务是在haskell中实现一个splay树。我的splay操作算法如下:

如果要展开的节点是根,则返回未更改的树。
如果要展开的节点与根节点相距一级,则执行zig操作并返回结果树。
如果要展开的节点是根目录的两个或多个级别,则会对从该节点开始展开子树的结果执行zig-zig或zig-zag操作,并返回结果树。

据我的老师说这是有效的。然而, the Wikipedia description of a splay tree 说zig步骤“只能作为splay操作的最后一步完成”,而在我的算法中,它是splay操作的第一步。

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

我如何用haskell(或其他一些函数语言)实现这一点?

例子

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

我的算法(第一步是zig)

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

维基百科算法(最后一步是zig)

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

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

3 回复 | 直到 15 年前

MtnViewMark 15 年前

关键是要建立一条到要展开的值的路径,然后从底部重建树,如果可能的话,一次重建两个级别(以便可以确定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 .

Travis Brown 15 年前

你确定你读的维基百科描述是正确的吗?有三种步骤:“之字形”、“之字形”和“之字形”。“zig”步骤是定义只有在 x 是根的子级。尽管有这些名称,“之字形”和“之字形”台阶并没有“之字形”台阶作为第一个组件。

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

Yin Zhu 15 年前

你可以参考 this course 这是一个非常好的讲座笔记,用OCAML编写的用于八字树的代码。