Метод рекурсивной вставки бинарного дерева поиска в Javascript - PullRequest
0 голосов
/ 13 мая 2018

Мой вопрос о том, как упростить рекурсивную версию insert до бинарного дерева поиска до минимума. Предположим, что я хочу создать BST из массива значений.

Вот как я бы сделал это в JavaScript (это методы класса BST).

_insert(target, key) {
  if (target.key > key) {
    if (!target.left) {
      target.left = new Node(key);
    } else {
      this._insert(target.left, key);
    }
  } else {
    if (!target.right) {
      target.right = new Node(key);
    } else {
      this._insert(target.right, key);
    }
  }
}

insert(key) {
  if (!this.root) {
    this.root = new Node(key);
  } else {
    this._insert(this.root, key);
  }
}

fill(keys) { keys.forEach(k => this.insert(k)); }

С другой стороны, в Хаскеле я бы сделал что-то вроде этого:

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = singleton x
insert x t@(Node a left right)
  | x == a = t
  | x < a = Node a (insert x left) right
  | x > a = Node a left (insert x right)

fill :: (Ord a) => [a] -> Tree a
fill [] = EmptyTree
fill xs = foldr insert EmptyTree $ reverse xs

Версия на Haskell, очевидно, намного лаконичнее и проще для чтения, чем версия на JavaScript.

У меня вопрос, могу ли я как-то упростить версию JavaScript, чтобы сделать ее более «похожей на Haskell» (я знаю, что я мог бы переписать эти методы в функции без необходимости использования класса BST, но код был бы очень похож на этот)? Этот код JavaScript - лучшее, что я придумал.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...