, так что я знаю, что операция в BST работает в режиме журнала из-за половины структуры, мне было интересно, какая временная сложность будет, если вы ищете значение, которое не было в структуре.Сложность времени BST
Средняя временная сложность случая будет равна O (log n), а наихудшим случаем будет O (n). Чтобы понять O (журнал N) сложность можно сослаться What does O(log n) mean exactly?
Это изображение объяснит вам, как часть:
Я также рекомендую пройти через wiki для деталей.
Он все равно будет O (log n). Подумайте так, он будет искать непрерывную половину, пока он не сможет найти.
Спасибо за ответ, но как он узнает, больше или меньше значение, чем корень, чтобы узнать, с какой стороны начать искать? У меня создалось впечатление, что он сделает одну сторону, а затем сделает следующее и поймет, что ее нет –
Вы говорите о BST. A BST будет располагаться следующим образом: 'leftChild
ktkaushik