Что такое бинарное дерево поиска?

Бинарное дерево поиска (Binary Search Tree, BST) — это древовидная структура данных, в которой каждый узел имеет не более двух потомков (левый и правый), и для любого узла выполняются условия:

• Все значения в левом поддереве меньше значения узла.
• Все значения в правом поддереве больше значения узла.

Эта структура оптимизирована для быстрого поиска, вставки и удаления элементов (в среднем O(log n)), если дерево сбалансировано.

Реализация на JavaScript/Node.js:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined; // Или обработать дубликат
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  find(value) {
    if (this.root === null) return false;
    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}

// Использование
const bst = new BinarySearchTree();
bst.insert(10).insert(5).insert(15).insert(3);
console.log(bst.find(5)); // Вернет узел со значением 5
console.log(bst.find(99)); // false

Важные нюансы:

• Производительность деградирует до O(n) в вырожденном случае (например, при вставке отсортированных данных 1, 2, 3, 4...), когда дерево превращается в связный список.
• Для гарантированной логарифмической сложности используются сбалансированные варианты BST: AVL-деревья или Красно-черные деревья.
• В Node.js BST может быть полезен для реализации кэшей, хранения отсортированных данных в памяти или как основа для более сложных структур (например, Map или Set в V8 используют вариации хеш-таблиц и деревьев).