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

Если вы никогда не видели BST, то, увидев, как он выглядит, может намекнуть, почему у него такое название. Начиная сверху у нас есть корневой узел и левое и правое поддерево. В приведенном выше примере 25 является корневым узлом. Начало левых поддеревьев равно 20, а родительский узел для двух его дочерних узлов, так же, как правые поддеревья начинаются с 36, причем 30 и 40 являются его собственными дочерними узлами. Что определяет начало этих родительских узлов и последующих дочерних узлов?

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

Предположим, мы ищем значение в 8-м узле бинарного дерева поиска. Проходя по дереву от корня, вы проверяете так же, как было построено все дерево. Перемещаясь по каждому узлу, который вы проверяете, является ли узел меньше или больше каждого поддерева, затем вы продолжаете повторять процесс, пока не достигнете узла, который является исходным узлом, который вы ищете. При использовании двоичного дерева поиска в JavaScript вы запускаете тесты, начиная с начального условного оператора. Эти условия соблюдены? Если нет, мы переходим к следующему условному оператору, который скажет нам, в каком направлении двигаться, влево или вправо поддерево. Этот процесс повторяется до тех пор, пока мы, наконец, не достигнем пункта назначения.

Обход BST, как правило, прост, что объясняет временную сложность по отношению к размеру набора данных. Зная, как код для поиска значений, как строится BST, просто царапает поверхность. При использовании этой структуры данных вы можете удалять узлы и вставлять узлы там, где это необходимо, но когда это происходит, может потребоваться реструктуризация остальной части дерева на основе значений, оставшихся в дереве. Несмотря на все это, это показывает гибкость при использовании этой структуры данных.

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