Корінь без дерева

2024
| Коментарів немає

10.3: Вкорінені дерева

Що відрізняє вкорінені дерева від неспрямованих дерев, полягає в тому, що вкорінене дерево містить відмінну вершину, яку називають коренем. Розглянемо дерево на малюнку \(\PageIndex<1>\) . Вершина \(A\) була позначена коренем дерева. Якщо ми виберемо будь-яку іншу вершину в дереві, наприклад, \(M\text\) ми знаємо, що існує унікальний шлях від \(A\) до \(M\text<.>\) Вершини на цьому шляху, \((A, D, K, M)\text\) описуються генеалогічними термінами:

  • \(M\) є дитиною \(K\) (так є \(L\) )
  • \(K\) є \(M\) батьком.
  • \(A\text\) \(D\text\) і \(K\) є \(M\) предками.
  • \(D\text\) \(K\text\) і \(M\) є нащадками \(A\text\)

Ці генеалогічні відносини часто легше візуалізувати, якщо дерево переписано так, щоб діти розташовувалися нижче батьків, як на малюнку \(\PageIndex\) .

За допомогою цього формату легко побачити, що кожну вершину в дереві можна розглядати як корінь дерева, яке містить, крім себе, всіх своїх нащадків. Наприклад, \(D\) це корінь дерева, який містить \(D\text\) \(K\text\) \(L\text\) і \(M\text<.>\) Крім того, \(K\) це корінь дерева, яке містить \(K\text\) \(L\text\) і \(M\text<.>\) Нарешті, \(L\) і \(M\) є корінням дерев, які містять тільки себе. З цього спостереження ми можемо дати формальне визначення вкоріненого дерева.

Визначення \(\PageIndex\) : Rooted Tree

  1. Основа: Дерево без вершин – це вкорінене дерево (порожнє дерево).
  2. Одинарна вершина без дітей – це вкорінене дерево.
  3. Рекурсія: \(T_1, T_2,\ldots,T_r\text\) \(r\geq 1\text\) Дозволяти бути неспільні вкорінені дерева з корінням \(v_1\text\) \(v_2, \ldots \text\) \(v_r\text\) відповідно, і нехай \(v_0\) буде вершина, яка не належить жодному з цих дерев. Потім вкорінене дерево, вкорінене в \(v_0\text\) отримується шляхом створення \(v_0\) батьківських вершин \(v_1\text\) \(v_2, \ldots\text\) і \(v_r\text\) Ми називаємо \(T_1, T_2, \ldots, T_r\) піддерева більшого дерева.

вкоріненого дерева – це кількість ребер, які відокремлюють вершину від кореня. Рівень кореня дорівнює нулю. Глибина дерева – це максимальний рівень вершин у дереві. Глибина дерева на малюнку \(\PageIndex\) три, що є рівнем вершин \(L\) і \(M\text<.>\) вершин \(E\text\) \(F\text\) \(G\text\) \(H\text\) \(I\text\) \(J\text\) і \(K\) мають рівень два. \(B\text\) \(C\text\) і \(D\) знаходяться на першому рівні і \(A\) мають нульовий рівень.

Приклад \(\PageIndex\) : A Decision Tree

Малюнок 2.1.1 – це вкорінене дерево з початком як корінь. Це приклад того, що називається деревом рішень.

Приклад \(\PageIndex\) : Tree Structure of Data

Одним із ключів до роботи з великими обсягами інформації є її послідовна, логічна організація. – це схема організації даних. Простим прикладом структури даних може бути інформація, яку приймальний відділ коледжу може тримати на своїх заявників. Елементи можуть виглядати приблизно так:

\ begin \ begin Заявник & = (Ім’я, середній початковий, прізвище, адреса вулиці,\\ & Місто, штат, поштовий індекс, домашній телефон, мобільний телефон, адреса електронної пошти,\\ & середня школа, майор, додаток платна, математика SAT,\\ & Рекомендація 1, Рекомендація 2, Рекомендація 3)\ кінець \ кінець

Така структура називається «плоский напилок».

Електронну таблицю можна використовувати для упорядкування даних таким чином. Хоча структура «плоского файлу» часто адекватна, є переваги кластеризації деякої інформації. Наприклад, інформація про заявника може бути розбита на чотири частини: ім’я, контактну інформацію, середню школу та дані програми:

