Двоичный деревья

Дерево — это иерархическая нелинейная структура данных, состоящая из узлов, соединенных ребрами. В отличие от линейных структур (массивы, списки), деревья позволяют представлять данные с отношениями "родитель-потомок".

Основные понятия:

• Корень (root) - самый верхний узел дерева

• Родительский узел - узел, имеющий дочерние элементы

• Дочерний узел - узел, связанный с узлом выше

• Лист - узел без дочерних элементов

• Ребро - связь между узлами

• Глубина узла - длина пути от корня до узла

• Высота дерева - максимальная глубина листьев

Основные типы деревьев:

1. Бинарные деревья - каждый узел имеет ≤ 2 потомков

2. Двоичные деревья поиска (BST) - бинарное дерево с упорядоченными элементами

3. AVL-деревья - сбалансированные BST

4. Красно-черные деревья - самобалансирующиеся BST

5. B-деревья - используются в файловых системах и базах данных

Сложность операций:

Пример кода:

class BinaryTree:
    def __init__(self, value):
        self.key = value
        self.left_child = None
        self.right_child = None
    
    def insert_left(self, value):
        """Вставка левого потомка"""
        if self.left_child is None:
            self.left_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.left_child = self.left_child
            self.left_child = new_node
    
    def insert_right(self, value):
        """Вставка правого потомка"""
        if self.right_child is None:
            self.right_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.right_child = self.right_child
            self.right_child = new_node
    
    def breadth_first_search(self, key):
        """Поиск в ширину (BFS)"""
        from collections import deque
        queue = deque([self])
        
        while queue:
            current_node = queue.popleft()
            if current_node.key == key:
                return True
            if current_node.left_child:
                queue.append(current_node.left_child)
            if current_node.right_child:
                queue.append(current_node.right_child)
        return False
    
    def preorder(self):
        """Прямой обход (корень -> левое -> правое)"""
        print(self.key, end=' ')
        if self.left_child:
            self.left_child.preorder()
        if self.right_child:
            self.right_child.preorder()
    
    def inorder(self):
        """Симметричный обход (левое -> корень -> правое)"""
        if self.left_child:
            self.left_child.inorder()
        print(self.key, end=' ')
        if self.right_child:
            self.right_child.inorder()
    
    def postorder(self):
        """Обратный обход (левое -> правое -> корень)"""
        if self.left_child:
            self.left_child.postorder()
        if self.right_child:
            self.right_child.postorder()
        print(self.key, end=' ')

	def invert(self):
        """Инверсия дерева (зеркальное отражение)"""
        current = [self]
        next_level = []
        
        while current:
            for node in current:
                # Меняем местами потомков
                node.left_child, node.right_child = node.right_child, node.left_child
                # Добавляем потомков в очередь следующего уровня
                if node.left_child:
                    next_level.append(node.left_child)
                if node.right_child:
                    next_level.append(node.right_child)
            current = next_level
            next_level = []
    
    def __str__(self):
        """Строковое представление дерева"""
        return (f"BinaryTree(key={self.key}, "
                f"left={self.left_child.key if self.left_child else None}, "
                f"right={self.right_child.key if self.right_child else None})")