Бинарные деревья
Бинарные деревья в чем-то похожи на бинарный поиск в отсортированном массиве, только применяется на этапе создания этой структуры данных.
По сути это «двунаправленные списки, адаптированные для алгоритма бинарного поиска».
Ключевым для классического бинарного дерева является наличие уникальных идентификаторов/индексов/хеш сумм и тд. Которые можно сравнивать, за счет этого можно двигаться по дереву.
Прародитель (Data1) называется корнем дерева, в бинарном дереве каждый родитель может иметь до 2 наследников, если наследников нет т.е. указатели равны nullptr (как у нижних кружков), то такие объекты называются листьями.
Рассмотрим пример:
Мы сформировали дерево на основе уникальных/неповторяющихся данных или например расчета контрольных/хеш сумм (данные попадали не сортированные)
Есть некоторый абстрактный индекс/идентификатор с названием Data, который также соответствует интересующим нам данным/классу/ссылке на нужные данные и тд.
Пусть Data1 равен 10, а мы хотим попасть и получить данные из идентификатора DataN равного 40, Data2=5, а Data3=15.
Data1 является корнем дерева, и мы двигаемся из него.
По правилам бинарных деревьев то, что находится слева меньше текущего ID, а то что справа больше, поэтому ветка с Data2 и его наследниками (в данном случае листьями т.к. не имеют продолжения) сразу отпадает, переходим вправо, в Data3.
Data3 и имеет левого и правого наследника, также DataN> Data3, поэтому опять идем по правой ветке, а левая отпадает, в результате мы приходим в DataN.
Бинарное дерево является по сути рекурсивной структурой, поэтому нужно знать корень дерева и в ряде случаев использовать рекурсивные алгоритмы.