Дерево в информатике, как следует из названия, представляет собой структуру данных, напоминающую иерархическое дерево. Состоящий из узлов, ответвляющихся от корневого узла, он соединен вместе направленными или неориентированными ребрами. Каждый узел может относиться к любому типу данных и иметь ноль или несколько дочерних узлов (дочерних узлов). При этом узлы дерева не могут ссылаться на своих родителей. В отличие от связанных списков или массивов деревья нелинейны.
Скорее всего, вы слышали о двоичном дереве, распространенном типе этой структуры данных. «Бинарный» в его имени подразумевает, что каждый из его узлов имеет не более двух дочерних элементов, левого и правого дочерних элементов. Деревья двоичного поиска следуют тому же принципу с некоторыми дополнительными характеристиками. Любые левые поддеревья должны иметь дочерние узлы со значениями меньше, чем у родительского узла, и наоборот, применяется к любым правым поддеревьям. В то время как общее двоичное дерево не поддерживает какой-либо порядок, в котором организованы его узлы, двоичные деревья поиска делают это с помощью метода сортировки значений.
