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

Вказівки

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

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

Скажімо, у нас є масив [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, автором якого є Тілл Тантау.