Эль Оширо
Когда я впервые начал изучать JavaScript и изучать основы циклов, я иногда тратил целую вечность, пытаясь найти оптимальные способы очень быстрой сортировки большого количества данных. Даже мне, начинающему программисту, казалось, что поиск с использованием грубой силы немного неэффективен и требует ненужного времени на просмотр избыточной информации. Только когда я начал изучать структуры данных во время посещения Грейс Хоппер, я начал ценить сложную, но нюансированную природу бинарных деревьев поиска.
Двоичные деревья поиска — это полезная древовидная структура, которая позволяет выполнять более быстрый поиск в больших коллекциях данных. Двоичные деревья поиска состоят из узловых объектов, содержащих часть сортируемых данных, самый верхний из которых называется корневым узлом. Кроме того, каждый узел содержит не более двух дочерних узлов, называемых левым и правым дочерними элементами. Однако к этим узлам есть некоторые ограничения — значение в каждом узле должно быть больше или равно значению, хранящемуся в левом дочернем элементе, и меньше или равно значению, хранящемуся в правом дочернем элементе.
Когда мне впервые представили эту концепцию в лекции Грейс Хоппер, я был впечатлен практическим применением сокращения времени поиска моих поисковых функций. В среднем бинарный поиск занимает O(log n) времени, что казалось впечатляющим, но в то время я не понимал и не понимал, для чего на самом деле можно использовать BST.
Некоторое время спустя мне стало скучно, и я решал случайные головоломки на Codewars, и я помню, что столкнулся с проблемой, которая оказалась для меня довольно сложной. В головоломке подсказка требовала от меня написать функцию, которая будет вставлять заданную входную строку в соответствующее место в массиве, организованном в алфавитном порядке. Например, предположим, что нам дан массив из 26 строк и входная строка, например:
let AlphaArray = [‘яблоко’, ‘мальчик’, ‘кот’, …, ‘зоопарк’]
пусть inputString = ‘bat’
Для меня, как для наивного начинающего программиста, самым простым ответом было бы использовать цикл for и перебирать заданный массив до тех пор, пока мы не найдем строку, которая в алфавитном порядке будет дальше в массиве, чем сама входная строка. В нашем примере мы обнаружим, что 1-й индексированный элемент, «мальчик», будет фиксированным элементом, который должен быть организован в алфавитном порядке дальше, чем сама входная строка; таким образом, нам нужно будет вставить нашу входную строку «bat» в позицию индекса 1 и переместить оставшиеся элементы (от 1 до 25 в исходном массиве) вниз на одну позицию дальше (таким образом, они будут проиндексированы от 2 до 26). Я решил эту проблему после приятного долгого размышления и пошел дальше, но что-то меня все время беспокоило — это казалось простым, но слишком простым. Технически эта функция будет перемещаться за логарифмическое время O(n), что не очень медленно, но я подумал, что должен быть лучший способ сделать это.
Введите бинарные деревья поиска. Имея отсортированный массив данных, можно увеличить как скорость, так и эффективность поиска, как следует из названия, разделив наши данные на непрерывно разветвляющуюся структуру данных. Проще говоря, BST позволит вам сортировать ваши данные в ряд узлов, где каждый узел состоит из родительского значения и дочерних значений, больших и/или меньших, чем родительское значение. Взгляните на диаграмму ниже.
На этой диаграмме значение 1-го узла равно 8, и этот узел также содержит двух дочерних элементов, состоящих из значений, больших и меньших, чем значение родителя (10 и 3 соответственно). Эти дочерние элементы также могут сами содержать дочерние элементы, представляющие значения больше/меньше их родительского значения. Этот процесс разветвления будет продолжаться до тех пор, пока ваш набор данных не будет исчерпан, и конечным результатом будет хорошо отсортированное дерево данных. Еще полезнее знать, что BST намного быстрее выполняет поиск, удаление и вставку, чем при использовании массива, логарифмическое время O(log n) по сравнению со временем массива O(n). Вау!
Помимо того, что BST интересны с технической точки зрения и более эффективны, они также являются распространенной темой на собеседованиях по техническим вопросам. Рассмотрим этот вопрос начального уровня, который часто появляется в интервью.
Подсказка. Дан корневой узел двоичного дерева поиска (BST) и значение. Вам нужно найти узел в BST, значение которого равно заданному значению. Возвратить поддерево с корнем этого узла. Если такой узел не существует, вы должны вернуть NULL.
Пример проблемы 1:
Например,
Учитывая дерево:
4
/ \
2 7
/ \
1 3
И значение для поиска: 2
Вы должны вернуть это поддерево:
2
/ \
1 3
Более того, если бы мы хотели найти значение 5 в приведенном выше примере, мы бы вернули NULL, потому что 5 не существует в дереве.
Найдите минутку, чтобы подумать, как вы могли бы решить эту проблему, и когда вы почувствуете, что готовы, прокрутите вниз, чтобы найти решение.
Есть несколько способов решить эту проблему, но мне нравится простая элегантность рекурсивного решения.
function binarySearch (узел, значение) {
если (узел === null || node.value === значение) {
узел возврата
} иначе если (значение ‹ node.value) {
двоичный поиск (узел.левый, значение)
} иначе если (значение › node.value) {
binarySearch (узел.право, значение)
}
}
Таким образом, в нашем примере дерева выше…
4
/ \
2 7
/ \
1 3 со значением поиска 2…
Мы бы подключили самый верхний узел дерева и 2 в качестве наших входов. Этот узел не имеет значения null и его значение 4 не равно 2, поэтому мы переходим ко второму оператору if. Затем мы увидели бы, что мы выполнили это условие, поскольку 2 меньше 4, и поэтому мы бы рекурсивно вызвали нашу функцию binarySearch, только на этот раз с нашим дочерним узлом 2 в качестве нашего входного узла. Мы снова запускаем функцию, и на этот раз мы выполняем условие нашего первого оператора if и возвращаем наш входной узел 2. Вы можете логически понять, как это могло бы работать, если бы мы также имели значение больше 4 (т.е. 7).
Это был краткий обзор распространенной задачи бинарного поиска, и я счел невероятным, насколько простыми и в то же время сложными являются BST. Надеюсь, вы сможете использовать эти знания самостоятельно, когда столкнетесь с BST в своих путешествиях по программированию! До скорого… :)
