Удаление узла из двоичного дерева в данные, используемые


Я в настоящее время изучает OCaml и написал после осуществления удаления узла из бинарного дерева

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node(left, nodeValue, right) -> 
      if value < nodeValue then
        Node((deleteNode left value), nodeValue, right)
      else if value > nodeValue then 
        Node(left, nodeValue, (deleteNode right value))
      else if left = Empty && right = Empty then 
        Empty
      else if left = Empty then 
        right
      else if right = Empty then
        left
      else 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))

Где в моем вкусе дерево

type tree = 
  | Empty
  | Node of tree * int * tree

Я ищу обзор мой код так что я могу улучшить мой OCaml и functional навыки.



626
2
задан 16 февраля 2018 в 06:02 Источник Поделиться
Комментарии
1 ответ

Синтаксис

Нет никаких жестких правил на этот счет, но я бы изменил пару вещей в свой синтаксис:


  • избежать ' в качестве идентификаторов. Особенно в этом случае, вы можете использовать tree вместо tree' (нет столкновений с типом имя).

  • обычно есть пространство перед конструктором аргументы, как Node (left, nodeValue, right) (действительно до конвенции, но я бы сказал, что это больше всего).

  • скобки вокруг функции приложения не нужны, так что это больше идиоматических писать Node (deleteNode left value, nodeValue, right). Вы можете также извлечь привязки: let newLeft = deleteNode left value in Node (newLeft, nodeValue, right)

  • случае верблюд редкого вида OCaml (я знаю, что это странно!). Например, стандартная библиотека использует такие имена, как print_endline и т. д. Итак, я хотел бы использовать node_valueи т. д.

Заменить условные с охранниками

Каждый раз if в шаблону филиал, вы можете извлечь его в охранника. Синтаксис | pattern when condition ->.

Применив это к первому ifs, мы можем приехать в это государство:

let rec deleteNode tree' value = 
match tree' with
| Empty -> Empty
| Node (left, nodeValue, right) when value < nodeValue ->
Node((deleteNode left value), nodeValue, right)
| Node (left, nodeValue, right) when value > nodeValue ->
Node(left, nodeValue, (deleteNode right value))
| Node (left, nodeValue, right) ->
if left = Empty && right = Empty then
Empty
else if left = Empty then
right
else if right = Empty then
left
else
let newValue = minValue right in
Node(left, newValue, (deleteNode right newValue))

Использовать глубокие шаблону

Вы можете заменить x = Empty тесты по шаблону. Другими словами, модели могут содержать шаблоны. При применении этого все условия, мы получим:

let rec deleteNode tree' value = 
match tree' with
| Empty -> Empty
| Node (left, nodeValue, right) when value < nodeValue ->
Node((deleteNode left value), nodeValue, right)
| Node (left, nodeValue, right) when value > nodeValue ->
Node(left, nodeValue, (deleteNode right value))
| Node (Empty, nodeValue, Empty) ->
Empty
| Node (Empty, nodeValue, right) ->
right
| Node (left, nodeValue, Empty) ->
left
| Node (left, nodeValue, right) ->
let newValue = minValue right in
Node(left, newValue, (deleteNode right newValue))

Удаление избыточных случаев

Это более очевидно с шаблоном, но Node (Empty, nodeValue, right) случаях также применяется при right = Empty, так что мы можем удалить более конкретные Node (Empty, nodeValue, Empty) случае.

Вот об этом! Есть хороший путь изучения программирования OCaml

3
ответ дан 20 февраля 2018 в 10:02 Источник Поделиться