Какова лучшая и худшая производительность поиска для сбалансированного BST?

Question

Какова лучшая и худшая производительность поиска для сбалансированного BST? как я могу объяснить в одном предложении, когда происходит каждый случай?

Answer 1

Поиск выполняется по пути от корня к листу, длина которого Log n в сбалансированном дереве.

Лучший случай: попадание в первый узел, O (1) *.

Худший случай: попадание в последний узел O (Log n).

---

Это верно, если реализация выполняет тест на равенство, позволяя досрочное завершение. В противном случае полный путь будет использоваться во всех случаях.

Answer 2

Для сбалансированного BST:

• Лучший вариант: O (1) Когда узел, который вы ищете, находится в корне (так что вы нужно только одно сравнение, чтобы найти его)
• Наихудший случай: O (logn), когда искомый узел является листом узел (то есть нижняя часть дерева)

Answer 3

Лучший случай: когда искомый элемент находится в корне дерева. Вы получаете O (1).

Наихудший случай: когда искомый элемент находится на листе самой длинной ветви, дерево является односторонним. Вы получаете O (n). Вы получаете O (log n).