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

Вказівки

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

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

Уявімо, що в нас є масив [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 Тілла Тантау.