Структура, види і використання бінарних дерев у комп’ютерних науках, оцінювання їхньої складності та стислий опис.
Дерево
Дерево - це нелінійна структура даних, яка зберігає дані в ієрархічнимо вигляді. Дані розкладені по окремим блокам, нодам, які з’єднані гранями. Кожна нода може мати певне значення в собі і також дочірню ноду.
Термін нода і грань пішли з теорії графів. Дерево це завжди зв’язний, ациклічний граф.
Листя - це останні ноди на дереві, у них немає дочірніх нод.
Є ще дві характеристики для дерев: висота і глибина.
Висота дерева це найбільша довжина від кореня до листя.
Глибина ноди це довжина шляху від ноди до кореня.
Дерева завдяки своїй ієрархії є дуже зручними структурами для маніпуляції даними, їх використовують в базах даних, для реалізації інших структур даних, в процесорах, в лексичному аналізі і в криптографії.
Яка різниця між графом і деревом?
Дерево і є графом, тільки в дереві в однієї ноди може бути тільки одна батьківська нода (крім кореня). В дереві не може бути цилків. Ці параметри і роблять дерево ієрархічною структурою.
Число Стралера
Число Стралера це число, яке вкиористовується для харакетристики розгалуженості системи.
Кожній ноді дерева дається певне значення, яке характеризує подальшу розгалуженість, алгоритм працює наступим чином:
Якщо в ноди немає дітей, то число рівне 1
Якщо в ноди є діти і їхні числа Стралера однакові, то число Стралера батьківської ноди буде максимальне число з дочірніх нод + 1.
Якщо в ноди є діти і їхні числа Стралера не однакові, то число Стралера батьківської ноди буде просто максимальним числом з дочірніх нод.
Є і інші методики для харакетризації розгалуженості системи.
O(log n)
Бінарні дерева, зазвичай, мають складність O(log n) через свою структуру. Основна причина полягає в тому, що кожен вузол має не більше двох дітей. Під час пошуку, вставки або видалення вузла в бінарному дереві, кожен крок зменшує кількість можливих вузлів для перевірки або обробки на певну частину.
Деякі бінарні дерева мають простішу складність для деяких операцій. Крім того, є деградоване бінарне дерево, складність якого O(n).
Rooted tree
Дерева, які мають спеціальний вертекс, який називають коренем, є Rooted Tree, дерева без кореня - Unrooted Tree.
Binary Tree
Бінарне дерево є деревом в якому кожна нода може мати не більше двох дочірніх нод. Зазвичай називають ліва і права нода/дитина.
Бінарне дерево завжди прагне підтримувати баланс між глибиною дерева та кількістю ключів у кожному вузлі. Це означає, що незалежно від обсягу даних, кількість кроків для пошуку буде логарифмічною відносно кількості записів у дереві, тобто O(log n), це причина по якій бінарні дерева виокристовуються для зберігання даних в реляційних БД.
В найгіршому випадку бінарне дерево дає O(n) для вставки і читання.
В найпростіших реалізаціях бінарних дерев вставка або видалення можуть призводити до зміни балансу дерева, що може призвести до неоптимальної структури, такої як дуже вузьке або глибоке дерево. Це може знизити ефективність операцій пошуку та інших операцій.
Full Binary Tree
Повні бінарне дерево - це дерево, внутрішні вузли якого (Вузли які мають нащадків), завжди мають тільки два нащадки.
Complete Binary Tree
Завершене бінарне дерево - це дерево рівні якьго, окрім, можливо, останнього рівня, мають максимальну кількість можливих вузлів, і всі вузли останнього рівня відображаються якомога лівіше.
Крайню ліву частину листкової ноди потрібно заповнювати першою. Не обов’язково, щоб остання кінцева нода мала правого брата.
Як відрізняти?
Нода C має лише одну дочірню ноду, що не робить дерево повним.
Нода C також має праву дитину, без лівої дитини, що не робить дерево завершеним.
Degrated binary tree
Деградоване бінарне дерево - це дерево у якому всі вузли розташовані в одному напрямку, що робить його зв’язаним списком (linked list). Основна властивість деградованого бінарного дерева, що воно втрачає властивість O(log n) деградуючи до O(n).
Binary Search Trees (BST)
Бінарне дерево пошуку (BST) є видом бінарного дерева, в якому кожен вузол має ключ, і всі ключі в лівому піддереві менші, ніж ключі поточного вузла, а всі ключі в правому піддереві більші.
Це структура даних, яка дозволяє швидко знаходити, вставляти і видаляти значення відсортованих даних: O (log n) / O(n).
Optimal BST
Оптимальне бінарне дерево пошуку - це таке бінарне дерево, яке мінімізує середню кількість порівнянь, необхідних для пошуку певного ключа у дереві. Це дерево поміщає ключі з більшою ймовірністю пошуку ближче до кореня дерева, тоді як ключі з нижчою ймовірністю пошуку дальше від дерева.
AVL Trees
Adelson-Velsky and Landis дерево - це спеціальний вид дерева, який автоматично регулюється/балансується, щоб всі гілки були приблизно однакового розміру. Коли ви додаєте або видаляєте елементи з AVL-дерева, воно самостійно коригується, щоб уникнути дисбалансу і забезпечити ефективну роботу. Це дозволяє виконувати швидкі операції пошуку, вставки та видалення даних, навіть коли дерево містить велику кількість елементів.
Балансування дерева - це процес коригування його форми, щоб всі гілки/грані були приблизно однакової довжини. Щоб дерево ефективно працювало, необхідно підтримували гілки однакової довжини. Це зробить пошук, вставку видалення вузлів швидше.
Функія | Середній випадок | Найгірший |
|---|---|---|
Пошук | O(log n) | O(log n) |
Вставка | O(log n) | O(log n) |
Видалення | O(log n) | O(log n) |
Red-black Tree
Червоно-чорне дерево - це одна з реалізацій самобалансуючих дерев, окрім того, що кожна нода має певне значенння, вона ще й має певний колір (червоний, або чорний), що дозволяє спростити складність деяких маніпуляцій в дереві.
Корінь дерева завжди чорний
Усі листки також чорні
Кожен червоний вузол має два чорний дочірніз вущли
Усі прості шляхи з кореня до листкових вузлів мають однакову кількість чорних вущліх, ця кількість вузлів називається чорною висотою.
Кольори роблять систему більш структурованою.
Функія | Середній випадок | Найгірший |
|---|---|---|
Пошук | O(log n) | O(log n) |
Вставка | O(1) | O(log n) |
Видалення | O(1) | O(log n) |
Дерева AVL більш збалансовані порівняно з ЧЧ деревами, але вони можуть викликати більше обератнь під час вставки та видалення (це вимагає алгоритм балансування). Тому, якщо ви часто вставляєте та видаляєте, то слід віддати перевагу ЧЧ деревам. А якщо ви частіше шукаєте, то дерева крще використовувати AVL дерева.
ЧЧ дерева використовуються для імплеменації TreeSet і TreeMap в Java, які дозволяють зберігати дані у відсортованому порядку, порівнючи дані через Comparator.
AA Tree
Дерево Арне Андерсона - це варіація ЧЧ дерева, яке спрощує обертання використовуючи один тип обертань skew та додаткову операцію split.
Щоб дерево було AA мають виконуватись необхідні умови:
Всі листки дерева є чорними вузлами (як у червоно-чорних деревах).
Кожен вузол має рівень, який використовується для балансування.
Рівень кожного лівого сина завжди не менший, ніж рівень його батька.
Рівень правого сина завжди менший, ніж рівень його батька.
Splay Tree
Сплей дерево - це ти самобалансуючого BST в якому операція доступу до вузла виконується через операцію сплей, яка підіймає цільвоий вузол до кореня дерева. Це дерево може бути корисним, якщо ви часто працюєте з групою певних нод.
Основним недоліком сплей дерев є те, що вони не гарантують збалансовану структуру дерева, що може призвести до деградації складності до O(n).
Функія | Середній випадок | Найгірший |
|---|---|---|
Пошук | O(log n) | O(n) |
Вставка | O(log n) | O(n) |
Видалення | O(log n) | O(n) |
Non BST
Huffman Tree
Дерево Хафмана - це особливий тип бінарного дерева, що використовується у схемах алгоритмів стиснення даних. Це дерево дозволяє створити оптимальний префіксний код для подання символів залежно від їхньої частоти входження у вихідний текст.
Rope / Cord
Rope - це окрема структура даних, яка працює як бінарне дерево і складається з маленьких стрічок, який використовуються для того, щоб збетігати і маніпулювати великими стрічками.
Так як це дерево реалізує стрічку, то і операції по типу concat, substring etc підтримує.
Heap Tree
Хіп дерево (Дерево купи) - це спеціальна структура дерева, яка використовується для імплементації пріоритетної черги (priority queue).
В Java priority queue імплементована саме через Heap Tree.
Хіп дерево може бути, або максимальним, або мінімальним.
Для мінімального має задовільнятись умова: Для кожної ноди значення її дочірніх вузлів менше або дорівнює її власному значенню.
Для маскимального умова обернена.
Є багато інших реалізай Хіп структури: 2–3 heap, B-heap, Fibonacci heap.
Обхід / Traversal
Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root.
Алгоритми обходу це алгоритми ціль яких обійти дерево, зібрати з нього інформацію, скопіювати його, або вписати дані в ноди. Є декілька визначених для цього алгоритмів.
Два найпопулярніші алгоритми обоходу: BFS і DFS.
Depth-first Search (пошук у глибину):
Основна ідея DFS полягає у тому, що він "занурюється" глибоко наскільки можливо в граф перед тим, як повернутися і відвідати інші гілки.
Початок з кореня: Починаємо обхід з кореневої ноди.
Відвідання нода: Першим кроком в обході є відвідання пооточної ноди.
Рекурсивний виклик для лівого піддерева: Потім рекурсивно викликаємо DFS для лівого піддерева поточної ноди (якщо воно існує).
Рекурсивний виклик для правого піддерева: Після завершення обходу лівого піддерева, рекурсивно викликаємо DFS для правого піддерева поточної ноди (якщо воно існує).
Повернення назад (рекурсивний зворотний хід): Після обходу обох піддерев, алгоритм повертається на рівень вище, де знаходиться батьківська нода, і продовжує обхід інших гілок.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def dfs(node):
if node is None:
return
print(node.value) # Відвідуємо поточний нод
dfs(node.left) # Рекурсивний виклик для лівого піддерева
dfs(node.right) # Рекурсивний виклик для правого піддерева
# Приклад бінарного дерева
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Depth-First Traversal:")
dfs(root)
node_c.children = [node_f]
# Викликаємо обхід у глибину
print("Depth-first order:")
depth_first_order(root)Breadth-first Search (пошук у ширину):
Початок з кореня: Починаємо обхід з кореня.
Відвідування нод: Починаючи з кореневої ноди відвідуємо всі ноди на поточному рівні перед тим, як перейти до нод на наступному рівні.
Пошук сусідів: Для кожної відвіданої ноли перевіряємо її дочірні ноди (ліву та праву, якщо вони існують).
Додавання до черги: Дочірні ноди додаються в чергу для подальшого обходу.
Перехід до наступного рівня: Після відвідування всіх нод на поточному рівні, переходимо до наступного рівня дерева.
Повторення процесу: Повторюємо процес до тих пір, поки всі ноди бінарного дерева не будуть відвідані.
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def bfs(root):
if root is None:
return
queue = deque()
queue.append(root)
while queue:
node = queue.popleft()
print(node.value) # Відвідуємо поточний нод
if node.left:
queue.append(node.left) # Додаємо лівого дочірнього нода до черги
if node.right:
queue.append(node.right) # Додаємо правого дочірнього нода до черги
# Приклад бінарного дерева
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Breadth-First Traversal:")
bfs(root)
BFS вимагає більше пам’яті, бо йому треба підтримувати чергу, але він гарантує знаходження найкоротшого шляху між двома вершинами, якщо такий шлях існує.
Черга дозволяє нам виконувати обхід вершин по рівнях. Починаючи з кореневого вузла, ми спочатку відвідуємо всі вершини на поточному рівні перед тим, як перейти до наступного рівня. Це важливо для збереження порядку обходу вершин у ширину.
Pre-order
Цей підхід зручний для побудови виразів префіксного запису, глибокого копіювання дерева або виконання певних операцій, які потребують спочатку обробки батьківських нод перед дочірніми.
Починаємо з кореня.
Потім рекурсивно переходимо до лівого піддерева.
Потім рекурсивно переходимо до правого піддерева.
Кожна нода відвідується до того, як відвідається будь-яка з її дочірніх вузлів.
In-order
Цей метод часто використовується для обходу впорядкованих дерев, пошуку, а також для відображення даних, впорядкованих за ключем.
Рекурсивно переходимо до лівого піддерева.
Відвідуємо поточну ноду.
Рекурсивно переходимо до правого піддерева.
Вузли відвідуються в порядку зростання значень у відповідності до упорядкування дерева.
Post-order
Цей метод допомагає у формуванні постфіксних виразів, обробці вузлів, які потребують обробки дочірніх вузлів перед батьківськими.
Рекурсивно переходимо до лівого піддерева.
Рекурсивно переходимо до правого піддерева.
Відвідуємо поточний вузол.
Кожен вузол відвідується після того, як оброблені всі його дочірні вузли.
Інші бінарні дерева
Я розглянув загально відомі бінарні дерева і методи взаємодії з ними, але ця тема набагато ширша, щоб повноцінно її охопити одним постом, ось інші дерева з якими ви можете познайомитись:
BSP Tree
Random binary Tree
Unrooted binary Tree
Scapegoat Tree
T Tree
