Поиск пола и потолка в BST с помощью Haskell

Мне дали следующий фрагмент кода, и я должен его завершить. Цель состоит в том, чтобы разработать функцию, которая будет вычислять нижний предел заданного элемента k в BST. Пол элемента «k» в BST — это наибольший ключ, меньший, чем «k».

Я действительно в растерянности... Я уже запрограммировал это для Java, но не смог реализовать это на Haskell.

floor :: Ord a => a -> ABST a -> Maybe a
floor x Empty    = Nothing
floor x (Node y w lt rt) 
  | x == y       = Just y
  | x < y = undefined
  | x > y = undefined

Заранее спасибо.


function floor haskell binary-search-tree
person Forset1    schedule 07.12.2014    source источник
comment
Сначала найдите самое большое поддерево, все элементы которого меньше k (т. е. пройдитесь по дереву, пока не найдете узел, меньший k). Затем верните наибольший элемент этого дерева. Вероятно, проще всего записать это как две разные функции.   -  person user2407038    schedule 07.12.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете попробовать проверить, помогают ли "естественные" рекурсивные вызовы в решении этой проблемы.

То есть рассмотреть:

floor :: Ord a => a -> ABST a -> Maybe a
floor x Empty    = Nothing
floor x (Node y w lt rt) 
  | x == y       = Just y
  | x < y = ???
  | x > y = ???
  where floorL = floor x lt
        floorR = floor x rt

Тогда есть ли способ использовать floorL,floorR для достижения желаемого результата?

person chi    schedule 07.12.2014