Дерева, червоно-чорні дерева

— Привіт, Аміго!

— Здорово, Ріша!

— Знайшов тут свої старі записи і приготував тобі трохи цікавого матеріалу. Думаю, тобі цікаво буде послухати.

— Давай. Ти завжди знаходиш щось цікаве, яке потім стає дуже корисним.

— Гаразд. Сьогодні я хочу тобі розповісти про дерева, тому почну я з графів.

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

Граф дуже зручно використовувати як математичну модель для різних реальних процесів та завдань. Для графів придумано дуже багато різних завдань та алгоритмів, тому їх досить часто використовують.

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

Але не завжди шлях з А до Б, займає стільки ж, як і шлях з Б до А. Тому іноді бажано мати дві різні лінії. Для цього лінії (ребра графа) замінюють на стрілки. Тобто. граф може містити дві стрілки: одну з А до Б, а другу з Б до А.

Якщо у графі використовуються стрілки, його називають орієнтованим графом, якщо просто лінії – неорієнтованим графом.

У кожної вершини може бути своя кількість ребер. Також вершина може мати ребер взагалі. Або навпаки, бути з'єднана ребрами з усіма іншими вершинами. Якщо у графі кожна вершина з'єднана ребром з кожної – такий граф називають повним.

Якщо в графі по ребрах можна дістатися до будь-якої вершини, такий граф називають зв'язним. Граф, що складається з трьох окремих вершин, без ребер взагалі, це все одно граф, але незв'язний.

Щоб з'єднати у зв'язковий граф N вершин, треба мінімум N-1 ребер. Такий граф називається деревом.

При цьому зазвичай одну вершину обирають коренем дерева, а решта оголошують її гілками. Гілки дерева, які не мають своїх гілок, називають листом листа. Приклад:

Дерево називають бінарним, якщо кожен елемент дерева має не більше двох нащадків. Тобто. їх може бути 0, 1 або 2. Вище праворуч зображено бінарне дерево.

Дерево називають повним бінарним деревом, коли у кожної гілки 2 нащадки, а все листя (без нащадків) знаходиться в одному ряду.

Приклад:

— А навіщо такі дерева потрібні?

— О, дерева застосовуються багато де. Бінарні дерева пошуку взагалі є відсортованою структурою даних.

— Це як?

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

— А можна докладніше.

— Сортування елементів дерева зазвичай додається. Ось, скажімо, у нас є 7 елементів: 13, 5, 4, 16, 8, 11, 10

Ось як додаються елементи до такого дерева.

Якщо ми шукаємо, наприклад, число 7 у такому дереві, пошук буде проходити так:

0) Починаємо з кореня.

1а) Число 7 дорівнює 13? Ні

1б) Число 7 більше 13? Ні, тоді йдемо до лівого піддерева.

2а) Чисто 7 дорівнює 5? Ні.

2б) Число 7 більше 5? Так, тоді йдемо у праве піддерево.

3а) Число 7 дорівнює 8? Ні

3б) Число 7 більше 8? Ні, тоді йдемо до лівого піддерева.

4а) Лівого піддерева немає, отже, числа 7 у дереві немає.

— Ага. Тобто. нам треба перевіряти лише вершини на шляху від кореня до гаданого місця потрібного числа. Так, це дійсно швидко.

— Ще б пак, якщо дерево збалансоване, то для мільйона елементів знадобиться обхід всього близько 20 вершин.

— Так, згоден, що це небагато.

А що означає – збалансоване дерево?

— Дерево без "перекосів" — без довгих гілок. Адже якщо ми подавали елементи при будівництві дерева в вже відсортованому порядку, у нас би вийшло довге-довжелезне дерево, що складається з однієї гілки.

— Гм. Справді. І як бути тоді?

— Як ти вже, напевно, здогадався, найефективнішим буде дерево, що має гілки приблизно рівної довжини. Тоді при кожному порівнянні відкидається найбільша частина піддерева з решти.

— Тобто. потрібно переробити дерево?

— Ага. Його потрібно "збалансувати" — зробити максимально схожим на повне бінарне дерево.

Для вирішення цієї проблеми були придумані дерева, що самобалансуються. Коли після додавання елемента в дереві виникає перекіс, воно трохи змінює порядок елементів, і все стає ок. Приклад балансування:

Однією з таких дерев є так звані «червоно-чорні дерева».

— А чому їх називають червоно-чорними?

— Їхній творець придумав фарбувати всі вершини у два кольори. Один колір – червоний, другий – чорний. І різні вершини підкоряються різним правилам. На цьому і будується все балансування.

Приклад:

— А що це за принципи?

— 1) Червона вершина не може бути сином червоної вершини.

2) Чорна глибина будь-якого аркуша однакова (чорною глибиною називають кількість чорних вершин на шляху з кореня).

3) Корінь дерева чорний.

Я не розповідатиму тобі, як це працює, у тебе вже мабуть голова кипить.

— Ага. Процесор гріється і не так слабко.

Ось тобі посилання, якщо захочеш – почитаєш тут докладніше.

Посилання на додатковий матеріал

А тепер – йди відпочивай.