На шестой неделе курса информатики мы изучим деревья — фундаментальную структуру данных, используемую в базах данных, файловых системах, алгоритмах поиска и сортировки. Мы познакомимся с бинарными деревьями, обходами, операциями вставки и поиска, а также с понятием сбалансированности.
Дерево — это структура, в которой каждый элемент (узел) может иметь потомков. У дерева есть корень (root), листья (leaf) и внутренние узлы. Важно, что между узлами нет циклов.
Бинарное дерево — это дерево, где каждый узел имеет не более двух потомков: левый и правый.
```python```
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
- **In-order** (лево-корень-право)
- **Pre-order** (корень-лево-право)
- **Post-order** (лево-право-корень)
```python```
def inorder(node):
if node:
inorder(node.left)
print(node.value)
inorder(node.right)
Добавление по принципу бинарного дерева поиска (BST):
```python```
def insert(root, value):
if not root:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Рекурсивный поиск значения:
```python```
def search(root, target):
if not root:
return False
if root.value == target:
return True
if target < root.value:
return search(root.left, target)
return search(root.right, target)
Если дерево перекошено в одну сторону, эффективность операций падает с O(log n) до O(n).
Существуют структуры:
- AVL-деревья;
- Красно-чёрные деревья;
- B-деревья (для баз данных).
Мы не реализуем их вручную, но они активно используются во встроенных структурах Python (например, `dict`, `set` — хеш-таблицы).
1. Реализуйте бинарное дерево поиска.
2. Добавьте функцию подсчёта количества узлов.
3. Напишите функцию для поиска максимального значения.