Tree Sort (Сортировка деревом)
Краткое описание
Алгоритм сортировки, который строит бинарное дерево поиска (BST) из элементов массива, а затем выполняет обход дерева in-order (симметричный обход) для получения отсортированного массива. Эффективность зависит от сбалансированности дерева: O(n log n) для сбалансированного и O(n²) для вырожденного дерева.
Когда использовать
- Данные поступают динамически — можно добавлять элементы в дерево по мере поступления и поддерживать отсортированный порядок
- Нужны дополнительные операции — кроме сортировки требуется поиск, вставка или удаление элементов (дерево поддерживает все за O(log n))
- Используется самобалансирующееся дерево — AVL или Red-Black Tree гарантирует O(n log n)
- Данные уже в древовидной структуре — если работаете с деревьями, можно использовать in-order обход
- Нужна онлайн-сортировка — элементы можно добавлять в любой момент
Когда не стоит использовать:
- Случайные данные без балансировки — вырожденное дерево даст O(n²), что хуже Quick Sort
- Ограниченная память — требует O(n) дополнительной памяти для узлов дерева
- Простота реализации важна — сложнее обычных алгоритмов сортировки
- Маленькие массивы — накладные расходы на создание дерева не окупятся
- Много дубликатов — стандартный BST плохо работает с дубликатами
С объяснением логики работы
/**
* Tree Sort — сортировка с использованием BST
*
* Алгоритм:
* 1. Создаём пустое бинарное дерево поиска (BST)
* 2. Вставляем все элементы массива в дерево
* 3. Выполняем in-order обход дерева (левое поддерево → корень → правое поддерево)
* 4. Получаем отсортированный массив
*
* Свойство BST: для любого узла все элементы левого поддерева меньше,
* а все элементы правого поддерева больше значения узла.
*/
/**
* Класс узла дерева
*/
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // Левое поддерево (меньшие значения)
this.right = null; // Правое поддерево (большие значения)
}
}
/**
* Класс бинарного дерева поиска
*/
class BinarySearchTree {
constructor() {
this.root = null; // Корень дерева
}
/**
* Вставка элемента в BST
* Рекурсивно находим правильную позицию
*/
insert(value) {
// Создаём новый узел
const newNode = new TreeNode(value);
// Если дерево пустое, новый узел становится корнем
if (this.root === null) {
this.root = newNode;
return;
}
// Иначе рекурсивно ищем место для вставки
this._insertNode(this.root, newNode);
}
/**
* Вспомогательная функция для рекурсивной вставки
*/
_insertNode(node, newNode) {
// Если новое значение меньше текущего узла
if (newNode.value < node.value) {
// Идём в левое поддерево
if (node.left === null) {
// Если левый ребёнок пустой, вставляем сюда
node.left = newNode;
} else {
// Иначе рекурсивно идём глубже
this._insertNode(node.left, newNode);
}
} else {
// Если новое значение больше или равно текущему узлу
// Идём в правое поддерево
if (node.right === null) {
// Если правый ребёнок пустой, вставляем сюда
node.right = newNode;
} else {
// Иначе рекурсивно идём глубже
this._insertNode(node.right, newNode);
}
}
}
/**
* In-order обход (симметричный обход)
* Порядок: Левое поддерево → Корень → Правое поддерево
* Для BST это даёт отсортированную последовательность!
*/
inOrderTraversal(node = this.root, result = []) {
if (node !== null) {
// Сначала обходим левое поддерево (меньшие элементы)
this.inOrderTraversal(node.left, result);
// Затем добавляем текущий узел
result.push(node.value);
// Затем обходим правое поддерево (большие элементы)
this.inOrderTraversal(node.right, result);
}
return result;
}
}
/**
* Основная функция Tree Sort
*/
function treeSort(arr) {
// ШАГ 1: Создаём пустое дерево
const bst = new BinarySearchTree();
// ШАГ 2: Вставляем все элементы в дерево
// Каждая вставка находит правильную позицию согласно свойству BST
for (let i = 0; i < arr.length; i++) {
bst.insert(arr[i]);
}
// ШАГ 3: Выполняем in-order обход
// Это даст нам элементы в отсортированном порядке
const sorted = bst.inOrderTraversal();
// ШАГ 4: Копируем результат обратно в исходный массив
for (let i = 0; i < sorted.length; i++) {
arr[i] = sorted[i];
}
return arr;
}
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90, 88];
console.log("Исходный массив:", numbers);
treeSort(numbers);
console.log("Отсортированный массив:", numbers);
/**
* ВИЗУАЛИЗАЦИЯ РАБОТЫ на примере [5, 3, 7, 1, 9]:
*
* Построение дерева:
*
* Вставка 5:
* 5
*
* Вставка 3 (< 5, идём влево):
* 5
* /
* 3
*
* Вставка 7 (> 5, идём вправо):
* 5
* / \
* 3 7
*
* Вставка 1 (< 5, < 3, идём влево-влево):
* 5
* / \
* 3 7
* /
* 1
*
* Вставка 9 (> 5, > 7, идём вправо-вправо):
* 5
* / \
* 3 7
* / \
* 1 9
*
* In-order обход: 1 → 3 → 5 → 7 → 9
* Результат: [1, 3, 5, 7, 9] — отсортирован!
*/
/**
* ПОЧЕМУ РАБОТАЕТ:
*
* Свойство BST:
* - Все узлы в левом поддереве < текущего узла
* - Все узлы в правом поддереве > текущего узла
*
* In-order обход:
* 1. Сначала посещаем левое поддерево (меньшие элементы)
* 2. Затем текущий узел
* 3. Затем правое поддерево (большие элементы)
*
* Это автоматически даёт отсортированный порядок!
*/
// Пример с вырожденным деревом (худший случай)
const worstCase = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// Построит цепочку вправо (вырожденное дерево):
// 1
// \
// 2
// \
// 3
// \
// ...
// Высота = n, вставка каждого элемента O(n) → итого O(n²)
// Пример со сбалансированным деревом (лучший случай)
const bestCase = [5, 3, 7, 1, 4, 6, 9];
// Построит сбалансированное дерево:
// 5
// / \
// 3 7
// / \ / \
// 1 4 6 9
// Высота = log n, вставка каждого элемента O(log n) → итого O(n log n)С анализом сложностей
/**
* Tree Sort с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n log n) — сбалансированное дерево
* - Средний случай: O(n log n) — случайные данные обычно дают сбалансированное дерево
* - Худший случай: O(n²) — вырожденное дерево (цепочка)
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(n) — память для узлов дерева
* - O(h) — стек рекурсии для обхода, где h — высота дерева
* - Лучший случай: O(log n)
* - Худший случай: O(n)
*
* ОСОБЕННОСТИ:
* - НЕ стабильный (зависит от реализации вставки дубликатов)
* - Не in-place (требует O(n) память)
* - Онлайн-алгоритм (можно добавлять элементы динамически)
*/
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
/**
* Вставка в BST
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший/средний случай: O(log n) — высота сбалансированного дерева
* - Худший случай: O(n) — высота вырожденного дерева
*
* АНАЛИЗ:
* - На каждом уровне дерева делаем 1 сравнение
* - Количество уровней = высота дерева (h)
* - Сбалансированное: h = log₂(n) → O(log n)
* - Вырожденное: h = n → O(n)
*/
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
this._insertNode(this.root, newNode);
}
_insertNode(node, newNode) {
// Рекурсивный спуск по дереву: O(h)
// h — высота дерева
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
// Рекурсивный вызов уменьшает задачу
this._insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this._insertNode(node.right, newNode);
}
}
}
/**
* In-order обход
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n)
* - Посещаем каждый узел ровно один раз
* - Для каждого узла: O(1) операций (добавление в массив)
* - Итого: n узлов * O(1) = O(n)
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(n) для результирующего массива
* - O(h) для стека рекурсии, где h — высота
*/
inOrderTraversal(node = this.root, result = []) {
if (node !== null) {
// Обход: T(n) = T(left) + O(1) + T(right)
// Где T(left) + T(right) = n-1 узлов
// Итого: T(n) = O(n)
this.inOrderTraversal(node.left, result);
result.push(node.value); // O(1)
this.inOrderTraversal(node.right, result);
}
return result;
}
}
/**
* Tree Sort — основная функция
*
* ОБЩАЯ ВРЕМЕННАЯ СЛОЖНОСТЬ:
*
* ЛУЧШИЙ/СРЕДНИЙ СЛУЧАЙ — O(n log n):
* - Построение дерева: n вставок * O(log n) каждая = O(n log n)
* - Обход дерева: O(n)
* - Копирование: O(n)
* - Итого: O(n log n) + O(n) + O(n) = O(n log n)
*
* ХУДШИЙ СЛУЧАЙ — O(n²):
* - Построение дерева: n вставок * O(n) каждая = O(n²)
* - Обход: O(n)
* - Итого: O(n²)
*
* Худший случай возникает при:
* - Отсортированных или почти отсортированных данных
* - Обратно отсортированных данных
* - Монотонных последовательностях
*/
function treeSort(arr) {
const bst = new BinarySearchTree();
// ФАЗА 1: Построение дерева
// Сложность: O(n log n) в среднем, O(n²) в худшем
for (let i = 0; i < arr.length; i++) {
bst.insert(arr[i]); // O(log n) в среднем, O(n) в худшем
}
// ФАЗА 2: Обход дерева
// Сложность: O(n) всегда
const sorted = bst.inOrderTraversal();
// ФАЗА 3: Копирование
// Сложность: O(n)
for (let i = 0; i < sorted.length; i++) {
arr[i] = sorted[i];
}
return arr;
}
/**
* СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ:
*
* Tree Sort vs Quick Sort:
* ✓ Quick Sort: O(n log n) в среднем, проще реализация
* ✓ Tree Sort: можно добавлять элементы динамически
* ✗ Tree Sort: O(n²) на отсортированных данных (без балансировки)
*
* Tree Sort vs Heap Sort:
* ✓ Heap Sort: всегда O(n log n)
* ✓ Tree Sort: проще понять концептуально
* ✗ Tree Sort: требует больше памяти
*
* Tree Sort vs самобалансирующиеся деревья:
* ✓ AVL/Red-Black Tree: гарантированная O(n log n)
* ✗ Обычный BST: может деградировать до O(n²)
*/
// ПРИМЕРЫ ПРОИЗВОДИТЕЛЬНОСТИ:
// ЛУЧШИЙ СЛУЧАЙ: случайные данные → сбалансированное дерево
const bestCase = [5, 2, 8, 1, 9, 3, 7, 4, 6];
// Ожидаемая высота: ~log₂(9) ≈ 3-4
// Сложность: O(9 * log 9) ≈ O(27) операций
// ХУДШИЙ СЛУЧАЙ: отсортированные данные → вырожденное дерево
const worstCase = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// Высота дерева: 9 (цепочка)
// Вставка элемента i требует i сравнений
// Сложность: 1+2+3+...+9 = 45 = O(n²)
/**
* ОПТИМИЗАЦИЯ: использование самобалансирующегося дерева
*
* AVL Tree или Red-Black Tree гарантируют:
* - Высота дерева всегда O(log n)
* - Вставка всегда O(log n)
* - Итоговая сложность всегда O(n log n)
*
* НО: более сложная реализация с операциями балансировки
*/
console.log("Tree Sort лучший случай:", treeSort([...bestCase]));
console.log("Tree Sort худший случай:", treeSort([...worstCase]));См. также
- trees — двоичные деревья поиска (BST)