Двоичное дерево – это структура данных дерево, в которой каждый узел имеет до двух дочерних узлов, образующих ветви дерева. Два потомка обычно называются левым и правым узлами.
Дерево и древовидная терминология
Предшественник и преемник
Бинарное дерево и почему бинарное дерево?
Типы бинарного дерева:
Представление дерева
- Использование связанного списка
- Использование массива
Общие операции с бинарным деревом:
- Создание дерева
- Вставка узла
- Удаление узла
- Поиск значения
- Пройти все узлы
- Удаление дерева
Двоичное дерево (реализация связанного списка)
Создание дерева
Обход всех узлов бинарного дерева (предварительный заказ):
Обход по порядку
Обход после заказа
Обход порядка уровней
Разные виды деревьев
двоичные деревья поиска (BST), иногда называемые упорядоченными или отсортированными двоичными деревьями, представляют собой контейнер определенного типа: структуру данных, в которой хранятся «элементы». (например, числа, имена и т. д.) в памяти. Они обеспечивают быстрый поиск, добавление и удаление элементов и могут использоваться для реализации либо динамических наборов элементов, либо таблиц поиска, позволяющих находить элемент по его ключу (например, находить номер телефона человека по имени).
Дерево AVL — это еще одно дерево сбалансированного бинарного поиска. Названные в честь своих изобретателей, Адельсона-Вельского и Лэндиса, они были первыми предложенными динамически сбалансированными деревьями. Подобно красно-черным деревьям, они не идеально сбалансированы, но пары под-деревьев отличаются по высоте не более чем на 1, что обеспечивает время поиска O(logn).
