Древовидная Структура Данных | Иллюстрированные Структуры Данных

• Деревья представляют иерархические данные, такие как организационные иерархии и структуры каталогов.  

• Элементы дерева называются узлами, а путь между узлами - ребром.  

• Конечные узлы не имеют дочерних узлов, корневой узел - первый узел, а родительский узел - узел над любым другим узлом.  

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

• Высота узла - максимальное расстояние от вершины до конечного узла в дочерних узлах.  

• Двоичное дерево: каждый узел имеет не более двух дочерних узлов.  

• Дерево бинарного поиска: узлы отсортированы, значение в левом узле меньше родительского, в правом - больше.  

• Поиск узла: начиная с корневого узла, сравниваем значение с родительским и переходим к нужной стороне дерева.  

• Вставка узла: сравниваем значение с родительским и вставляем узел в нужное место дерева.  

• Несбалансированные деревья: каждая вставка увеличивает высоту дерева, что делает операции медленными.  

• Сбалансированные деревья: количество узлов слева и справа от корня равно, что делает операции логарифмически быстрыми.  

• Обход по порядку: посещаем левый узел, родительский узел, правый узел.  

• Обход по предварительному заказу: посещаем корневой узел, левый узел, правый узел.  

• Обход по пост-заказу: посещаем левый узел, правый узел, корневой узел.