Поиск места элемента в списке - базовая задача для разработчиков. Это может быть определение положения игрока в рейтинге, статистика игрока по фрагам в онлайн-игре или, например, поиск положения товара в списке, отсортированного по цене. Решим похожую задачу: найдём место новому футболисту в рейтинге десяти лучших игроков мира.
Как правило, для создания списков в JS разработчики пользуются массивами. Это логично, ведь это базовая структура, которая представлена в движке JS и чтобы использовать другой вид списков, нужно проделать большую: написать заново все методы для работы со списком, протестировать их. Не всегда результат стоит затраченных усилий.
const list = [94, 94, 92, 90, 90, 89, 88, 88, 87];
Чтобы найти порядковый номер элемента в массиве JS, нужно воспользоваться прямым перебором: перебрать все элементы по порядку, сравнивая их с образцом.
По принципу прямого перебора работают методы indexOf, find и findIndex, встроенные во все массивы.
const list = [94, 94, 92, 90, 90, 89, 88, 88, 87];
const newElement = 91;
const indexOfNewElement = list.findIndex(it => newElement < it);
list.splice(indexOfNewElement, 0, newElement);
В худшем случае, если элемент находится в конце списка или его в списке нет, поиск займет столько же итераций, сколько элементов содержится в списке: в ходе поиска будет проверен каждый элемент списка.
Проблема такого решения в том, что производительность этого кода падает вместе с увеличением количества элементов в списке. Если список относительно небольшой и счет количества элементов идет на сотни, проблем быть не должно, но когда список становится большим и количество элементов начинает измеряться тысячами, чтобы вставить один элемент приходится проверять тысячу остальных.
Если список упорядочен и мы точно знаем, что элементы в нем отсортированы, можно использовать двоичный поиск, он заметно сокращает количество итераций, которое нужно провести, чтобы найти элемент.
Основная идея двоичного поиска - постоянное разделение списка пополам. Поиск начинается со среднего элемента. Первое сравнение, мы производим с элементом, который находится в середине списка. Список упорядочен, поэтому мы знаем, что все элементы, которые больше среднего находятся в левой части списка, а те элементы, которые меньше среднего - в правой.
"Больше" или "меньше", это условные понятия: список может быть отсортирован в любом порядке и критерий сравнения может быть любым. Под "больше" подразумевается что один элемент стоит в списке раньше другого, а под "меньше" - что позже.
После первого сравнения, если мы не нашли нужный элемент, мы понимаем в какую сторону нам двигаться дальше. Если искомый элемент больше среднего, мы отправляемся в левую половину списка, а если меньше среднего - в правую и повторяем процедуру на ней: находим элемент посередине, сравниваем с ним и так далее, пока не найдем место для элемента.
Проблема двоичного поиска в массивах JS заключается в том, что, получая массив, мы не можем быть уверены в том, что он отсортирован. У объектов массива нет никаких признаков, которые бы показывали, отсортирован массив или нет и проверить порядок элементов можно только перебрав их все по порядку. Такое решение нам не подходит, потому что в этой ситуации мы опять возвращаемся к прямому перебору всех элементов списка в лучшем случае, а в худшем случае, чтобы алгоритм заработал, массив нужно отсортировать, что займет еще какое-то количество повторений.
Чтобы гарантировать, что двоичный поиск будет работать, мы можем перераспределить данные так, чтобы они были заведомо упорядоченными. Напишем структуру данных, которая будет гарантировать, что двоичный поиск будет работать правильно. Двоичный поиск всегда начинается с середины списка, поэтому первым в структуре поставим элемент, с которого начинается поиск.
После сравнения с первым элементом в списке, у нас есть только два варианта: мы можем оказаться в левой части списка и сравнивать наше значение со средним значением левой части или мы можем оказаться в правой части и сравнивать значение со средним значением правой части.
Мы можем записать для среднего элемента ссылки на те элементы, с которыми будет производиться сравнение после него: для середин левой и правой половины списков, а потом рекурсивно продолжим разбиение списка на половины, пока у нас не закончатся элементы.
const first = 90;const first = {
val: 90,
left: {
val: 92,
},
right: {
val: 88,
},
};const first = {
val: 90,
left: {
val: 92,
left: {
val: 94,
left: {
val: 94
}
},
right: {
val: 90,
},
},
right: {
val: 88,
left: {
val: 89,
},
right: {
val: 88,
right: {
val: 87,
},
},
},
};Сделаем структуру единообразной, такой, чтобы все объекты были одинаковыми. Если объект крайний в поиске и после него некуда дальше идти, всё равно добавим ему поля left и right, но запишем в них null.
В результате мы получили дерево, в корне у которого стоит элемент, с которого начинается поиск, а его потомки: элементы, по которым поиск продолжается. Из-за того, что у каждого узла только два потомка, то есть при поиске есть только два варианта развития событий, дерево называется двоичным или бинарным.
Мы получили структуру, перемещение по которой идеально подходит для двоичного поиска: она заведомо упорядочена так, что поиск сработает, нам не нужно гадать, в правильном ли порядке находятся элементы, ведь мы сами расставили их так, как удобно нам для поиска.
Поиск элемента начинается с корня и всегда идет вниз. Если искомый элемент больше того, на котором мы находимся, нужно перейти в правую ветку дерева, если меньше - в левую.
Вставка производится точно так же как и поиск, с той разницей, что новая запись вставляется только на место null-листа.
const insert = (tree, value) => {
if (value >= tree.val) {
if (tree.left === null) {
tree.left = {
val: value,
left: null,
right: null,
};
} else {
insert(tree.left, node);
}
} else {
if (tree.right === null) {
tree.right = {
val: value,
left: null,
right: null,
};
} else {
insert(tree.right, node);
}
}
}
Имплементация упорядоченного списка в виде двоичного дерева дает прирост скорости для записи и поиска элементов в списке относительно обычного массива. В зависимости от размеров списка, разница в скорости может быть стократной.
Любой список должен иметь интерфейс forEach для последовательного перебора элементов. В случае двоичного дерева эту задачу можно решить используя перебор внутренним порядком, по-английски он назвается Inorder. Работает он так:
const inorder = (node, visit) => {
if (node.left) inorder(node.left, visit);
visit(node.val);
if (node.right) inorder(node.right, visit);
};Под посещением можно понимать любое действие, которое мы выполняем с элементом. Например, если мы перебираем дерево, чтобы вывести все его элементы по порядку, то посещением в этом случае будет команда вывода, например console.log
Используя внутренний перебор, можно перебрать все элементы по порядку, несмотря на то, что хранятся они в другом порядке
const inorder = (node, visit) => {
if (node.left) inorder(node.left, visit);
visit(node.val);
if (node.right) inorder(node.right, visit);
};
Дерево работает гораздо лучше простого массива для поиска и вставки элементов, но когда дело доходит до удаления, могут начаться сложности. Если удаляемый элемент является листом дерева, то есть не имеет потомков, то удаление будет тривиальным, но сложноcти начинаются когда нужно удалить элемент с потомками: в этом случае нужно будет не просто убрать элемент, который мы хотим удалить, но и переставить другие элементы в дереве.
Всегда существует несколько способов собрать дерево из одних и тех же элементов и какие-то способы могут оказаться неэффективными. Если вставить в дерево подряд все элементы по возрастанию, дерево превратится в простой список. Это не плохо, просто в этой ситуации теряются все преимущества бинарного поиска и никакого прироста в скорости относительно обычного массива не выйдет. Если хочется этого избежать, то нужно использовать балансировку: делать так, чтобы элементы в дереве стояли так, чтобы дерево не было слишком глубоким.
Чтобы сбалансировать дерево самым простым образом, сначала дерево нужно вытянуть в так называемую "лиану" - дерево, в котором у каждого элемента есть только правый потомок - а потом последовательно пройти по всем элементам дерева и "повернуть" их в левую сторону. Подробней, как делается левый поворот можно почитать в Википедии и в дополнительных материалах к этой статье.
Существуют вариации двоичных деревьев, которые называются самобалансирующимися. Самые популярные варианты таких деревьев: красно-чёрное и AVL-деревья. В них узлы содержат дополнительную информацию, которая помогает держать дерево сбалансированным.
Использование двоичных деревьев поиска для списков выгодно если список упорядочен, он достаточно большой и основные действия, которые производятся со списком - это вставка и поиск.
Список должен быть упорядоченным, чтобы на нём мог работать двоичный поиск. Если список состоит из случайных элементов, то никакого смысла использовать двоичное дерево нет: на случайных списках двоичный поиск работать не будет.
Список достаточно большой: преимущества двоичного поиска начинают проявляться на относительно больших списках. Незначительный прирост скорости будет ощущаться и на 100 элементах, но когда порядок доходит до 1000 прирост будет существенным и может оказаться стократным.
Основные действия, которые выполняются со списком: вставка и поиск элементов. Если список нужен для того, чтобы обращаться к его элементам по порядковому номеру, то массив будет удобней.
Код главы на CodePen
Библиотека для работы с бинарными деревьями на гитхабе
Ссылки на тесты производительности
Балансировка деревьев
Самобалансирующиеся деревья: