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

Вказівки

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

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

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