25. Расскажите про бинарное дерево.

Бинарное дерево - иерархическая структура данных, в которой каждый узел может иметь двух потомков. Как правило, первый называется родительским узлом, а наследники называются левым и правым нодами/узлами.

Каждый узел в дереве задаёт поддерево, корнем которого он является. Оба поддерева — левое и правое — тоже являются бинарными деревьями. Ноды, которые не имеют потомков, называются листьями дерева.

У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X. У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X. Этим достигается упорядоченная структура данных, то есть всегда отсортированная.

Поиск в лучшем случае - O(log(n)), худшем - O(n) - при вырождении в связанный список.

Предыдущий вопрос: 24. Расскажите про сортировку слиянием.

Следующий вопрос: 26. Расскажите про красно-черное дерево.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне