Домашнее задание по двоичному дереву поиска по функциональному программированию

Итак, мне нужно написать функцию вставки для двоичного дерева, чтобы сделать его двоичным деревом поиска, но у меня возникли некоторые проблемы. Все функции, поэтому я понимаю, что понятия состояния нет. Поэтому мне нужно рекурсивно создавать дерево снова и снова при вставке. У меня проблемы с обдумыванием этой идеи.

treenode -> procedure(val, left, right) procedure(some) if some then -(some, 1) then right else left else val

Это позволяет мне создавать узлы и получать доступ к значению, левому поддереву и правому поддереву, например (0 означает пустое дерево):

.treenode(4, 0, 0)

чтобы создать более сложное дерево, я могу сделать:

.treenode(4, .treenode(3, 0, 0), .treenode(6, .treenode(2, 0, 0), 0))

Я дошел до вставки в пустое дерево:

insert -> procedure(root, value) if empty(root) then .treenode(value, 0, 0) else insert_recursive(root, .treenode(value, 0, 0)

Здесь я не могу понять, как вставить в такое дерево. В этом языке нет концепции состояния, поэтому мне нужно каким-то образом рекурсивно добавить новый узел со значением в текущее дерево. Если кто-то может дать мне подсказку, я был бы очень признателен. Как я должен называть это:

tree = empty
tree = insert(tree, 4)
tree = insert(tree, 6)
....
and so on

functional-programming context-free-language
person Some Guy    schedule 19.03.2019    source источник
comment
Какой это язык? Кроме того, какое отношение этот вопрос имеет к КЛЛ?   -  person Bergi    schedule 19.03.2019
comment
@Bergi это язык, который мы создали в классе   -  person Some Guy    schedule 22.03.2019

Ответы (1)


arrow_upward
3
arrow_downward

Я никогда раньше не встречался с этой грамматикой, так что потерпите меня, если я ошибусь в синтаксисе. Надеюсь, код демонстрирует, что нужно сделать -

  1. если дерево пусто, нет значения для сравнения, создайте одноэлементный узел со значением. Это та часть, которую вы уже закончили.
  2. в противном случае дерево не пусто, поэтому у нас есть значение для сравнения. Если вставляемое значение меньше значения корня, создайте новый узел, состоящий из значения корня, вставьте значение в левую ветвь корня и оставьте правую ветвь корня нетронутой.
  3. если значение больше корневого значения, сделайте то же самое, что и выше, но вставьте новое значение в корневую правую ветвь вместо левой
  4. значение не меньше и не больше значения корня, поэтому оно равно значению корня, и вставлять больше нечего. В этом случае верните немодифицированный корень

Пункты списка соответствуют пронумерованным комментариям ниже -

insert -> procedure(root, value)
  if empty(root) then           #1
    .treenode(value, 0, 0)
  else if value < root.value    #2 
    .treenode (root.value, insert(root.left, value), root.right)
  else if value > root.value    #3
    .treenode (root.value, root.left, insert(root.right, value))
  else                          #4
    root

StackOverflow позволяет нам запускать фрагменты кода JavaScript непосредственно в сообщениях с ответами. Вот работающий фрагмент, который позволяет вам увидеть эту концепцию в действии:

const empty =
  {}

const treenode = (value, left = empty, right = empty) =>
  ({ value, left, right })

const insert = (t, value) =>
  t === empty
    ? treenode (value, empty, empty)
: value < t.value
    ? treenode (t.value, insert (t.left, value), t.right)
: value > t.value
    ? treenode (t.value, t.left, insert (t.right, value))
: t

const print = (t, pre = '', child = '') =>
  t === empty
    ? pre + '∅\n'
    : print
        ( t.right
        , child + '┌── '
        , child + '.   '
        )
    + pre + String (t.value) + '\n'
    + print
       ( t.left
       , child + '└── '
       , child + '.   '
       )

let tree = empty
tree = insert (tree, 4)
tree = insert (tree, 6)
tree = insert (tree, 9)
tree = insert (tree, 3)
tree = insert (tree, 5)
tree = insert (tree, 1)

console.log (print (tree))

Программа печатает построенное tree. Символ ∅ обозначает пусто -

.   .   .   ┌── ∅
.   .   ┌── 11
.   .   .   └── ∅
.   ┌── 9
.   .   └── ∅
┌── 6
.   .   ┌── ∅
.   └── 5
.   .   └── ∅
4
.   ┌── ∅
└── 3
.   .   ┌── ∅
.   └── 1
.   .   └── ∅
person Mulan    schedule 19.03.2019
comment
Как только вы поймете, что нужно сделать, не стесняйтесь редактировать этот ответ с допустимым синтаксисом для вашей процедуры. Дайте мне знать, если у вас есть другие вопросы по этому поводу. - person Mulan; 19.03.2019
comment
То, что вы сказали, имеет смысл, но, я думаю, это не сработает. Мне нужно вернуть копию всего дерева с добавленным новым узлом, поэтому, когда я пытаюсь получить дерево, я также рекурсивно строю его снова. В базовом случае того, что вы мне дали, он просто возвращает узел дерева с новым значением, однако мне нужно, чтобы все дерево возвращалось вместе с новым узлом. - person Some Guy; 19.03.2019
comment
@SomeGuy Я включил работающий фрагмент кода, чтобы продемонстрировать, что вставка действительно возвращает все дерево, а не только недавно вставленный узел - person Mulan; 19.03.2019