Сложность дерева двоичного поиска на основе значений

Question

Я создал двоичное дерево поиска на языке Си, когда я тестирую свое дерево, операции вставки и поиска выполняются по разному.Например, у меня есть два сценария: вставка случайных значений от 1 до 10000 и вставка отсортированных значений от 1 до 10000. Когда я вставляю случайные значения от 1 до 10000 в мой BST, тогда это занимает меньше времени, чем вставка отсортированных значений от 1 до 10000 вмой BST.
то же самое для операции поиска, которая будет выполняться в моем BST, это занимает меньше времени, пока я ищу по этим случайным значениям, но занимает слишком много времени при поиске отсортированных значений в моем BST.Теперь, проблема в сложности времени, может кто-нибудь объяснить, как это обрабатывается?какова временная сложность для всех четырех случаев?

Примечание: Вставка и поиск в отсортированных значениях занимают почти одно и то же время, а поиск занимает немного больше времени!

Answer 1

Использовать AVL Tree.Это сохранит ваше дерево сбалансированным, и вы всегда получите время поиска по журналу (n)

Answer 2

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

Например, если вы вставляете от 1 и увеличиваете, вы получите

 1
/\
  2
  /\
    3
    /\
     ...

где правильный «позвоночник» является связанным списком.