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

Бинарное дерево поиска (BST) — основная структура данных

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

Структура BST

        50
       /        30   70
     / \   /     20 40 60 80

Реализация в JavaScript

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  insert(value) {
    const newNode = new Node(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;
      }
    }
  }
  
  search(value) {
    let current = this.root;
    
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    
    return false;
  }
}

Обход дерева (Traversal)

// In-order — отсортированные значения
inOrder(node = this.root, result = []) {
  if (node !== null) {
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
  }
  return result;
}

// Pre-order (узел → левый → правый)
preOrder(node = this.root, result = []) {
  if (node !== null) {
    result.push(node.value);
    this.preOrder(node.left, result);
    this.preOrder(node.right, result);
  }
  return result;
}

// Post-order (левый → правый → узел)
postOrder(node = this.root, result = []) {
  if (node !== null) {
    this.postOrder(node.left, result);
    this.postOrder(node.right, result);
    result.push(node.value);
  }
  return result;
}

Удаление узла

delete(value) {
  this.root = this._deleteNode(this.root, value);
  return this;
}

_deleteNode(node, value) {
  if (node === null) return null;
  
  if (value < node.value) {
    node.left = this._deleteNode(node.left, value);
    return node;
  } else if (value > node.value) {
    node.right = this._deleteNode(node.right, value);
    return node;
  } else {
    // Нашли узел
    if (node.left === null && node.right === null) return null;
    if (node.left === null) return node.right;
    if (node.right === null) return node.left;
    
    // Два потомка — находим min из правого поддерева
    let minRight = node.right;
    while (minRight.left !== null) {
      minRight = minRight.left;
    }
    
    node.value = minRight.value;
    node.right = this._deleteNode(node.right, minRight.value);
    return node;
  }
}

Сложность операций

Худший случай O(n) — когда дерево несбалансировано.

Сбалансированные BST

• AVL Tree — O(log n) гарантировано
• Red-Black Tree — проще, тоже O(log n)
• B-Tree — используется в БД

Поиск в диапазоне

function findInRange(node, min, max, result = []) {
  if (node === null) return result;
  
  if (node.value >= min) {
    findInRange(node.left, min, max, result);
  }
  
  if (node.value >= min && node.value <= max) {
    result.push(node.value);
  }
  
  if (node.value <= max) {
    findInRange(node.right, min, max, result);
  }
  
  return result;
}

Key takeaway

• BST = быстрый поиск O(log n)
• Все операции O(log n) в сбалансированном дереве
• In-order обход возвращает отсортированные значения
• Используется в БД, файловых системах, поисковых системах
• Для гарантии O(log n) используй AVL или Red-Black деревья