Сбалансированные деревья

АВЛ-дерево получило своё название по фамилиям его разработчиков – советских математиков Георгия Максимовича Адельсон-Вельского (родился 8 января 1922 г. в Самаре) и Евгения Михайловича Ландиса, которые предложили использовать такое дерево в 1962 году.

АВЛ-дерево полностью удовлетворяет менее строгому определению сбалансированности дерева. Сбалансированность достигается за счёт поворотов (или вращений), а для сравнения высот ветвей в каждом узле двоичного дерева поиска используется дополнительное поле – признак сбалансированности ветвей (или разность их высот).

Красно-чёрное дерево (RB-tree) отличается от АВЛ-дерева смыслом признака сбалансированности: вместо разности высот ветвей используется абстрактный "цвет" (красный или чёрный) и дерево строится по следующим правилам:

1. Все указатели на терминальные узлы считаются непустыми (т.е. в дереве имеются фиктивные терминальные узлы).

2. Все такие терминальные узлы считаются "чёрными".

3. Все узлы, соседние с "красными" узлами, считаются "чёрными" (т.е. запрещена ситуация с двумя "красными" узлами подряд).

4. В левой и правой ветвях дерева, ведущих от его корня к листьям, число "чёрных" узлов одинаково. Это число называется "чёрной высотой" дерева.

Теоретически считается, что красно-чёрное дерево требует меньшего объёма памяти для хранения отдельного узла, чем АВЛ-дерево, т.к. для представления цвета достаточно всего одного бита. Но на практике это преимущество реализовать без потерь на дополнительные операции доступа к отдельным битам весьма сложно. Даже один из вариантов реализации красно-чёрного дерева – когда "красные" узлы обозначаются нечётными ключами, а "чёрные" узлы – чётными (или наоборот), не всегда пригоден на практике, т.к. решаемая задача может не допускать такого разделения узлов.

Используемые при балансировке операции вращения фактически представляют собой переприсвоения значений указателей в узлах дерева и, как следствие, перепроведение связей между узлами, после которого высоты левой и правой ветвей оказываются одинаковыми (или отличаются не более чем на один уровень) и дерево считается сбалансированным.

Б-деревья являются сбалансированными деревьями, у которых число ветвей, исходящих из узлов, может быть 2 и более. Узел, корневой для двух ветвей, содержит единственный ключ, а узел, корневой для нескольких ветвей, содержит составной ключ – несколько ключей, число которых на 1 меньше числа ветвей.

Дата добавления: 2015-07-15