Внедрение двоичного дерева поиска:
Давайте проясним одну вещь: если вы собираетесь реализовать BST, основное предположение состоит в том, что у вас есть значения, которые вы пытаетесь отсортировать в том порядке, в котором вы хотите, чтобы они были отсортированы. Если вы вызываете свое двоичное дерево поиска функции в вашей предыдущей функции, которая сортирует ваш массив значений, скорее всего, вы получите время выполнения O (n log n), что никому не нужно. На данном этапе игры я стараюсь поддерживать алгоритмы на уровне O(n), если не быстрее.
В большинстве случаев ваше двоичное дерево поиска должно иметь время выполнения O (log n), потому что, если мы ищем в массиве размера n и каждый раз уменьшаем массив вдвое, пока не получим желаемое значение, это может быть выражен как логарифм по основанию 2 от n, также известный как O (log n). Логарифмические функции растут очень медленно и обратны экспонентам, которые растут очень быстро. В худшем случае у вас много значений, время выполнения обычно составляет O (n).
Вот несколько графиков из Академии Хана, иллюстрирующих это:
Дальнейшее чтение:
