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