Двійкове дерево пошуку

Вказівки

Вставляйте числа в бінарне дерево пошуку та шукайте їх у ньому.

Коли потрібно подати відсортовані дані, масив не дуже добре підходить на роль структури даних.

Уявімо, що в нас є масив [1, 3, 4, 5], і ми додаємо до нього 2, тож він стає [1, 3, 4, 5, 2]. Тепер нам доведеться знову сортувати весь масив! Можна зробити краще, якщо зрозуміти, що нам потрібно лише звільнити місце для нового елемента [1, nil, 3, 4, 5], а потім покласти цей елемент у звільнене місце. Але це все одно вимагає зсунути багато елементів на одну позицію.

Бінарні дерева пошуку, натомість, працюють із відсортованими даними значно ефективніше.

Бінарне дерево пошуку складається з низки зʼєднаних вузлів. Кожен вузол містить фрагмент даних (наприклад, число 3), змінну з назвою left і змінну з назвою right. Змінні left і right указують на nil або на інші вузли. Оскільки ці інші вузли, своєю чергою, мають під собою ще інші вузли, ми кажемо, що змінні left і right указують на піддерева. Усі дані в лівому піддереві менші або дорівнюють даним поточного вузла, а всі дані в правому піддереві більші за дані поточного вузла.

Наприклад, якби в нас був вузол із даними 4 і ми додали дані 2, наше дерево мало б такий вигляд:

      4
     /
    2

Якби ми потім додали 6, воно мало б такий вигляд:

      4
     / \
    2   6

Якби ми потім додали 3, воно мало б такий вигляд

       4
     /   \
    2     6
     \
      3

А якби ми потім додали 1, 5 і 7, воно мало б такий вигляд

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Подяка

Зображення створив habere-et-dispertire, використавши PGF/TikZ Тілла Тантау.

Реалізація

Реалізувати ефективну структуру дерева, яку можна змінювати, у Cairo (чи будь-якій чисто функціональній мові з незмінною памʼяттю) складно, бо ці мови створені так, щоб уникати зміни даних після їх створення. Ця незмінність означає, що замість оновлення вузла дерева безпосередньо потрібно щоразу створювати нову версію дерева, коли ми його змінюємо.

Щоб показати, чому це так, уявімо просту структуру бінарного дерева, де в кожного вузла є лівий і правий дочірній вузол. Припустімо, ми починаємо з такого маленького дерева:

       1
      / \
     2   3

Тепер припустімо, що ми хочемо додати новий вузол 4 як лівий дочірній вузол вузла 2. У чисто функціональній мові (як-от Cairo чи Haskell) памʼять незмінна, тож ми не можемо просто додати вузол 4 безпосередньо до 2. Натомість нам доводиться створювати нову версію кожного вузла на шляху від кореня до зміненого вузла, бо кожен вузол на цьому шляху тепер указує на нове або змінене піддерево.

Ось як відбувався б цей процес:

1. Додаємо вузол 4 до вузла 2:

   • Створюємо нову версію вузла 2, у якій 4 тепер лівий дочірній вузол.

       2'
      / 
     4   
   

2. Оновлюємо кореневий вузол:

   • Оскільки вузол 1 спочатку вказував на старий 2, ми створюємо нову версію кореневого вузла 1', яка тепер указує на оновлений вузол 2' ліворуч і зберігає вузол 3 праворуч.

       1'
      / \
     2'  3
   

Отже, отримане дерево має такий вигляд:

       1'
      / \
     2'  3
    /
   4

Це нове дерево (1') усе ще нагадує початкове, але з оновленим шляхом. Головне ось у чому: нам довелося заново створити кожен вузол уздовж шляху (1 до 2), щоб зберегти незмінність, адже наявні вузли не можна змінити на місці. Початкове дерево все ще існує (наприклад, для всіх посилань на його початковий корінь 1), а це нове дерево представляє змінений стан.

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