Дерева пошуку з двома обмеженнями: Вставка, Пошук та… |…

Одна властивість, три операції

Дерево пошуку з двома ключами (BST) зберігає ключі відповідно до однієї властивості: для кожного вузла всі елементи в його лівому піддереві менші за нього, а всі елементи в його правому піддереві більші за нього. Ця одна властивість достатньо, щоб пошук, вставка та видалення завжди слідували б однаковому шаблону – порівнювати цільовий ключ з поточним вузлом і рекурсивно йти ліворуч або праворуч – перетворюючи те, що могло б бути лінійним скануванням, на шлях вниз по дереву.

search(node, key):
  if node is null: return not found
  if key == node.key: return node
  if key < node.key: return search(node.left, key)
  else:                return search(node.right, key)
insert: search until you fall off the tree, attach a new leaf there
delete: 0 or 1 child -> splice node out; 2 children -> replace with in-order successor

жива демонстрація · пов'язана симуляція● LIVE

Складність залежить повністю від форми дерева

Усі три операції коштують O(h), де h – висота дерева. Для ідеально збалансованого дерева з n ключами, h = O(log n), тому пошук, вставка та видалення також є логарифмічними. Однак, BST, побудований шляхом вставки ключів у вже відсортованому порядку, деградує до прямої ланцюжка, з h = n − 1: дерево стає структурно пов’язаним списком, і кожна операція має складність O(n). Інваріант BST гарантує правильність; він не гарантує баланс.

Проходження в порядку номеру відновлює відсортований порядок безкоштовно

Відвідування BST (двостороннього пошукового дерева) в порядку номеру (спочатку ліве піддерево, потім вузол, потім правий піддерево, рекурсивно) завжди дає ключі в зростаючому відсортованому порядку, що є прямим наслідком інваріанту пошуку. Це одна з причин використання BST замість хеш-таблиці, коли потрібні запити діапазону або відсортоване ітерування: хеш-таблиця забезпечує середній час доступу O(1), але не надає порядку, тоді як збалансований BST забезпечує час доступу O(log n) та вихід даних у відсортованому вигляді як побічний продукт.

AVL дерева: балансування за допомогою ротацій

AVL дерево (Adelson-Velsky та Landis, 1962) відновлює логарифмічну гарантію шляхом забезпечення балансової інваріантності після кожного вставлення та видалення: для кожного вузла різниця висот його лівого та правого піддерев не перевищує 1. Коли операція порушує цю інваріантність, дерево виконує ротацію – локальну перебудову кількох покажчиків, яка відновлює баланс без порушення властивості пошукового дерева.

Праворучна ротація навколо вузла y (виправляючи ліво-лівий дисбаланс): y x / \ / \ x C -> A y / \ / \ A B B C (Ліворучна ротація є дзеркальним відображенням правої) Оскільки ротація лише перерозподіляє фіксовану кількість покажчиків, і потрібно виправити не більше одного дисбалансу на рівні шляху до кореня, кожне вставлення або видалення коштує O(log n) для пошуку плюс O(log n) у найгіршому випадку для ребалансування. AVL дерева підтримують висоту протягом приблизно 1.44 log2(n), що є більш жорстким обмеженням, ніж у червоно-чорного дерева, яке трохи послаблює баланс, але робить менше ротацій на оновлення.

right rotation around node y (fixes left-left imbalance):
      y                x
     / \                / \
    x   C     ->      A   y
   / \                    / \
  A   B                  B   C
(a left rotation is the mirror image)

Чому балансування варте витрат на обслуговування

Уся привабливість BST (двоствольового пошукового дерева) над простим відсортованим масивом полягає в O(log n) вставці та видаленні замість O(n) переміщення. Ця перевага зникає, коли дерево дозволяють деградувати. Варіанти самобалансування – AVL, червоно-чорне дерева, дерева сплайсінгу – усі існують для того, щоб гарантія O(log n) зберігалася для будь-якої послідовності операцій, а не лише сприятливих випадків, на додаток до фактора балансу для кожного вузла та періодичної роботи з обертання.

Frequently asked questions

Чому бінарне дерево пошуку може стати таким же повільним, як і з'єднаний список?

Інкваріант бінарного дерева пошуку обмежує лише відносну упорядкованість, а не форму. Вставка ключів у вже відсортованому порядку призводить до того, що кожен новий вузол приєднується як правопохідний потомок попереднього, створюючи пряму ланцюжок висотою n-1 замість збалансованого дерева висотою log n — кожне пошукове операція коштує O(n).

Що робить обертання AVL?

Це локальне, константний час переупорядкування кількох вказівок батько-дитина навколо точки дисбалансу, яке відновлює інваріант висоти балансу, зберігаючи при цьому інваріант упорядкованості BST. Послідовність цих обертань, максимум O(log n) з них, усуває будь-який дисбаланс, спричинений однією вставкою або видаленням.

Чи завжди відсортований обхід у порядку (in-order traversal) для незбалансованого бінарного дерева пошуку?

Так — упорядкованість виникає виключно з інваріанту ліворуч менше, праворуч більше, який зберігається незалежно від висоти та балансу дерева. Незбалансоване дерево пошуку дає відсортоване вихідні дані так само надійно, як і збалансоване; лише час обходу та складність пошуку/вставки/видалення залежать від балансу.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Binary Search Tree і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію Binary Search Tree

Дерева пошуку з двома обмеженнями: Вставка, Пошук та Збалансування AVL