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

Давай разберём эту тему, а то я вижу, у тебя глаза уже стекленеют. Бинарное дерево поиска — это не какая-то космическая хуйня, а вполне себе логичная штука, если в неё вникнуть.

Представь, что ты — царь и у тебя есть вассалы. Ты — корень, ёпта. У тебя два сына: левый, который всегда тупее (значение меньше), и правый, который умнее (значение больше). И так далее по цепочке. Левый сын тоже заводит своих двух сыновей, которые тупее его, а правый — тех, кто умнее. И так до бесконечности, пока не надоест. Вот тебе и дерево, ядрёна вошь.

Главная фишка в том, что искать в этой структуре — одно удовольствие, если, конечно, твоя династия не выродилась в длиннющую херовину. В среднем, если дерево пышное и раскидистое (сбалансированное), поиск, вставка и удаление занимают O(log n). Это быстро, чувак. Но если ты будешь вставлять данные по порядку — 1, 2, 3, 4... — то получишь не дерево, а обычный связный список, палку кривую. И тогда производительность накроется медным тазом, станет O(n). То есть, чтобы найти число 100, придётся пройтись по всем 99 предкам. Пиздец, а не эффективность.

Поэтому умные дядьки придумали сбалансированные деревья — AVL или Красно-чёрные. Там уже правила жёстче, зато баланс держат, и сложность всегда логарифмическая. Но их реализация — это отдельная песня, там поворачивать узлы надо, цвета менять... Э сабака сука, можно с ума сойти.

Вот, смотри, как это выглядит в коде на 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

Видишь? Всё просто, как три копейки. Создаёшь узел, потом начинаешь его пристраивать. Ищешь место: если значение меньше текущего — идёшь налево, если больше — направо. Нашёл пустое место — воткни свой узел туда и радуйся. Поиск работает по тому же принципу: сравнивай и иди в нужную сторону, пока не найдёшь или не упрёшься в пустоту.

В Node.js такая штука может пригодиться, если тебе нужно быстро искать что-то в памяти, а не лезть в базу. Например, для кэша, или чтобы держать данные отсортированными. Внутри самого V8, кстати, Map и Set используют гибрид хеш-таблиц и деревьев, чтобы и скорость была, и порядок. Умные ребята, чёрт побери.

Так что запомни: BST — это мощно, но только если оно сбалансировано. А иначе получишь не дерево, а жалкую верёвку, по которой придётся карабкаться до самого конца. Доверия к такому дереву — ноль ебать.