Блог

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

 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
  

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

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
.   .   └── ∅