Один алгоритм для поиска, обхода, вставки и удаления бинарного дерева

Question

Я вижу реализации двоичного дерева, такие как this :

var insert = function(value, root) {
  if (!root) {
    // Create a new root.
    root = { val: value };
  }
  else {
    var current = root;
    while (current) {
      if (value < current.val) {
        if (!current.left) {
          // Insert left child.
          current.left = { val: value };
          break;
        }
        else {
          current = current.left;
        }
      }
      else if (value > current.val) {
        if (!current.right) {
          // Insert right child.
          current.right = { val: value };
          break;
        }
        else {
          current = current.right;
        }
      }
      else {
        // This value already exists. Ignore it.
        break;
      }
    }
  }

  return root;
}

var exists = function(value, root) {
  var result = false;

  var current = root;
  while (current) {
    if (value < current.val) {
      current = current.left;
    }
    else if (value > current.val) {
      current = current.right;
    }
    else {
      result = true;
      break;
    }
  }

  return result;
}

var traversePre = function(head, callback) {
  // Preorder traversal.
  if (head) {
    if (callback) {
      callback(head.val);
    }

    traversePre(head.left, callback);
    traversePre(head.right, callback);
  }
}

var traversePost = function(head, callback) {
  // Postorder traversal.
  if (head) {
    traversePost(head.left, callback);
    traversePost(head.right, callback);

    if (callback) {
      callback(head.val);
    }
  }
}

var traverseIn = function(head, callback) {
  // Inorder traversal.
  if (head) {
    traverseIn(head.left, callback);

    if (callback) {
      callback(head.val);
    }

    traverseIn(head.right, callback);
  }  
}

var traverseInIterative = function(head, callback) {
  // Inorder traversal (iterative style).
  var current = head;
  var history = [];

  // Move down to the left-most smallest value, saving all nodes on the way.
  while (current) {
    history.push(current);
    current = current.left;
  }

  current = history.pop();
  while (current) {
    if (callback) {
      callback(current.val);
    }

    // Move to the right, and then go down to the left-most smallest value again.
    current = current.right;
    while (current) {
      history.push(current);
      current = current.left;
    }

    current = history.pop();
  }
}

var root = insert(10);
insert(5, root);
insert(6, root);
insert(3, root);
insert(20, root);

В частности, traverseInIterative выглядит довольно хорошо для меня.Но мне интересно, действительно ли нужно иметь insert и exists, а также иметь search или delete.Я понимаю (как в этих реализациях), что они реализованы по-разному, но мне интересно, если бы вы могли реализовать универсальную функцию сопоставления, которая решает все это одним махом, который был бы одновременно идеальным с точки зрения производительности.

Answer 1

Одним из способов создания универсального метода для выполнения всех операций было бы -

genericMethod(value, root, command)

Здесь параметр command получил бы строку, указывающую insert или delete или search.И на основе параметра команды вы можете настроить внутреннюю реализацию для поддержки всех операций.

Теперь давайте перейдем к вопросу производительности и перспективы проектирования.Я не думаю, что такой метод был бы идеальным.Наличие такого общего метода вызовет у вас больше проблем, чем вы думаете.

Теперь после просмотра вашего кода - есть ряд вещей, которые можно улучшить, которые, на мой взгляд, дадут вам лучший опыт, например -

• Для вставки / удаления - вам нужнопроверить, существует ли значение уже или нет.Поэтому просто вызовите метод exists(), а не пишите одинаковые коды в этом методе.

Этот тип общего поведения гарантирует, что вы не будете снова и снова писать одни и те же коды, а также SRP (принцип единой ответственности), так что вашкод отлично разделен и более легко читается.