Как устроены left и right ветки дерева?

Основы бинарного дерева

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

Различие между левой и правой ветвями

В бинарном дереве поиска (BST) левая ветвь содержит узлы с ключами меньше корневого, а правая — с ключами больше корневого. Это свойство рекурсивно применяется ко всем поддеревьям, что позволяет выполнять поиск за O(log n) в сбалансированном дереве.

Пример кода на JavaScript

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

// Создание дерева
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);

// Поиск значения
function search(node, target) {
  if (!node) return false;
  if (node.value === target) return true;
  if (target < node.value) return search(node.left, target);
  return search(node.right, target);
}

Применение

Левая и правая ветви используются в алгоритмах сортировки (например, in-order обход дает отсортированный массив), в базах данных для индексации и в реализации ассоциативных массивов. Понимание их устройства критично для работы с деревьями.

Вывод: левая и правая ветви — основа организации данных в бинарных деревьях, обеспечивающая эффективный поиск и сортировку. Применяйте эту структуру, когда нужен быстрый доступ к упорядоченным данным.