如何删除splay树中的最小元素

Question

我做了一个splay树，但我不明白如何从中删除最小元素，有人可以帮忙吗？

data Splay a = Empty | Node a (Splay a) (Splay a) deriving Show

data Direction = L | R deriving Eq

rotate :: Direction -> Splay a -> Splay a
rotate L (Node x a (Node y b c)) = (Node y (Node x a b) c)
rotate R (Node y (Node x a b) c) = (Node x a (Node y b c))

insert :: Ord a => a -> Splay a -> Splay a
insert x t = let (path, t') = pathToInserted x t in splay t' path
  where pathToInserted :: Ord a => a -> Splay a -> ([Direction], Splay a)
        pathToInserted x Empty = ([], Node x Empty Empty)
        pathToInserted x t@(Node val l r)
          | x == val = ([], t)
          | x < val  = let (path,l') = pathToInserted x l in (L:path, Node val l' r)
          | x > val  = let (path,r') = pathToInserted x r in (R:path, Node val l r')

splay :: Splay a -> [Direction] -> Splay a
splay t [] = t 
-- Zig
splay t [L] = rotate R t
splay t [R] = rotate L t
-- Zig-zig
splay (Node q (Node p x c) d) (L:L:path) = 
        rotate R $ rotate R (Node q (Node p (splay x path) c) d)
splay (Node p a (Node q b x)) (R:R:path) = 
        rotate L $ rotate L (Node p a (Node q b (splay x path)))
-- Zig-zag
splay (Node q (Node p a x) d) (L:R:path) = 
        rotate R (Node q (rotate L $ Node p a (splay x path)) d)
splay (Node p a (Node q x d)) (R:L:path) = 
        rotate L (Node p a (rotate R $ Node q (splay x path) d))

fromList :: Ord a => [a] -> Splay a
fromList = foldr insert Empty

insert' :: Ord a => a -> Splay a -> Splay a
insert' x Empty = Node x Empty Empty
insert' x t@(Node val l r)
  | x == val = t
  | x < val  = rotate R (Node val (insert' x l) r)
  | x > val  = rotate L (Node val l (insert' x r))

main :: IO()
main = putStrLn . show $ fromList [8,3,10,1,6,4,7,14,13]

Answer 1

张开最左边的元素和 return 它的右子元素。你需要一个像 pathToInserted 这样的助手到 return 适当长度的 L 列表。

如何删除splay树中的最小元素

How to delete min element in splay tree

algorithm

haskell

data-structures

splay-tree