Что такое древовидная структура?

Древовидная структура данных (Tree)

Древовидная структура — это иерархическая структура данных, состоящая из узлов (nodes), соединённых рёбрами (edges), где один узел является корнем (root), а остальные узлы организованы в подуровни. Каждый узел может иметь ноль или более потомков (children), но имеет ровно одного родителя (parent), кроме корня. Деревья широко используются для представления иерархических отношений в данных.

Основные компоненты

• Node (узел) — элемент дерева, содержащий данные
• Root (корень) — узел без родителя, начало дерева
• Edge (ребро) — связь между узлами
• Parent (родитель) — узел, имеющий потомков
• Child (потомок) — узел, имеющий родителя
• Leaf (листовой узел) — узел без потомков
• Height (высота) — максимальное расстояние от корня до листового узла
• Depth (глубина) — расстояние узла от корня
• Subtree (поддерево) — дерево, состоящее из узла и всех его потомков

Реализация базового дерева на Python

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
    
    def add_child(self, child_node):
        """Добавить потомка"""
        self.children.append(child_node)
    
    def get_height(self):
        """Получить высоту поддерева"""
        if not self.children:
            return 1
        return 1 + max(child.get_height() for child in self.children)
    
    def get_depth(self):
        """Получить глубину узла от корня"""
        if not hasattr(self, 'parent') or self.parent is None:
            return 0
        return 1 + self.parent.get_depth()

# Создание дерева
root = Node("A")
child1 = Node("B")
child2 = Node("C")
child3 = Node("D")
child4 = Node("E")

root.add_child(child1)
root.add_child(child2)
child1.add_child(child3)
child1.add_child(child4)

# Визуально:
#       A (root)
#      / \
#     B   C
#    / \
#   D   E

Обход дерева (Tree Traversal)

Depth-First Search (DFS) — обход в глубину

class Tree:
    def __init__(self, root):
        self.root = root
    
    # Preorder (корень → потомки)
    def preorder(self, node=None):
        if node is None:
            node = self.root
        result = []
        result.append(node.value)
        for child in node.children:
            result.extend(self.preorder(child))
        return result
    
    # Postorder (потомки → корень)
    def postorder(self, node=None):
        if node is None:
            node = self.root
        result = []
        for child in node.children:
            result.extend(self.postorder(child))
        result.append(node.value)
        return result

# Использование
tree = Tree(root)
print(tree.preorder())   # ['A', 'B', 'D', 'E', 'C']
print(tree.postorder())  # ['D', 'E', 'B', 'C', 'A']

Breadth-First Search (BFS) — обход в ширину

from collections import deque

class Tree:
    def levelorder(self):
        """Обход по уровням"""
        result = []
        queue = deque([self.root])
        
        while queue:
            node = queue.popleft()
            result.append(node.value)
            queue.extend(node.children)
        
        return result

# Использование
tree = Tree(root)
print(tree.levelorder())  # ['A', 'B', 'C', 'D', 'E']

Бинарное дерево (Binary Tree)

Частный случай дерева, где каждый узел имеет максимум 2 потомков:

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root):
        self.root = root
    
    def inorder(self, node=None):
        """Левое поддерево → корень → правое поддерево"""
        if node is None:
            node = self.root
        result = []
        if node.left:
            result.extend(self.inorder(node.left))
        result.append(node.value)
        if node.right:
            result.extend(self.inorder(node.right))
        return result
    
    def preorder(self, node=None):
        """Корень → левое поддерево → правое поддерево"""
        if node is None:
            node = self.root
        result = []
        result.append(node.value)
        if node.left:
            result.extend(self.preorder(node.left))
        if node.right:
            result.extend(self.preorder(node.right))
        return result
    
    def postorder(self, node=None):
        """Левое поддерево → правое поддерево → корень"""
        if node is None:
            node = self.root
        result = []
        if node.left:
            result.extend(self.postorder(node.left))
        if node.right:
            result.extend(self.postorder(node.right))
        result.append(node.value)
        return result

# Создание бинарного дерева
#       1
#      / \
#     2   3
#    / \
#   4   5

root = BinaryNode(1)
root.left = BinaryNode(2)
root.right = BinaryNode(3)
root.left.left = BinaryNode(4)
root.left.right = BinaryNode(5)

tree = BinaryTree(root)
print(tree.inorder())    # [4, 2, 5, 1, 3]
print(tree.preorder())   # [1, 2, 4, 5, 3]
print(tree.postorder())  # [4, 5, 2, 3, 1]

Бинарное дерево поиска (Binary Search Tree, BST)

Отсортированное бинарное дерево, где левое поддерево < узел < правое поддерево:

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        """Вставить значение"""
        if self.root is None:
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value):
        """Поиск значения"""
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def inorder(self):
        """Обход в порядке сортировки (left → node → right)"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# Использование
bst = BinarySearchTree()
values = [5, 3, 7, 2, 4, 6, 8]
for val in values:
    bst.insert(val)

print(bst.search(4))      # True
print(bst.search(10))     # False
print(bst.inorder())      # [2, 3, 4, 5, 6, 7, 8]

Практические применения

1. Файловая система — директории и файлы образуют дерево
2. DOM дерево — структура HTML документов
3. Организационная иерархия — структура компании
4. Компилятор — синтаксическое дерево программы
5. Поиск — использование в алгоритмах поиска (DFS, BFS)
6. Сортировка — двоичное дерево поиска для сортировки
7. Индексирование БД — B-tree индексы

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

Для сбалансированного бинарного дерева поиска:

• Поиск — O(log n)
• Вставка — O(log n)
• Удаление — O(log n)
• Обход — O(n)

Для несбалансированного дерева (worst case):

• Все операции — O(n)

Древовидная структура — это фундаментальная структура данных, используемая в множестве алгоритмов и приложений.