如何实现最后执行Zig操作的splay树,而不是先执行Zig操作?
-
30-09-2019 - |
题
对于我的算法和数据结构类,我的任务是在Haskell中实现splay树。我用于播放操作的算法如下:
- 如果要张开的节点是根,则返回未更改的树。
- 如果要溅出的节点是根部的一个级别,则执行ZIG操作并返回结果树。
- 如果要散布的节点是从根部摘要的两个或多个级别,则在该节点启动子树的结果上执行Zig-Zig或Zig-Zag操作,然后返回结果树。
根据我的老师,这是有效的。然而, Wikipedia的张开树的描述 说ZIG步骤“仅作为播放操作的最后一步才能完成”,而在我的算法中,这是播放操作的第一步。
我想实现一棵在最后而不是先执行ZIG操作的splay树,但是我不确定如何最好地完成。在我看来,这样的算法将变得更加复杂,因为人们如何在确定是否应执行ZIG操作之前找到该节点要张开。
如何在Haskell(或其他一些功能性语言)中实现这一目标?
例子
在此示例中,我们搜索值4,提示我们将其溅到树的顶部。
我的算法(曲折作为第一步)
1 1 4 \ \ / 2 zig 2 zig-zig 2 \ --> \ ------> / \ 3 4 1 3 \ / 4 3
Wikipedia算法(ZIG作为最后一步)
1 1 4 \ \ / 2 zig-zig 4 zig 1 \ ------> / --> \ 3 3 3 \ / / 4 2 2
两棵树都是有效的,但是它们具有不同的结构。我想用功能性语言实施第二种,最好是Haskell。
解决方案
关键是要构建通往要张开值的途径,然后从底部重建树,如果可能的话,可以一次进行两个级别(以便可以做出Zig-Zip vs. 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)
您可以找到此代码,以及可运行的单元测试和我的快速检查 回购.
其他提示
您确定正确阅读了Wikipedia描述吗?有三种步骤:“ Zig”,“ Zig-Zig”和“ Zig-Zag”。 “ Zig”步骤是 定义 只有在 x
是根源的孩子。尽管有名称,但“ Zig-Zig”和“ Zig-Zag”步骤并未将“ Zig”步骤作为第一个组件。
在我看来,您的实现遵循这方面的Wikipedia描述。
你可以参考 这个课程, ,在OCAML中有一个非常好的演讲说明,用于Splay树。
不隶属于 StackOverflow