Яка складність пошуку вузла в бінарному дереві?

Складність пошуку вузла в бінарному дереві залежить від його структури: збалансоване воно чи ні.

1. У збалансованому бінарному дереві пошуку (BST):

Кожне порівняння виключає половину елементів, що залишилися. Середня та найкраща складність: O(log n)

2. У незбалансованому дереві:

Якщо елементи вставлені, наприклад, за зростанням, дерево перетворюється на ланцюжок (список). Найгірша складність: O(n)

3. Приклад роботи:

Щоб знайти 9: 8 → 10 → 9 - три кроки (≈ log₂7 ≈ 3).

Підсумок:

• Середній випадок (збалансоване дерево): O(log n)
• Найгірший випадок (вироджене дерево): O(n)