[Powered by Google Translate] Як би ви представляєте всіх членів вашої родини в комп'ютері? Ми могли б просто використовувати список, але є чітка ієрархія тут. 

Скажімо, ми починаємо з вашої прабабусі, Alice. Вона має 2 синів, Боба і ваші дідусі, Чарлі. Чарлі має 3 дітей, Ваш дядько, Дейв, твоя тітка, Єва, і ваш батько, Фред. Ви єдина дитина в сім'ї Фреда. 

Чому організацію членів вашої родини, таким чином, бути краще, ніж просте уявлення списку? Однією з причин є те, що ця ієрархічна структура, називають «деревом», містить більше інформації, ніж простий список. Ми знаємо, що сімейні відносини між усіма тільки шляхом вивчення дерева. Крім того, це може прискорити довідкової час надзвичайно, якщо дерево сортування даних. 

Ми не можемо скористатися тим, що тут, але ми бачимо приклад цьому найближчим часом. Кожна людина являє собою вузол на дереві. Вузли можуть мати дочірні вузли а також батьківського вузла. Ці технічні терміни, навіть при використанні дерев для речей, крім сім'ї. Вузлу Аліси має 2 дітей, і немає батьків, в той час як вузол Чарлі має 3 дітей та 1 батько. 

Листовим вузлом є той, який не має дітей по зовнішньому краю дерева. Самий верхній вузол дерева, кореневий вузол, не має батька. 

Бінарне дерево є специфічний тип дерева, , В якій кожен вузол має, найбільше, 2 дітей. Ось структура вузла в бінарному дереві в C. Кожен вузол має деякі пов'язані з ним дані і 2 покажчики на інші вузли. 

У наш генеалогічне дерево, пов'язані з ним дані звали кожної людини. Ось вона Int, хоча це може бути що завгодно. Як з'ясувалося, бінарне дерево не було б хороше уявлення для сім'ї, так як люди часто мають більше 2 дітей. 

Бінарне дерево пошуку це особливий, впорядкований тип бінарного дерева , Що дозволяє нам дивитися на значеннях швидко. Ви, можливо, помітили, що кожен вузол під корінь дерева корінь іншого дерева, званого "піддерево". Тут, корінь дерева 6, і її дитини, 2, є коренем піддерева. 

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

Ось як це буде виглядати, якщо ми повернули всіх вузлів в структурах C. Зверніть увагу, що якщо дитина відсутня, покажчик є нульовим. Як ми перевіряємо, якщо 7 в дереві? Ми починаємо в корені. Сім більше 6, так що якщо це в дерево, воно повинно бути з правого боку. Тоді, це менше, ніж 8, тому він повинен бути зліва. Тут ми знайшли 7. Зараз ми перевіримо на 5. П'ять менше, ніж 6, тому він повинен бути зліва. П'ять більше 2, тому він повинен бути правильним, і це також більше 4, тому він повинен бути ще раз направо. Тим не менше, немає жодної дитини тут. Покажчик є нульовим. Це означає, що 5 не в наших дерев. 

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

Пам'ятайте, що 5 не був в дерево. Як ми можемо вставити його? Цей процес схожий на пошук. Ми ітерацію по дереву, починаючи з 6, зліва 2, Право 4, і ще раз направо, а 4 не має дитиною на цій стороні. Це буде нова посада на 5, і він почне без дітей. 

Як швидко операцій на бінарному дереві пошуку? Пам'ятайте, що Bigohnotation прагне забезпечити верхньої межі. У гіршому випадку, наше дерево може бути просто зв'язаний список Це означає, що вставки, видалення та пошуку може зайняти час, пропорційне числу вузлів у дереві. Це O (N). 

Наприклад, наступне є дійсним бінарне дерево пошуку. Однак, якщо ми намагаємося знайти 9, ми повинні пройти кожному вузлі. Це не краще, ніж зв'язаний список. В ідеалі, ми хотіли б, кожен вузол наші бінарне дерево пошуку, щоб мати 2 дітей. Таким чином, вставка, видалення і пошук б, на худий кінець, O (журнал N) часу. Дерево, перш ніж могла б бути більш збалансованою, як це. Тепер, дивлячись будь-яке значення має, найбільше, 3 кроки. Це дерево є збалансованим, значення, яке має мінімальну глибину в порівнянні з числом вузлів. 

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

Мене звати Bannus Ван-дер-Kloot. Це CS50.