\ begin \ begin Заявник & = ((Ім’я, середнє початкове, прізвище),\\ & (адреса вулиці, місто, штат, поштовий індекс),\\ & (домашній телефон, мобільний телефон),\\ &середня школа,\\ & (Майор, платна програма, (Математика, Вербальна SAT),\\ & (Рекомендація 1, Рекомендація 2, Рекомендація 3))\ end < спліт>\ end

Першим пунктом у кожному ApplicantItem є список \((FirstName, MiddleInitial, LastName)\text\) , у якому кожен елемент у цьому списку є єдиним полем вихідного плоского файлу. Третій елемент – це просто єдиний предмет середньої школи з плоского файлу. Дані заявки – це список і один з його пунктів, сам по собі список з рекомендаційними даними для кожної рекомендації, яку має заявник.

Організацію цих даних можна візуалізувати за допомогою вкоріненого дерева, такого як на малюнку \(\PageIndex\) .

Малюнок \(\PageIndex\) : Дані заявника в кореневому дереві

Загалом, ви можете представляти елемент даних, \(T\text\) як вкорінене дерево з \(T\) коренем та піддеревом для кожного поля. Ті поля, які є більш ніж одним елементом, є корінням подальших піддерев, тоді як окремі елементи не мають додаткових дочірніх елементів у дереві.

Алгоритм Крускала

Альтернативний алгоритм побудови мінімального остовного дерева використовує ліс вкорінених дерев. Спочатку опишемо алгоритм найпростішими словами. Після цього ми опишемо, як використовуються вкорінені дерева для реалізації алгоритму. Наостанок ми продемонструємо реалізацію алгоритму SageMath. У всіх версіях цього алгоритму припустимо, що \(G = (V, E, w)\) це зважений неорієнтований граф з \(\lvert V\rvert = m\) і \(\lvert E\rvert = n\text<.>\)

Алгоритм \(\PageIndex\) : Kruskal’s Algorithm – Informal Version

  1. Сортувати ребра \(G\) за зростанням відповідно до ваги. Тобто,
    \ begin i\ leq j\ ліворуч w\ ліворуч (e_j\ право)\ leq w\ left (e_j\ right)\ text \ end
  2. Перейдіть вниз по списку з кроку 1 і додайте ребра до набору (спочатку порожніх) ребер, щоб набір не утворював цикл. Коли зустрічається ребро, яке створить цикл, ігноруйте його. Продовжуйте вивчати \(m – 1\) ребра, доки не буде вибрано обидва ребра або ви не дійдете до кінця списку країв. Якщо вибрано \(m – 1\) ребра, ці ребра складають мінімальне остовне дерево для \(G\text\) Якщо вибрано менше \(m – 1\) країв, \(G\) то не буде з’єднано.

Крок 1 може бути виконаний за допомогою однієї з будь-якої кількості стандартних процедур сортування. Використовуючи найбільш ефективну процедуру сортування, час, необхідний для виконання цього кроку \(n \log n\text<.>\) , пропорційний Другий крок алгоритму, також складності \(n \log n\) часу, – це той, який використовує ліс вкорінених дерев, щоб перевірити, чи слід додати край до набору охоплюючих.

Алгоритм \(\PageIndex\) : Kruskal’s Algorithm

  1. Сортувати ребра \(G\) за зростанням відповідно до ваги. Тобто,
    \ begin i\ leq j\ ліворуч w\ ліворуч (e_j\ право)\ leq w\ left (e_j\ right)\ text \ end
    1. Ініціалізувати кожну вершину в V, щоб бути коренем власного вкоріненого дерева.
    2. Спускайтеся вниз по списку ребер, доки не буде завершено або не буде вичерпано список країв. Для кожного ребра \(e =\left\\text\) ми можемо визначити, чи можна e додати до набору остоків без формування циклу, визначаючи, чи дорівнює корінь \(‘s\) дерева кореню \(‘s\) дерева. Якщо два кореня рівні, то ігноруйте е Якщо коріння різні, то ми можемо додати е до набору. Крім того, ми зливаємо дерева, які \(v_1\) і \(v_2\) належать. Це досягається шляхом перетворення \(‘s\) root батьком \(‘s\) root або навпаки.
    1. Оскільки ми запускаємо алгоритм Крускала з \(m\) дерев і кожне додавання ребра зменшує кількість дерев на одиницю, ми закінчуємо алгоритм одним кореневим деревом, якщо існує остовне дерево.
    2. Вкорінене дерево, яке ми розробляємо в алгоритмі, не є самим остовним деревом.

    Примітка SageMath – Реалізація алгоритму Крускала

    Алгоритм Крускала було реалізовано у Sage. Ми проілюструємо, як може бути сформовано остовне дерево для зважених графіків. Для початку створюємо такий графік

    Ми створимо графік, використовуючи список трійок форми \((\text,\text, \text)\text<.>\) \(weighted\) Метод говорить Sage розглядати мітки як ваги.

    edges=[(1, 2, 4), (2, 8, 4), (3, 8, 4), (4, 7, 5), (6, 8, 5), (1, 3, 6), (1, 7, 6), (4, 5, 6), (5, 10, 9), (2, 10, 7), (4, 6, 7), (2, 4, 8), (1,8, 9), (1, 9, 9), (5, 6, 9), (1, 10, 10), (2, 9, 10), (4, 9, 10), (5, 9, 10), (6, 9, 10)] G=Graph(edges) G.weighted(True) G.graphplot(edge_labels=True,save_pos=True).show()

    Далі ми завантажуємо функцію kruskal і використовуємо її для створення списку ребер у дереві \(G\text<.>\)

    from sage.graphs.spanning_tree import kruskal E = kruskal(G, check=True);E

    Щоб побачити результуюче дерево з таким же вбудовуванням, як \(G\text\) ми генеруємо графік з країв остовного дерева. Далі встановлюємо позиції вершин такими ж, як на графі. Нарешті, наносимо ділянку дерева.

    T=Graph(E) T.set_pos(G.get_pos()) T.graphplot(edge_labels=True).show()

    Вправи

    Припустимо, що неспрямоване дерево має діаметр \(d\) і що ви хотіли б вибрати вершину дерева як корінь, щоб отримане вкорінене дерево мало найменшу можливу глибину. Як би був обраний такий корінь і якою буде глибина дерева (в перерахунку \(d\) )?

    Знайдіть будь-який простий шлях довжини \(d\) і знайдіть вершину в положенні \(\lceil d/2\rceil\) на контурі. Дерево, що вкорінюється в цій вершині, матиме глибину \(\lceil d/2\rceil\text\) якої мінімальна.

    Скористайтеся алгоритмом Kruskal, щоб знайти мінімальне остовне дерево для наступних графіків. Окрім остовного дерева, знайдіть остаточне вкорінене дерево в алгоритмі. Коли ви об’єднаєте два дерева в алгоритмі, зробіть корінь з нижнім номером коренем нового дерева.

    Малюнок \(\PageIndex\) Малюнок \(\PageIndex\)

    Припустимо, що інформація про будівлі розміщена в записах з п’ятьма полями: назва будівлі, його місце розташування, його власник, його висота і площа приміщення. Поля місцезнаходження та власника — це записи, які містять всю інформацію, яку ви очікуєте, наприклад, вулицю, місто та стан, а також ім’я власника (перше, середнє, останнє) у полі власника. Намалюйте вкорінене дерево для опису цього типу записів

    Відповідь Малюнок \(\PageIndex\)

    Пройдіть вручну алгоритм Kruskal, щоб переконатися, що приклад мінімального остовного дерева за допомогою Sage у підрозділі 10.3.3 є правильним.

    5.2: Дерева

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

    Якщо це нагадує вам алгоритм Prim, він повинен. Алгоритм Prim справив саме так: вільне дерево, що з’єднує всі вузли — і конкретно вільне дерево з найкоротшою загальною довжиною. Поверніться назад і подивіться на фінальну рамку малюнка 5.1.12 і переконайте себе, що затемнені краю утворюють вільне дерево.

    З цієї причини алгоритм часто називають алгоритмом мінімального остовного дерева Prim. «Остовне дерево» просто означає «вільне дерево, яке охоплює (з’єднує) всі вузли графа.»

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

    Вкорінені дерева

    Тепер вкорінене дерево – це те саме, що і вільне дерево, за винятком того, що ми піднімаємо один вузол, щоб стати коренем. Виявляється, це робить все різниця. Припустимо, що ми вибрали A в якості кореня Figure \(\PageIndex\) . Тоді ми б вкорінене дерево в лівій половині малюнка \(\PageIndex\) . Вершина А була розташована вгорі, а все інше тече під нею. Я думаю, що це як тягнутися до вільного дерева, ретельно схопивши вузол, а потім піднявши руку, щоб решта вільного дерева бовталася звідти. Якби ми вибрали (скажімо) C як корінь замість цього, у нас було б інше вкорінене дерево, зображене в правій половині фігури. Обидва цих вкорінених дерева мають всі ті ж ребра, що і вільне дерево: B з’єднаний як з A, так і C, F з’єднаний тільки з A і т.д. різниця лише в тому, який вузол позначається корінь.

    До сих пір ми говорили, що просторове позиціонування на графіках не має значення. Але це трохи змінюється з вкоріненими деревами. Вертикальне позиціонування – це наш єдиний спосіб показати, які вузли «вище» інших, і слово «вище» дійсно має значення тут: воно означає ближче до кореня. Висота вузла показує, скільки кроків він знаходиться від кореня. У правому вкоріненому дереві вузли B, D та E знаходяться на відстані одного кроку від кореня (C), тоді як вузол F знаходиться на відстані трьох кроків.

    Малюнок \(\PageIndex\) : Два різних вкорінених дерева з однаковими вершинами і ребрами.

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

    Дерева мають безліч застосувань. Подумайте про файли та папки на жорсткому диску: вгорі знаходиться корінь файлової системи (можливо, « / » на Linux/Mac або « C: \\» у Windows), а під ними знаходяться іменовані папки. Кожна папка може містити файли, а також інші іменовані папки, і так далі по ієрархії. Результатом є те, що кожен файл має один, і лише один, окремий шлях до нього з верхньої частини файлової системи. Файл може бути збережений, а пізніше витягнутий, точно одним способом.

    «Організаційна діаграма» така: генеральний директор знаходиться вгорі, потім під нею знаходяться віце-президент, директори, менеджери і, нарешті, рядові співробітники. Так і військова організація: Головнокомандувач керує генералами, які командують полковниками, хто командує майорами, хто командує капітанами, хто командує лейтенантами, хто командує сержантами, які командують рядовими.

    Людське тіло – це навіть вкорінене дерево: воно містить скелетну, серцево-судинну, травну та інші системи, кожна з яких складається з органів, потім тканин, потім клітин, молекул та атомів. Насправді, все, що має такого роду частково-цілу ієрархію стримування просто просять бути представленим у вигляді дерева.

    У комп’ютерному програмуванні додатків занадто багато, щоб назвати. Компілятори сканують код і будують «дерево розбору» його основного значення. HTML – це спосіб структурування простого тексту в деревоподібну ієрархію відображуваних елементів. Шахові програми AI будують дерева, що представляють їх можливі майбутні ходи та ймовірні відповіді суперника, щоб «побачити багато ходів вперед» та оцінити їх найкращі варіанти. Об’єктно-орієнтовані конструкції передбачають «ієрархії успадкування» класів, кожен з яких спеціалізується на конкретному іншому. І т. д. Крім простої послідовності (як масив), дерева, ймовірно, є найбільш поширеною структурою даних у всіх комп’ютерних наук.

    Термінологія вкорінених дерев

    Вкорінені дерева несуть з собою ряд термінів. Я буду використовувати дерево з лівого боку Figure \(\PageIndex\) як ілюстрацію кожного:

    Вузол у верхній частині дерева, який є A в нашому прикладі. Зверніть увагу, що на відміну від дерев в реальному світі, дерева інформатики мають свій корінь у верхній частині і ростуть вниз. Кожне дерево має корінь, крім порожнього дерева, яке є «деревом», яке взагалі не має вузлів. (Це свого роду дивне мислення про «нічого» як дерево, але це ніби як порожній набір \(\varnothing\) , який все ще набір.)

    Кожен вузол, крім кореня, має одного батька: вузла безпосередньо над ним. Батько D – C, батьком C є B, батьком F є A, а A не має батька.

    Деякі вузли мають дочірні, які представляють собою вузли, з’єднані безпосередньо під ним. Діти A – F і B, C – D і E, Єдина дитина B – C, а E не має дітей.

    рідний брат.

    Вузол з тим самим батьківським. Рідний брат Е – D, B – F, і жоден з інших вузлів не має братів і сестер.

    Ваш батько, бабуся і дідусь, прадідусь і т.д., весь шлях назад до кореня. Єдиним предком B є A, тоді як предки E – C, B та A. Зверніть увагу, що F не є предком C, хоча він знаходиться над ним на діаграмі: немає зв’язку від C до F, крім повернення через корінь (який не рахується).

    Ваші діти, онуки, правнуки і т.д., весь шлях йде. Нащадки B – C, D і E, тоді як A – F, B, C, D та E.

    Вузол без дітей. F, D і E – це листя. Зверніть увагу, що в (дуже) маленькому дереві корінь сам міг бути листом.

    внутрішній вузол.

    Будь-який вузол, який не є листом. A, B і C – внутрішні вузли в нашому прикладі.

    глибина (вузла).

    Глибина вузла – це відстань (у кількості вузлів) від нього до кореня. Сам корінь має глибину нуль. У нашому прикладі B має глибину 1, E – глибиною 3, а A – глибиною 0.

    висота (дерева).

    Висота вкоріненого дерева – це максимальна глибина будь-якого з його вузлів; тобто максимальна відстань від кореня до будь-якого вузла. Наш приклад має висоту 3, так як «найглибші» вузли – D і E, кожен з глибиною 3. Дерево з одним вузлом вважається, що має висоту 0. Химерно, але щоб бути послідовним, скажемо, що порожнє дерево має висоту -1! Дивно, але що ще може бути? Сказати, що він має висоту 0, здається, не відповідає дереву з одним вузлом, також має висоту 0. У будь-якому випадку, це не вийде багато.

    Всі вузли з однаковою глибиною розглядаються на одному «рівні». B і F знаходяться на рівні 1, а D і E – на рівні 3. Вузли на одному рівні не обов’язково є братами і сестрами. Якби F мав дитину на ім’я G на прикладі діаграми, то G і C були б на одному рівні (2), але не були б братами і сестрами, тому що вони мають різних батьків. (Ми можемо назвати їх «двоюрідними братами», щоб продовжити сімейну аналогію.)

    Нарешті, багато з того, що надає деревам свою виразну силу, – це їх рекурсивний характер. Це означає, що дерево складається з інших (менших) дерев. Розглянемо наш приклад. Це дерево з коренем А. Але двоє дітей А – це кожне дерево по-своєму! F сам по собі являє собою дерево тільки з одним вузлом. Б і його нащадки роблять ще одне дерево з чотирма вузлами. Ми вважаємо ці два дерева піддеревами оригінального дерева. Поняття «корінь» дещо зміщується, коли ми розглядаємо піддерева — A є корінням вихідного дерева, а B — корінь другого піддерева. Коли ми розглядаємо дітей Б, ми бачимо, що є ще одне піддерево, яке корениться в C і так далі. Легко помітити, що будь-яке піддерево виконує всі властивості дерев, і тому все, що ми говорили вище, відноситься і до нього.

    Бінарні дерева (BT)

    Вузли в вкоріненому дереві можуть мати будь-яку кількість дітей. Існує особливий тип вкоріненого дерева, хоча, називається двійкове дерево, яке ми обмежуємо, просто кажучи, що кожен вузол може мати не більше двох дітей. Крім того, ми позначимо кожного з цих двох дітей як «ліва дитина» і «права дитина». (Зауважте, що певний вузол може мати лише лівий дочірній або лише правий дочірній, але все одно важливо знати, в якому напрямку є ця дитина.)

    Ліва половина малюнка \(\PageIndex\) – бінарне дерево, а права – ні (C має трьох дітей). Більше двійкове дерево (висотою 4) показано на малюнку \(\PageIndex\) .

    Обхід бінарних дерев

    Існували два способи обходу графіка: ширина-перший і глибина-перший. Цікаво, що існує три способи обходу дерева: попереднє замовлення, післязамовлення та замовлення. Всі три починаються з кореня, а всі три розглядають кожен з дочірніх коренів як піддерева. Різниця полягає в порядку відвідування.

    Малюнок \(\PageIndex\) : Бінарне дерево.

    Щоб пройти попереднє замовлення дерева, ми:
    1. Відвідайте корінь.
    2. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    3. Те ж саме зробіть з потрібною дитиною.

    Це складно, тому що ви повинні пам’ятати, що кожен раз, коли ви «ставитеся до дитини як піддерево», ви робите весь процес обходу на цьому піддереві. Це передбачає запам’ятовування, де ви були, коли закінчите.

    Дотримуйтесь цього прикладу уважно. Для дерева на малюнку \(\PageIndex\) ми починаємо з відвідування Г. Потім ми обходимо ціле «K піддерево». Це передбачає відвідування самого K, а потім обхід всього лівого піддерева (закріпленого на D). Після того, як ми відвідаємо D вузол, ми виявимо, що він насправді не має лівого піддерева, так що ми йдемо вперед і пройти його праворуч піддерево. Це відвідування O, а потім I (оскільки O також не має лівого піддерева), який, нарешті, повертається назад вгору по сходах.

    Саме в цей момент легко загубитися. Ми закінчуємо відвідувати мене, а потім ми повинні запитати «добре, де, чорт возьми, ми були? Як ми сюди потрапили?» Відповідь полягає в тому, що ми щойно були на K вузлі, де ми пройшли його ліве (D) піддерево. Так що тепер, що настав час робити? Обхід правого піддерева, звичайно, який є М. Це передбачає відвідування M, C і E (в такому порядку) перед поверненням на саму вершину, G.

    Тепер ми знаходимося в тій же ситуації, де ми могли б заблукати раніше: ми провели багато часу в заплутаному безладі лівого піддерева G, і ми просто повинні пам’ятати, що зараз прийшов час, щоб зробити G правого піддерева. Дотримуйтесь цієї ж процедури, і весь порядок відвідування закінчується тим, що: G, K, D, O, I, M, C, E, H, A, B, F, N, L. (Див. Малюнок \(\PageIndex\) для візуального.)

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при попередньому обході.

    Щоб перетнути дерево після замовлення, ми:
    1. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    2. Те ж саме зробіть з потрібною дитиною.
    3. Відвідайте корінь.

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

    Для нашого зразка дерева, перший відвіданий вузол виявляється I. Це тому, що ми повинні відкласти відвідування G, поки ми не закінчимо його ліве (і праворуч) піддерево; потім ми відкладаємо K, поки ми не закінчимо його ліве (і праворуч) піддерево; відкласти D, поки ми не закінчимо з O піддерево, і відкласти O, поки ми не зробимо I. Річ починає розкручуватися. весь шлях назад до K. Але ми не можемо насправді відвідати K себе ще, тому що ми повинні зробити його правильне піддерево. Це призводить до C, E і M, в такому порядку. Тоді ми можемо зробити K, але ми все ще не можемо зробити G, тому що у нас є весь світ правого піддерева, щоб боротися з. Весь порядок закінчується: I, O, D, C, E, M, K, A, F, L, N, B, H і, нарешті, G. (Див. Рисунок \(\PageIndex\) для візуального.)

    Зверніть увагу, що це не віддалено зворотне відвідування попереднього замовлення, як ви могли очікувати. G останній замість першого, але решта все переплутано.

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при обході після замовлення.

    Нарешті, щоб обходити дерево в порядку, ми:
    1. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    2. Відвідайте корінь.
    3. Обходьте правильне піддерево в повному обсязі.

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

    Для дерева зразків першим відвіданим вузлом є D. Це тому, що це перший зустрінутий вузол, який не має лівого піддерева, що означає, що крок 1 не повинен нічого робити. За цим слідують О і Я, з тієї ж причини. Потім ми відвідуємо K перед його праворуч піддерево, який, в свою чергу, відвідує C, M, і E, в цьому порядку. Остаточний порядок: D, O, I, K, C, M, E, G, A, H, F, B, L, N (Див \(\PageIndex\) . Рис.)

    Якщо ваші вузли розташовані рівномірно, ви можете прочитати обхід по порядку від діаграми, переміщаючи очі зліва направо. Будьте обережні з цим, тому що в кінцевому підсумку просторове положення не має значення, а, скоріше, відносини між вузлами. Наприклад, якби я намалював вузол я далі вправо, для того, щоб зробити лінії між D – O – я менш крутим, що я вузол міг би бути висунутий фізично праворуч від K. Але це не змінило б порядок і K відвідав раніше.

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при обході в порядку.

    Нарешті, варто згадати, що всі ці методи обходу елегантно використовують рекурсію. Рекурсія – це спосіб прийняти велику проблему і розбити її на подібні, але менші, підпроблеми. Потім кожну з цих підпроблем можна атакувати так само, як ви атакували більшу проблему: розбиваючи їх на підзадачі. Все, що вам потрібно, це правило для того, щоб врешті-решт зупинити процес «розпаду», фактично роблячи щось.

    Кожен раз, коли один з цих процесів обходу розглядає лівий або правий дочірній як піддерево, вони «рекурсируються», повторно ініціюючи весь процес обходу на меншому дереві. Наприклад, попереднє замовлення обходу, після відвідування кореня, каже: «Гаразд, давайте зробимо вигляд, що ми почали всю цю обхідну річ з меншим деревом, вкоріненим у моєї лівої дитини. Як тільки це закінчиться, розбудити мене, щоб я міг так само почати його з моєю правильною дитиною». Рекурсія – дуже поширений і корисний спосіб вирішення певних складних завдань, а дерева рясніють можливостями.

    Розміри бінарних дерев

    Бінарні дерева можуть мати будь-яку рвану стару форму, як наш \(\PageIndex\) приклад з малюнком. Іноді, однак, ми хочемо поговорити про бінарних деревах з більш правильною формою, які задовольняють певним умовам. Зокрема, мова піде про три особливих видах:

    повне двійкове дерево.

    Повне двійкове дерево – це дерево, в якому кожен вузол (крім листя) має два дочірніх. Іншим чином, кожен вузол має або два дочірніх, або жоден: жодна строгість не допускається. Малюнок \(\PageIndex\) не повний, але було б, якби ми додали три порожні вузли на малюнку \(\PageIndex\) .

    Малюнок \(\PageIndex\) : Повне двійкове дерево.

    До речі, не завжди можливо мати повне двійкове дерево з певною кількістю вузлів. Наприклад, двійкове дерево з двома вузлами не може бути повним, оскільки воно неминуче матиме корінь лише з одним дочірнім.

    повне двійкове дерево.

    Повне двійкове дерево – це те, в якому кожен рівень має всі можливі вузли, за винятком, мабуть, найглибшого рівня, який заповнюється весь шлях зліва. Малюнок \(\PageIndex\) не повний, але було б, якби ми зафіксували її, як на малюнку \(\PageIndex\) .

    Малюнок \(\PageIndex\) : Повне двійкове дерево.

    На відміну від повних бінарних дерев, завжди можна мати повне двійкове дерево незалежно від того, скільки вузлів воно містить. Ви просто продовжуєте заповнювати зліва направо, рівень за рівнем.

    ідеальне двійкове дерево.

    Наш останній особливий тип має досить зухвалу назву, але «ідеальне» дерево – це просто те, що точно збалансовано: кожен рівень повністю заповнений. Малюнок не \(\PageIndex\) ідеальний, але було б, якби ми або додали вузли для заповнення рівня 4, або видалили незавершену частину рівня 3 (як на рис \(\PageIndex\) .)

    Малюнок \(\PageIndex\) : «Ідеальне» бінарне дерево.

    Ідеальні бінарні дерева, очевидно, мають найсуворіші обмеження розміру. Насправді можна мати ідеальні бінарні дерева з \(2^-1\) вузлами, якщо \(h\) це висота дерева. Таким чином, є ідеальні бінарні дерева з 1, 3, 7, 15, 31. вузлами, але жоден між ними. У кожному такому дереві \(2^h\) з вузлів (майже рівно половини) складають листя.

    Тепер, як ми побачимо, бінарні дерева можуть володіти деякими досить дивовижними повноваженнями, якщо вузли всередині них організовані певним чином. Зокрема, двійкове дерево пошуку та купа – це два спеціальні види бінарних дерев, які відповідають певним обмеженням. В обох випадках те, що робить їх такими потужними, – це швидкість, з якою дерево росте, коли до нього додаються вузли.

    Припустимо, у нас є ідеальне двійкове дерево. Щоб зробити його бетонним, припустимо, він має висоту 3, що дало б йому 1+2+4+8=15 вузлів, 8 з яких – листя. Тепер що станеться, якщо збільшити висоту цього дерева до 4? Якщо це все ще «ідеальне» дерево, ви додасте ще 16 вузлів (всі листя). Таким чином, ви подвоїли кількість листя, просто додавши ще один рівень. Це каскади, тим більше рівнів ви додаєте. Дерево висотою 5 раз подвоює кількість листя (до 32), а висота 6 подвоює його знову (до 64).

    Якщо це не здається вам дивовижним, це, мабуть, тому, що ви не повністю розумієте, наскільки швидко може накопичуватися такий експоненціальний ріст. Припустимо, у вас було ідеальне бінарне дерево висотою 30 – звичайно, не вражаюча фігура. Можна було б уявити, що він припадає на аркуш паперу. по висоті, тобто. Але запустіть цифри, і ви виявите, що таке дерево буде більше, ніж по одному для кожної людини в Сполучених Штатах. Збільште висоту дерева лише до 34 – всього 4 додаткових рівня – і раптом у вас є понад 8 мільярдів листя, що легко перевищує чисельність населення планети Земля.

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

    Причина, що це називається «експоненціальним» зростанням, полягає в тому, що кількість, яку ми змінюємо – висота – з’являється як показник кількості листя, тобто \(2^h\) . Кожен раз, коли ми додаємо лише один рівень, ми подвоюємо кількість листочків.

    Так що кількість листя ( \(l\) називайте його) \(2^h\) , якщо \(h\) це висота дерева. Перегортаючи це навколо, ми говоримо, що \(h = \lg(l)\) . Функція «lg» – це логарифм, зокрема логарифм з основою-2. Це те, що часто використовують комп’ютерні вчені, а не база з 10 (яка пишеться «лог») або база \(e\) (яка пишеться «ln»). Так як \(2^h\) росте дуже і дуже швидко, то з цього випливає , що \(\lg(l)\) росте дуже і дуже повільно. Після того, як наше дерево досягне декількох мільйонів вузлів, ми можемо додавати все більше і більше вузлів, не збільшуючи висоту дерева значно.

    Повідомлення про винос тут просто полягає в тому, що неймовірно велика кількість вузлів можна розмістити в дереві з дуже скромною висотою. Це дає можливість, серед іншого, шукати величезну кількість інформації дивно швидко. за умови, що вміст дерева впорядковано належним чином.

    Бінарні дерева (BT)

    Вузли в вкоріненому дереві можуть мати будь-яку кількість дітей. Існує особливий тип вкоріненого дерева, хоча, називається двійкове дерево, яке ми обмежуємо, просто кажучи, що кожен вузол може мати не більше двох дітей. Крім того, ми позначимо кожного з цих двох дітей як «ліва дитина» і «права дитина». (Зауважте, що певний вузол може мати лише лівий дочірній або лише правий дочірній, але все одно важливо знати, в якому напрямку є ця дитина.)

    Ліва половина малюнка \(\PageIndex\) – бінарне дерево, а права – ні (C має трьох дітей). Більше двійкове дерево (висотою 4) показано на малюнку \(\PageIndex\) .

    Обхід бінарних дерев

    Існували два способи обходу графіка: ширина-перший і глибина-перший. Цікаво, що існує три способи обходу дерева: попереднє замовлення, післязамовлення та замовлення. Всі три починаються з кореня, а всі три розглядають кожен з дочірніх коренів як піддерева. Різниця полягає в порядку відвідування.

    Малюнок \(\PageIndex\) : Бінарне дерево.

    Щоб пройти попереднє замовлення дерева, ми:
    1. Відвідайте корінь.
    2. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    3. Те ж саме зробіть з потрібною дитиною.

    Це складно, тому що ви повинні пам’ятати, що кожен раз, коли ви «ставитеся до дитини як піддерево», ви робите весь процес обходу на цьому піддереві. Це передбачає запам’ятовування, де ви були, коли закінчите.

    Дотримуйтесь цього прикладу уважно. Для дерева на малюнку \(\PageIndex\) ми починаємо з відвідування Г. Потім ми обходимо ціле «K піддерево». Це передбачає відвідування самого K, а потім обхід всього лівого піддерева (закріпленого на D). Після того, як ми відвідаємо D вузол, ми виявимо, що він насправді не має лівого піддерева, так що ми йдемо вперед і пройти його праворуч піддерево. Це відвідування O, а потім I (оскільки O також не має лівого піддерева), який, нарешті, повертається назад вгору по сходах.

    Саме в цей момент легко загубитися. Ми закінчуємо відвідувати мене, а потім ми повинні запитати «добре, де, чорт возьми, ми були? Як ми сюди потрапили?» Відповідь полягає в тому, що ми щойно були на K вузлі, де ми пройшли його ліве (D) піддерево. Так що тепер, що настав час робити? Обхід правого піддерева, звичайно, який є М. Це передбачає відвідування M, C і E (в такому порядку) перед поверненням на саму вершину, G.

    Тепер ми знаходимося в тій же ситуації, де ми могли б заблукати раніше: ми провели багато часу в заплутаному безладі лівого піддерева G, і ми просто повинні пам’ятати, що зараз прийшов час, щоб зробити G правого піддерева. Дотримуйтесь цієї ж процедури, і весь порядок відвідування закінчується тим, що: G, K, D, O, I, M, C, E, H, A, B, F, N, L. (Див. Малюнок \(\PageIndex\) для візуального.)

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при попередньому обході.

    Щоб перетворити дерево після замовлення, ми:
    1. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    2. Те ж саме зробіть з потрібною дитиною.
    3. Відвідайте корінь.

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

    Для нашого зразка дерева, перший відвіданий вузол виявляється I. Це тому, що ми повинні відкласти відвідування G, поки ми не закінчимо його ліве (і праворуч) піддерево; потім ми відкладаємо K, поки ми не закінчимо його ліве (і праворуч) піддерево; відкласти D, поки ми не закінчимо з O піддерево, і відкласти O, поки ми не зробимо I. Річ починає розкручуватися. весь шлях назад до K. Але ми не можемо насправді відвідати K себе ще, тому що ми повинні зробити його правильне піддерево. Це призводить до C, E і M, в такому порядку. Тоді ми можемо зробити K, але ми все ще не можемо зробити G, тому що у нас є весь світ правого піддерева, щоб боротися з. Весь порядок закінчується: I, O, D, C, E, M, K, A, F, L, N, B, H і, нарешті, G. (Див. Рисунок \(\PageIndex\) для візуального.)

    Зверніть увагу, що це не віддалено зворотне відвідування попереднього замовлення, як ви могли очікувати. G останній замість першого, але решта все переплутано.

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при обході після замовлення.

    Нарешті, щоб обходити дерево в порядку, ми:
    1. Ставтеся до лівого дитини і всіх його нащадків як до піддерева, і обходьте його в повному обсязі.
    2. Відвідайте корінь.
    3. Обходьте правильне піддерево в повному обсязі.

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

    Для дерева зразків першим відвіданим вузлом є D. Це тому, що це перший зустрінутий вузол, який не має лівого піддерева, що означає, що крок 1 не повинен нічого робити. За цим слідують О і Я, з тієї ж причини. Потім ми відвідуємо K перед його праворуч піддерево, який, в свою чергу, відвідує C, M, і E, в цьому порядку. Остаточний порядок: D, O, I, K, C, M, E, G, A, H, F, B, L, N (Див \(\PageIndex\) . Рис.)

    Якщо ваші вузли розташовані рівномірно, ви можете прочитати обхід по порядку від діаграми, переміщаючи очі зліва направо. Будьте обережні з цим, тому що в кінцевому підсумку просторове положення не має значення, а, скоріше, відносини між вузлами. Наприклад, якби я намалював вузол я далі вправо, для того, щоб зробити лінії між D – O – я менш крутим, що я вузол міг би бути висунутий фізично праворуч від K. Але це не змінило б порядок і K відвідав раніше.

    Малюнок \(\PageIndex\) : Порядок відвідування вузла при обході в порядку.

    Нарешті, варто згадати, що всі ці методи обходу елегантно використовують рекурсію. Рекурсія – це спосіб прийняти велику проблему і розбити її на подібні, але менші, підпроблеми. Потім кожну з цих підпроблем можна атакувати так само, як ви атакували більшу проблему: розбиваючи їх на підзадачі. Все, що вам потрібно, це правило для того, щоб врешті-решт зупинити процес «розпаду», фактично роблячи щось.

    Кожен раз, коли один з цих процесів обходу розглядає лівий або правий дочірній як піддерево, вони «рекурсируються», повторно ініціюючи весь процес обходу на меншому дереві. Наприклад, попереднє замовлення обходу, після відвідування кореня, каже: «Гаразд, давайте зробимо вигляд, що ми почали всю цю обхідну річ з меншим деревом, вкоріненим у моєї лівої дитини. Як тільки це закінчиться, розбудити мене, щоб я міг так само почати його з моєю правильною дитиною». Рекурсія – дуже поширений і корисний спосіб вирішення певних складних завдань, а дерева рясніють можливостями.

    Розміри бінарних дерев

    Бінарні дерева можуть мати будь-яку рвану стару форму, як наш \(\PageIndex\) приклад з малюнком. Іноді, однак, ми хочемо поговорити про бінарних деревах з більш правильною формою, які задовольняють певним умовам. Зокрема, мова піде про три особливих видах:

    повне двійкове дерево.

    Повне двійкове дерево – це дерево, в якому кожен вузол (крім листя) має два дочірніх. Іншим чином, кожен вузол має або два дочірніх, або жоден: жодна строгість не допускається. Малюнок \(\PageIndex\) не повний, але було б, якби ми додали три порожні вузли на малюнку \(\PageIndex\) .

    Малюнок \(\PageIndex\) : Повне двійкове дерево.

    До речі, не завжди можливо мати повне двійкове дерево з певною кількістю вузлів. Наприклад, двійкове дерево з двома вузлами не може бути повним, оскільки воно неминуче матиме корінь лише з одним дочірнім.

    повне двійкове дерево.

    Повне двійкове дерево – це те, в якому кожен рівень має всі можливі вузли, за винятком, мабуть, найглибшого рівня, який заповнюється весь шлях зліва. Малюнок \(\PageIndex\) не повний, але було б, якби ми зафіксували її, як на малюнку \(\PageIndex\) .

    Малюнок \(\PageIndex\) : Повне двійкове дерево.

    На відміну від повних бінарних дерев, завжди можна мати повне двійкове дерево незалежно від того, скільки вузлів воно містить. Ви просто продовжуєте заповнювати зліва направо, рівень за рівнем.

    ідеальне двійкове дерево.

    Наш останній особливий тип має досить зухвалу назву, але «ідеальне» дерево – це просто те, що точно збалансовано: кожен рівень повністю заповнений. Малюнок не \(\PageIndex\) ідеальний, але було б, якби ми або додали вузли для заповнення рівня 4, або видалили незавершену частину рівня 3 (як на рис \(\PageIndex\) .)

    Малюнок \(\PageIndex\) : «Ідеальне» бінарне дерево.

    Ідеальні бінарні дерева, очевидно, мають найсуворіші обмеження розміру. Насправді можна мати ідеальні бінарні дерева з \(2^-1\) вузлами, якщо \(h\) це висота дерева. Таким чином, є ідеальні бінарні дерева з 1, 3, 7, 15, 31. вузлами, але жоден між ними. У кожному такому дереві \(2^h\) з вузлів (майже рівно половини) складають листя.

    Тепер, як ми побачимо, бінарні дерева можуть володіти деякими досить дивовижними повноваженнями, якщо вузли всередині них організовані певним чином. Зокрема, двійкове дерево пошуку та купа – це два спеціальні види бінарних дерев, які відповідають певним обмеженням. В обох випадках те, що робить їх такими потужними, – це швидкість, з якою дерево росте, коли до нього додаються вузли.

    Припустимо, у нас є ідеальне двійкове дерево. Щоб зробити його бетонним, припустимо, він має висоту 3, що дало б йому 1+2+4+8=15 вузлів, 8 з яких – листя. Тепер що станеться, якщо збільшити висоту цього дерева до 4? Якщо це все ще «ідеальне» дерево, ви додасте ще 16 вузлів (всі листя). Таким чином, ви подвоїли кількість листя, просто додавши ще один рівень. Це каскади, тим більше рівнів ви додаєте. Дерево висотою 5 раз подвоює кількість листя (до 32), а висота 6 подвоює його знову (до 64).

    Якщо це не здається вам дивовижним, це, мабуть, тому, що ви не повністю розумієте, наскільки швидко може накопичуватися такий експоненціальний ріст. Припустимо, у вас було ідеальне бінарне дерево висотою 30 – звичайно, не вражаюча фігура. Можна було б уявити, що він припадає на аркуш паперу. по висоті, тобто. Але запустіть цифри, і ви виявите, що таке дерево буде більше, ніж по одному для кожної людини в Сполучених Штатах. Збільште висоту дерева лише до 34 – всього 4 додаткових рівня – і раптом у вас є понад 8 мільярдів листя, що легко перевищує чисельність населення планети Земля.

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

    Причина, що це називається «експоненціальним» зростанням, полягає в тому, що кількість, яку ми змінюємо – висота – з’являється як показник кількості листя, тобто \(2^h\) . Кожен раз, коли ми додаємо лише один рівень, ми подвоюємо кількість листочків.

    Так що кількість листя ( \(l\) називайте його) \(2^h\) , якщо \(h\) це висота дерева. Перегортаючи це навколо, ми говоримо, що \(h = \lg(l)\) . Функція «lg» – це логарифм, зокрема логарифм з основою-2. Це те, що часто використовують комп’ютерні вчені, а не база з 10 (яка пишеться «лог») або база \(e\) (яка пишеться «ln»). Так як \(2^h\) росте дуже і дуже швидко, то з цього випливає , що \(\lg(l)\) росте дуже і дуже повільно. Після того, як наше дерево досягне декількох мільйонів вузлів, ми можемо додавати все більше і більше вузлів, не збільшуючи висоту дерева значно.

    Повідомлення про винос тут просто полягає в тому, що неймовірно велика кількість вузлів можна розмістити в дереві з дуже скромною висотою. Це дає можливість, серед іншого, шукати величезну кількість інформації дивно швидко. за умови, що вміст дерева впорядковано належним чином.

    Бінарні дерева пошуку (BST)

    Гаразд, тоді давайте поговоримо про те, як організувати цей вміст. Двійкове дерево пошуку (BST) – це будь-яке двійкове дерево, яке задовольняє одній додатковій властивості: кожен вузол «більше» всіх вузлів у його лівому піддереві, і «менше (або дорівнює)» всіх вузлів у його правому піддереві. Ми будемо називати це властивістю BST. Фрази «більше, ніж» і «менше, ніж» знаходяться тут в лапках, тому що їх значення дещо гнучке, залежно від того, що ми зберігаємо в дереві. Якщо ми зберігаємо числа, ми будемо використовувати числовий порядок. Якщо ми зберігаємо імена, ми будемо використовувати в алфавітному порядку. Незалежно від того, що ми зберігаємо, нам просто потрібен спосіб порівняти два вузли, щоб визначити, який з них «йде перед» іншим.

    Приклад БСТ, що містить людей, наведено на рис \(\PageIndex\) . Уявіть, що кожен з цих вузлів містить велику кількість інформації про конкретну людину — запис співробітника, історію хвороби, інформацію про обліковий запис, що у вас є. Самі вузли індексуються по імені людини, а вузли організовані за правилом BST. Мітч приходить після Бен/Джессіки/Джима і перед Randi/Owen/Molly/Xander в алфавітному порядку, і це впорядкування відносин між батьками і дітьми повторюється весь шлях вниз по дереву. (Перевірте це!)

    Будьте обережні, щоб зауважити, що правило впорядкування застосовується між вузлом та усім вмістом його піддерев, а не лише до його безпосередніх дітей. Це помилка новачка, яку ви хочете уникнути. Ваш перший нахил, коли дивиться на малюнок \(\PageIndex\) , нижче, – це судити про це BST. Однак це не двійкове дерево пошуку! Джессіка знаходиться зліва від Мітча, як вона повинна бути, і Ненсі праворуч від Джессіки, як вона повинна бути. Здається, це перевірити. Але проблема полягає в тому, що Ненсі є нащадком лівого піддерева Мітча, тоді як вона повинна бути належним чином розміщена десь у його правому піддереві. І так, це має значення. Так що не забудьте перевірити ваш BST весь шлях вгору і вниз.

    Малюнок \(\PageIndex\) : Двійкове дерево пошуку. Малюнок \(\PageIndex\) : НЕ двійкове дерево пошуку, хоча воно виглядає як одне на перший погляд. (Примітка Ненсі і Мітч)

    Сила BST

    Гаразд, так що все гудіння про BST, у всякому разі? Ключовим розумінням є усвідомлення того, що якщо ви шукаєте вузол, все, що вам потрібно зробити, це почати з кореня і йти по висоті дерева вниз, роблячи одне порівняння на кожному рівні. Скажімо, ми шукаємо фігуру \(\PageIndex\) для Моллі. Дивлячись на Мітча (корінь), ми відразу знаємо, що Моллі повинна бути в правому піддереві, а не лівому, тому що вона йде після Мітча в алфавітному порядку. Отже, ми дивимося на Ренді. Цього разу ми виявляємо, що Моллі приходить перед Ренді, тому вона повинна бути десь у лівій гілці Ренді. Оуен знову відправляє нас вліво, в цей момент знаходимо Моллі.

    З деревом такого розміру це не здається таким дивовижним. Але припустимо, що його висота була 10. Це означало б близько 2000 вузлів у дереві – клієнти, користувачі, друзі, що завгодно. З BST, вам доведеться тільки вивчити десять з цих 2000 вузлів, щоб знайти все, що ви шукаєте, в той час як якщо вузли були просто в звичайному списку, вам доведеться порівняти проти 1000 або близько того з них, перш ніж ви наткнулися на той, який ви шукали. А в міру зростання розмірів дерева ця невідповідність зростає (набагато) більше. Якби ви хотіли знайти записи однієї людини в Нью-Йорку, ви б скоріше шукали 7 мільйонів імен, або 24 імена?? Тому що це різниця, на яку ти дивишся.

    Це здається майже занадто добре, щоб бути правдою. Як таке прискорення можливо? Хитрість полягає в тому, щоб зрозуміти, що з кожним вузлом, на який ви дивитеся, ви ефективно усуваєте половину решти дерева з розгляду. Наприклад, якщо ми шукаємо Моллі, ми можемо ігнорувати всю ліву половину Мітча, навіть не дивлячись на неї, а потім те саме для всієї правої половини Ренді. Якщо ви відкидаєте половину чогось, то половину половину, що залишилася, потім половину знову, це не займе у вас багато часу, перш ніж ви усунули майже кожен помилковий свинець.

    Існує формальний спосіб опису цього прискорення, який називається «позначення Big-O». Тонкощі трохи складні, але основна ідея така. Коли ми говоримо, що алгоритм «O (n)» (вимовляється «oh—of—n»), це означає, що час, необхідний для виконання алгоритму, пропорційний кількості вузлів. Це не означає будь-якої конкретної кількості мілісекунд або чогось іншого – це сильно залежить від типу комп’ютерного обладнання, яке ви маєте, мови програмування та безлічі інших речей. Але те, що ми можемо сказати про O (N) алгоритм є те, що якщо ви подвоїти кількість вузлів, ви збираєтеся приблизно подвоїти час роботи. Якщо ви вчетверо кількість вузлів, ви збираєтеся вчетверо час роботи. Це те, що ви очікуєте.

    Пошук «Моллі» у простому несортованому списку імен – це перспектива O (n). Якщо у списку є тисяча вузлів, в середньому ви знайдете Моллі після сканування через 500 з них. (Можливо, вам пощастить і знайти Моллі на початку, але тоді, звичайно, ви можете отримати дійсно не пощастило і не знайти її до кінця. Це в середньому приблизно до половини розміру списку в звичайному випадку.) Однак, якщо є мільйон вузлів, це займе у вас 500 000 обходів в середньому, перш ніж знайти Моллі. У десять разів більше вузлів означає в десять разів довше, щоб знайти Моллі, і в тисячу разів більше означає в тисячу разів довше. облом.

    Дивлячись на Моллі в BST, однак, це процес O (lg n). Нагадаємо, що «lg» означає логарифм (основа-2). Це означає, що подвоєння кількості вузлів дає вам незначне збільшення часу роботи. Припустимо, у вашому дереві була тисяча вузлів, як зазначено вище. Вам не доведеться переглядати 500, щоб знайти Моллі: вам доведеться лише переглянути десять (тому що \(\lg(1000) \approx 10\) ). Тепер збільште його до мільйона вузлів. Вам не доведеться переглядати 500 000, щоб знайти Моллі: вам доведеться лише переглянути двадцять. Припустимо, у вас в дереві було 6 мільярдів вузлів (приблизно населення землі). Вам не доведеться переглядати 3 мільярди вузлів: вам доведеться лише переглянути тридцять три. Абсолютно запаморочливий.

    Додавання вузлів до BST

    Знайти речі в BST блискавично. Виявляється, так само додається до нього речі. Припустимо, ми придбаємо нового клієнта на ім’я Дженніфер, і нам потрібно додати її до нашого BST, щоб ми могли отримати інформацію про її обліковий запис у майбутньому. Все, що ми робимо, це слідувати тому ж процесу, який ми б, якби шукали Дженніфер, але як тільки ми знайдемо місце, де вона буде, ми додаємо її туди. В цьому випадку Дженніфер приходить і перед Мітчем (йдемо наліво), і перед Джессікою (знову йдемо наліво), і після Бена (йдемо вправо). Бен не має права дитина, тому ми поклали Джессіку в дерево прямо в цей момент. (Див \(\PageIndex\) . Рис.)

    Цей процес додавання також є алгоритмом O (lg n), оскільки нам потрібно лише подивитися на невелику кількість вузлів, рівну висоті дерева.

    Малюнок \(\PageIndex\) : BST після додавання Дженніфер.

    Зверніть увагу, що новий запис завжди стає листом при додаванні. Насправді це дозволяє нам подивитися на дерево і реконструювати деякі з того, що було раніше. Наприклад, ми знаємо, що Мітч, мабуть, був першим вузлом, спочатку вставленим, і що Ренді був вставлений перед Оуеном, Ксандером або Моллі. Як вправа, додайте своє власне ім’я до цього дерева (і кілька імен ваших друзів), щоб переконатися, що ви зрозуміли його. Коли ви закінчите, дерево, звичайно, повинно підкорятися властивості BST.

    Видалення вузлів з BST

    Видалення вузлів трохи складніше, ніж їх додавання. Як видалити запис, не зіпсуючи структуру дерева? Легко побачити, як видалити Моллі: так як вона всього лише листочок, просто видаліть її і покінчіть з цим. Але як видалити Джесіку? Або з цього приводу, Мітч?

    Ваша перша схильність може полягати в тому, щоб усунути вузол і сприяти одному з його дітей піднятися на його місце. Наприклад, якщо ми видаляємо Джессіку, ми могли б просто підняти Бен до того, де Джессіка була, а потім перемістити Дженніфер під Бен, а також. Однак це не працює. Результат виглядав би як Фігура \(\PageIndex\) , з Дженніфер в неправильному місці. Наступного разу, коли ми шукаємо Дженніфер в дереві, будемо шукати праворуч Бена (як треба), повністю пропустивши її. Дженніфер фактично була втрачена.

    Одним з правильних способів (є й інші) видалення вузла є заміна вузла крайнім лівим нащадком правого піддерева. (Або, еквівалентно, крайній правий нащадок лівого піддерева). \(\PageIndex\) На малюнку показаний результат після видалення Джесіки. Ми замінили її Джимом, не тому, що це нормально, щоб сліпо просувати потрібну дитину, а тому, що у Джима не було лівих нащадків. Якби він мав, просування його було б так само неправильно, як просування Бена. Натомість ми б сприяли лівому нащадку Джима.

    Малюнок \(\PageIndex\) : Неправильний потенційний BST після видалення Джесіки неправильно. Малюнок \(\PageIndex\) : BST після видалення Джесіки правильно.

    Як ще один приклад, давайте перейдемо цільнокровиком і видалимо кореневий вузол, Мітч. Результат такий, як показано на малюнку \(\PageIndex\) . Це ганчірка до багатства для Моллі: вона отримала підвищення з листа аж до вершини. Чому саме Моллі? Тому що вона була лівим нащадком правого піддерева Мітча.

    Щоб зрозуміти, чому це працює, просто врахуйте, що Моллі була відразу після Мітча в алфавітному порядку. Те, що він був царем, а вона селянином, вводив в оману. Два з них були насправді дуже близькі: послідовні, по суті, з обходом в порядку. Таким чином, заміна Мітча на Моллі дозволяє уникнути перетасування будь-кого з алфавітного порядку, і зберігає найважливішу властивість BST.

    Малюнок \(\PageIndex\) : BST після видалення Мітча.

    Врівноваженість

    Нарешті, нагадайте, що цей дивовижно швидкий пошук критично залежить від того, що дерево «кущисте». В іншому випадку наближення, яке \(h=\lg(l)\) руйнується. Як смішно екстремальний приклад, розглянемо Рисунок \(\PageIndex\) , який містить ті самі вузли, які ми використовували. Це законне двійкове дерево пошуку! (Перевірте це!) Тим не менш, пошук вузла в цьому жахливості, очевидно, не буде швидше, ніж шукати його в простому старому списку. Ми повертаємося до продуктивності O (n).

    Малюнок \(\PageIndex\) : Неймовірно поганий, але все ще технічно законний, BST.

    На практиці існує три способи боротьби з цим. Один з підходів полягає в тому, щоб просто не турбуватися про це. Зрештою, до тих пір, поки ми вставляємо та видаляємо вузли випадковим чином, без помітного малюнка, шанси отримати дерево настільки однобоке, як Рисунок \(\PageIndex\) , астрономічно малі. Це так само ймовірно, як кидати колоду карт у повітрі і приземлитися все в акуратному стеку. Закон ентропії говорить нам, що ми отримаємо суміш коротких гілок і довгих гілок, і що на великому дереві неврівноваженість буде мінімальною.

    Другий підхід полягає в тому, щоб періодично перебалансувати дерево. Якщо наш веб-сайт виходить в автономному режимі для обслуговування кожен раз у той час, ми могли б відновити наше дерево з нуля, вставивши вузли в свіже дерево у вигідному порядку. В якому порядку ми повинні їх вставляти? Ну і пам’ятайте, що який би вузол не був вставлений першим, буде корінь. Це говорить про те, що ми хотіли б вставити середній вузол спочатку в наше дерево, так що Моллі стає новим коренем. Це залишає половину вузлів для її лівого піддерева і половину для її правого. Якщо ви будете слідувати цьому процесу логічно (і рекурсивно) ви зрозумієте, що ми б далі хочемо вставити середні вузли кожної половини. Це прирівнювалося б до Дженніфер і Ренді (в будь-якому порядку). Я думаю про це як маркування на лінійці: спочатку ви вставляєте півдюйма, потім \(\frac\) і \(\frac\) дюйми, потім \(\frac\) , \(\frac\) , \(\frac\) , і \(\frac\) дюйми і т.д. це відновлює нам відмінно збалансоване дерево через рівні проміжки часу, роблячи будь-які великі дисбаланси ще більш невірогідними (і короткочасними).

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

    1. Здається, немає єдиної думки щодо того, яке з цих понять є найбільш основним. Деякі автори називають вільне дерево просто як «дерево» – ніби це був «нормальний» вид дерева – і використовують термін вкорінене дерево для іншого виду. Інші автори роблять навпаки. Щоб уникнути плутанини, я намагатимуся завжди використовувати повний термін (хоча я визнаю, що я той, хто вважає вкорінені дерева більш важливою концепцією за замовчуванням).
Українцям