Двоичные деревья представляют собой структуры данных, упорядочивающие вставляемые узлы: элементы, меньшие узла, записываются в его левое поддерево, а элементы, б льшие узла, помещаются в правое. Самые нижние поддеревья пусты. Вследствие такой структуры двоичные деревья естественным образом поддерживают быстрый рекурсивный обход и, соответственно, быстрый поиск для широкого круга применений — по крайней мере, в идеальном случае при каждом переходе к поддереву пространство поиска сокращается вдвое.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
