Оглавление:
- Определение - Что означает Самобалансирующееся Дерево Бинарного Поиска?
- Techopedia объясняет самобалансирующееся дерево двоичного поиска
Определение - Что означает Самобалансирующееся Дерево Бинарного Поиска?
Самобалансирующееся двоичное дерево поиска - это тип структуры данных, который самонастраивается для обеспечения согласованных уровней доступа к узлу. В самобалансирующемся бинарном дереве поиска соединения от верхнего узла к дополнительным узлам сортируются и перестраиваются так, чтобы дерево было четным, а линии траектории поиска для каждого конечного узла были равны по длине.
Самобалансирующееся дерево двоичного поиска также известно как сбалансированное дерево или дерево двоичного поиска с балансировкой по высоте.
Techopedia объясняет самобалансирующееся дерево двоичного поиска
Бинарное дерево поиска в общем случае предоставляет структуру данных с одним узлом наверху и одним или двумя узлами, подключенными к нему на каждом последующем уровне. Деревья двоичного поиска поддерживают три операции - операторы могут вставлять компоненты, удалять компоненты или искать некоторое число или другое содержимое узла. Отчасти преимущество двоичных деревьев поиска заключается в том, что система может сортировать, игнорируя одну половину дерева на каждом уровне, что приводит к более эффективным рабочим нагрузкам поиска.
Положительным аспектом самобалансирующегося бинарного дерева поиска является то, что доступ к узлу одинаков - например, вместо того, чтобы делать пять шагов на одной стороне дерева или три шага на другой стороне дерева, из-за собственной -корректированная структура узла, поиск будет проходить только определенное количество шагов (n) для любого заданного конечного узла. Это достигается путем удаления отдельных узловых соединений и замены их бинарными для сокращения отдельных ветвей дерева.
Недостаток самобалансирующегося бинарного поиска три состоит в том, что он работает только в том случае, если соединения узлов «независимы от уровня» - другими словами, если отдельный узел может быть перенастроен на предыдущий уровень для сокращения ветви дерева., Например, если самобалансирующееся двоичное дерево поиска составлено с заданным номером вверху и двумя последующими числами с каждой стороны, и имеется цепочка из трех дополнительных чисел с соединениями с одним узлом, корректировка дерева приведет к пятый узел вместе с третьим узлом вместо четвертого узла, так что третий узел имеет два соединительных узла вместо одного. Однако, если структура данных должна идентифицировать конкретное содержимое узла как связанное с определенным родителем / дочерним отношением, корректировка этих узлов в соответствии с равномерностью древовидной структуры не будет работать.
