Двоичные деревья
Существует два основных типа бинарных деревьев: сбалансированные и несбалансированные. Сбалансированное дерево стремится поддерживать высоту дерева (высота = количество узлов между корнем и самым дальним потомком) как можно более равномерно. Существует несколько типов алгоритмов для сбалансированных деревьев, два самых известных из которых - AVL- и RedBlack-деревья. Сложность операций вставки / удаления / поиска на деревьях AVL и RedBlack составляет O (log n) или лучше - что является важной частью. Другими алгоритмами самобалансировки являются дерево AA, Splay и Scapegoat.
Сбалансированные деревья приобретают свойство (и имя) быть уравновешенными из-за того факта, что после каждой операции удаления или вставки в дерево алгоритм анализирует дерево, чтобы убедиться, что оно все еще сбалансировано, в противном случае оно попытается это исправить ( что делается по-разному с каждым алгоритмом), вращая узлы вокруг дерева.
Обычные (или несбалансированные) бинарные деревья не изменяют свою структуру, чтобы поддерживать себя сбалансированными, и имеют риск, чаще всего со временем, стать очень неэффективными (особенно, если значения вставляются по порядку). Однако, если производительность не имеет значения, и вы в основном хотите отсортированную структуру данных, тогда они могут это сделать. Сложность операций вставки / удаления / поиска в несбалансированном дереве варьируется от O (1) (в лучшем случае - если вы хотите получить корень) до O (n) (в худшем случае, если вы вставили все узлы по порядку и хотите самый большой узел )
Существует еще один вариант, который называется рандомизированным двоичным деревом, в котором используется какая-то рандомизация, чтобы убедиться, что дерево не становится полностью несбалансированным (что совпадает со связным списком)