Как построить сбалансированное бинарное дерево

Сбалансированное дерево поиска B-tree (t=2)

На 3-м курсе обучения в своем университете передо мной встала задача реализовать B-дерево, содержащее уникальные ключи, упорядоченное по возрастанию (со степенью t=2) на языке c++ (с возможностью добавления, удаления, поиска элементов и соответственно, перестройкой дерева).

Перечитав несколько статей на Хабре (например, B-tree, 2-3-дерево. Наивная реализация и другие), казалось бы, все было ясно. Только теоретически, а не практически. Но и с этими трудностями мне удалось справиться. Цель моего поста — поделиться полученным опытом с пользователями.

Немного основных моментов

B-деревом называется дерево, удовлетворяющее следующим свойствам:
1. Каждый узел содержит хотя бы один ключ. Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила. Здесь t — параметр дерева, не меньший 2.
2. У листьев потомков нет. Любой другой узел, содержащий n ключей, содержит n+1 потомков. При этом:
а) Первый потомок и все его потомки содержат ключи из интервала ;
б) Для , i-й потомок и все его потомки содержат ключи из интервала ;
в) (n+1)-й потомок и все его потомки содержат ключи из интервала .
3. Глубина всех листьев одинакова.

Реализация

Для начала создадим структуру узла нашего дерева.
Структура узла

const int t=2; struct BNode < int keys[2*t]; BNode *children[2*t+1]; BNode *parent; int count; //количество ключей int countSons; //количество сыновей bool leaf; >;

Теперь создадим класс Tree, включающий в себя соответствующие методы.

Класс Tree

class Tree < private: BNode *root; void insert_to_node(int key, BNode *node); void sort(BNode *node); void restruct(BNode *node); void deletenode(BNode *node); bool searchKey(int key, BNode *node); void remove(int key, BNode *node); void removeFromNode(int key, BNode *node); void removeLeaf(int key, BNode *node); void lconnect(BNode *node, BNode *othernode); void rconnect(BNode *node, BNode *othernode); void repair(BNode *node); public: Tree(); ~Tree(); void insert(int key); bool search(int key); void remove(int key); >;

Сразу описываем конструктор и деструктор. В деструкторе вызывается рекурсивный метод удаления элементов из дерева.

Конструктор и деструктор

Tree::Tree() < root=nullptr; >Tree::~Tree() < if(root!=nullptr) deletenode(root); >void Tree::deletenode(BNode *node)< if (node!=nullptr)< for (int i=0; ichildren[i]!=nullptr) deletenode(node->children[i]); else < delete(node); break; >> > >

Первым делом рассмотрим добавление ключа в узел. В моем случае (t=2) это будет выглядеть следующим образом:

Т.е., как только в узле становится больше 3 элементов — узел разбивается.
Итак, для добавления элемента в дерево необходимо реализовать несколько методов.
Первый – простое добавление в узел. В данном методе вызывается метод сортировки, необходимый для выполнения условия о возрастающих значениях дерева. Второй метод –
добавления значения в узел, в котором предварительно ищется нужная позиция и при
необходимости (в узле становится больше 3 элементов) вызывается третий метод – метод разбиения узла на: родителя и двух сыновей.

Первый метод – метод простого добавления.

Метод простого добавления

void Tree::insert_to_node(int key, BNode *node)< node->keys[node->count]=key; node->count=node->count+1; sort(node); >

Метод сортировки чисел в узле:

Метод сортировки

void Tree::sort(BNode *node) < int m; for (int i=0; ikeys[i]!=0) && (node->keys[j]!=0))< if ((node->keys[i]) > (node->keys[j]))< m=node->keys[i]; node->keys[i]=node->keys[j]; node->keys[j]=m; > > else break; > > >

Думаю, тут всё понятно.

Второй метод – метод добавления значения в узел с предварительным поиском позиции:

Метод добавления в узел с предварительным поиском

void Tree::insert(int key)< if (root==nullptr) < BNode *newRoot = new BNode; newRoot->keys[0]=key; for(int j=1; jkeys[j]=0; for (int i=0; ichildren[i]=nullptr; newRoot->count=1; newRoot->countSons=0; newRoot->leaf=true; newRoot->parent=nullptr; root=newRoot; > else < BNode *ptr=root; while (ptr->leaf==false)< //выбор ребенка до тех пор, пока узел не будет являться листом for (int i=0; ikeys[i]!=0) < if (keykeys[i]) < ptr=ptr->children[i]; break; > if ((ptr->keys[i+1]==0)&&(key>ptr->keys[i])) < ptr=ptr->children[i+1]; //перенаправляем к самому последнему ребенку, если цикл не "сломался" break; > > else break; > > insert_to_node(key, ptr); while (ptr->count==2*t) < if (ptr==root)< restruct(ptr); break; >else < restruct(ptr); ptr=ptr->parent; > > > >

Третий метод – метод разбиения узла:

Метод разбиения узла

void Tree::restruct(BNode *node)< if (node->count<(2*t-1)) return; //первый сын BNode *child1 = new BNode; int j; for (j=0; j<=t-2; j++) child1->keys[j]=node->keys[j]; for (j=t-1; jkeys[j]=0; child1->count=t-1; //количество ключей в узле if(node->countSons!=0)< for (int i=0; ichildren[i]=node->children[i]; child1->children[i]->parent=child1; > for (int i=t; ichildren[i]=nullptr; child1->leaf=false; child1->countSons=t-1; //количество сыновей > else < child1->leaf=true; child1->countSons=0; for (int i=0; ichildren[i]=nullptr; > //второй сын BNode *child2 = new BNode; for (int j=0; jkeys[j]=node->keys[j+t]; for (j=t; jkeys[j]=0; child2->count=t; //количество ключей в узле if(node->countSons!=0) < for (int i=0; ichildren[i]=node->children[i+t]; child2->children[i]->parent=child2; > for (int i=t+1; ichildren[i]=nullptr; child2->leaf=false; child2->countSons=t; //количество сыновей > else < child2->leaf=true; child2->countSons=0; for (int i=0; ichildren[i]=nullptr; > //родитель if (node->parent==nullptr)< //если родителя нет, то это корень node->keys[0]=node->keys[t-1]; for(int j=1; jkeys[j]=0; node->children[0]=child1; node->children[1]=child2; for(int i=2; ichildren[i]=nullptr; node->parent=nullptr; node->leaf=false; node->count=1; node->countSons=2; child1->parent=node; child2->parent=node; > else < insert_to_node(node->keys[t-1], node->parent); for (int i=0; iparent->children[i]==node) node->parent->children[i]=nullptr; > for (int i=0; iparent->children[i]==nullptr) < for (int j=(2*t); j>(i+1); j--) node->parent->children[j]=node->parent->children[j-1]; node->parent->children[i+1]=child2; node->parent->children[i]=child1; break; > > child1->parent=node->parent; child2->parent=node->parent; node->parent->leaf=false; delete node; > >

Для поиска были реализованы следующие методы, возвращающие true или false (второй метод рекурсивный):

bool Tree::search(int key)< return searchKey(key, this->root); > bool Tree::searchKey(int key, BNode *node)< if (node!=nullptr)< if (node->leaf==false)< int i; for (i=0; ikeys[i]!=0) < if(key==node->keys[i]) return true; if ((keykeys[i]))< return searchKey(key, node->children[i]); break; > > else break; > return searchKey(key, node->children[i]); > else < for(int j=0; jkeys[j]) return true; return false; > > else return false; >

Реализация метода удаления ключа из узла была самой сложной. Ведь в некоторых случаях удаления нужно склеивать соседние узлы, а в некоторых брать значения из узлов «братьев». Например:

Удаление представляет собой несколько случаев. Первый из них — простой метод удаления ключа из узла:

Метод удаления ключа из узла

void Tree::removeFromNode(int key, BNode *node)< for (int i=0; icount; i++)< if (node->keys[i]==key)< for (int j=i; jcount; j++) < node->keys[j]=node->keys[j+1]; node->children[j]=node->children[j+1]; > node->keys[node->count-1]=0; node->children[node->count-1]=node->children[node->count]; node->children[node->count]=nullptr; break; > > node->count--; >

Во втором же случае после удаления ключа необходимо соединить соседние узлы. Поэтому второй и третий методы – методы соединения узлов:

Методы соединения узлов

void Tree::lconnect(BNode *node, BNode *othernode)< if (node==nullptr) return; for (int i=0; i<=(othernode->count-1); i++)< node->keys[node->count]=othernode->keys[i]; node->children[node->count]=othernode->children[i]; node->count=node->count+1; > node->children[node->count]=othernode->children[othernode->count]; for (int j=0; jcount; j++)< if (node->children[j]==nullptr) break; node->children[j]->parent=node; > delete othernode; > void Tree::rconnect(BNode *node, BNode *othernode)< if (node==nullptr) return; for (int i=0; i<=(othernode->count-1); i++)< node->keys[node->count]=othernode->keys[i]; node->children[node->count+1]=othernode->children[i+1]; node->count=node->count+1; > for (int j=0; jcount; j++)< if (node->children[j]==nullptr) break; node->children[j]->parent=node; > delete othernode; >

Четвертый метод – метод «починки» узла. В данном методе дерево в буквальном смысле перестраивается до тех пор, пока не будут удовлетворены все условия B-дерева:

Метод «починки» узла

void Tree::repair(BNode *node)< if ((node==root)&&(node->count==0))< if (root->children[0]!=nullptr)< root->children[0]->parent=nullptr; root=root->children[0]; > else < delete root; >return; > BNode *ptr=node; int k1; int k2; int positionSon; BNode *parent=ptr->parent; for (int j=0; jcount; j++)< if (parent->children[j]==ptr) < positionSon=j; //позиция узла по отношению к родителю break; >> //если ptr-первый ребенок (самый левый) if (positionSon==0)< insert_to_node(parent->keys[positionSon], ptr); lconnect(ptr, parent->children[positionSon+1]); parent->children[positionSon+1]=ptr; parent->children[positionSon]=nullptr; removeFromNode(parent->keys[positionSon], parent); if(ptr->count==2*t)< while (ptr->count==2*t) < if (ptr==root)< restruct(ptr); break; >else < restruct(ptr); ptr=ptr->parent; > > > else if (parent->count <=(t-2)) repair(parent); >else < //если ptr-последний ребенок (самый правый) if (positionSon==parent->count)< insert_to_node(parent->keys[positionSon-1], parent->children[positionSon-1]); lconnect(parent->children[positionSon-1], ptr); parent->children[positionSon]=parent->children[positionSon-1]; parent->children[positionSon-1]=nullptr; removeFromNode(parent->keys[positionSon-1], parent); BNode *temp=parent->children[positionSon]; if(ptr->count==2*t)< while (temp->count==2*t) < if (temp==root)< restruct(temp); break; >else < restruct(temp); temp=temp->parent; > > > else if (parent->count <=(t-2)) repair(parent); >else < //если ptr имеет братьев справа и слева insert_to_node(parent->keys[positionSon], ptr); lconnect(ptr, parent->children[positionSon+1]); parent->children[positionSon+1]=ptr; parent->children[positionSon]=nullptr; removeFromNode(parent->keys[positionSon], parent); if(ptr->count==2*t)< while (ptr->count==2*t) < if (ptr==root)< restruct(ptr); break; >else < restruct(ptr); ptr=ptr->parent; > > > else if (parent->count <=(t-2)) repair(parent); >> >

Пятый метод – метод удаления ключа из листа:

Метод удаления ключа из листа

void Tree::removeLeaf(int key, BNode *node)< if ((node==root)&&(node->count==1))< removeFromNode(key, node); root->children[0]=nullptr; delete root; root=nullptr; return; > if (node==root) < removeFromNode(key, node); return; >if (node->count>(t-1)) < removeFromNode(key, node); return; >BNode *ptr=node; int k1; int k2; int position; int positionSon; int i; for (int i=0; icount-1; i++)< if (key==node->keys[i]) < position=i; //позиция ключа в узле break; >> BNode *parent=ptr->parent; for (int j=0; jcount; j++)< if (parent->children[j]==ptr) < positionSon=j; //позиция узла по отношению к родителю break; >> //если ptr-первый ребенок (самый левый) if (positionSon==0)< if (parent->children[positionSon+1]->count>(t-1))< //если у правого брата больше, чем t-1 ключей k1=parent->children[positionSon+1]->keys[0]; //k1 - минимальный ключ правого брата k2=parent->keys[positionSon]; //k2 - ключ родителя, больше, чем удаляемый, и меньше, чем k1 insert_to_node(k2, ptr); removeFromNode(key, ptr); parent->keys[positionSon]=k1; //меняем местами k1 и k2 removeFromNode(k1, parent->children[positionSon+1]); //удаляем k1 из правого брата > else < //если у правого единственного брата не больше t-1 ключей removeFromNode(key, ptr); if (ptr->count <=(t-2)) repair(ptr); >> else < //если ptr-последний ребенок (самый правый) if (positionSon==parent->count)< //если у левого брата больше, чем t-1 ключей if (parent->children[positionSon-1]->count>(t-1))< BNode *temp=parent->children[positionSon-1]; k1=temp->keys[temp->count-1]; //k1 - максимальный ключ левого брата k2=parent->keys[positionSon-1]; //k2 - ключ родителя, меньше, чем удаляемый и больше, чем k1 insert_to_node(k2, ptr); removeFromNode(key, ptr); parent->keys[positionSon-1]=k1; removeFromNode(k1, temp); > else < //если у единственного левого брата не больше t-1 ключей removeFromNode(key, ptr); if (ptr->count <=(t-2)) repair(ptr); >> else < //если ptr имеет братьев справа и слева //если у правого брата больше, чем t-1 ключей if (parent->children[positionSon+1]->count>(t-1))< k1=parent->children[positionSon+1]->keys[0]; //k1 - минимальный ключ правого брата k2=parent->keys[positionSon]; //k2 - ключ родителя, больше, чем удаляемый и меньше, чем k1 insert_to_node(k2, ptr); removeFromNode(key, ptr); parent->keys[positionSon]=k1; //меняем местами k1 и k2 removeFromNode(k1, parent->children[positionSon+1]); //удаляем k1 из правого брата > else < //если у левого брата больше, чем t-1 ключей if (parent->children[positionSon-1]->count>(t-1))< BNode *temp=parent->children[positionSon-1]; k1=temp->keys[temp->count-1]; //k1 - максимальный ключ левого брата k2=parent->keys[positionSon-1]; //k2 - ключ родителя, меньше, чем удаляемый и больше, чем k1 insert_to_node(k2, ptr); removeFromNode(key, ptr); parent->keys[positionSon-1]=k1; removeFromNode(k1, temp); > else < //если у обоих братьев не больше t-1 ключей removeFromNode(key, ptr); if (ptr->count <=(t-2)) repair(ptr); >> > > >

Шестой метод – метод удаления из произвольного узла:

Метод удаления из произвольного узла

void Tree::remove(int key, BNode *node)< BNode *ptr=node; int position; //номер ключа int i; for (int i=0; icount-1; i++)< if (key==node->keys[i]) < position=i; break; >> int positionSon; //номер сына по отношению к родителю if (ptr->parent!=nullptr)< for(int i=0; iparent->count; i++)< if (ptr->children[i]==ptr) < positionSon==i; break; >> > //находим наименьший ключ правого поддерева ptr=ptr->children[position+1]; int newkey=ptr->keys[0]; while (ptr->leaf==false) ptr=ptr->children[0]; //если ключей в найденном листе не больше 1 - ищем наибольший ключ в левом поддереве //иначе - просто заменяем key на новый ключ, удаляем новый ключ из листа if (ptr->count>(t-1)) < newkey=ptr->keys[0]; removeFromNode(newkey, ptr); node->keys[position]=newkey; > else < ptr=node; //ищем наибольший ключ в левом поддереве ptr=ptr->children[position]; newkey=ptr->keys[ptr->count-1]; while (ptr->leaf==false) ptr=ptr->children[ptr->count]; newkey=ptr->keys[ptr->count-1]; node->keys[position]=newkey; if (ptr->count>(t-1)) removeFromNode(newkey, ptr); else < //если ключей не больше, чем t-1 - перестраиваем removeLeaf(newkey, ptr); >> >

И седьмой метод – сам метод удаления, принимающий в качестве входных данных — значение ключа для удаления из дерева.

Основной метод удаления

void Tree::remove(int key)< BNode *ptr=this->root; int position; int positionSon; int i; if (searchKey(key, ptr)==false) < return; >else < //ищем узел, в котором находится ключ для удаления for (i=0; icount-1; i++)< if (ptr->keys[i]!=0) < if(key==ptr->keys[i]) < position=i; break; >else < if ((keykeys[i]))< ptr=ptr->children[i]; positionSon=i; i=-1; > else < if (i==(ptr->count-1)) < ptr=ptr->children[i+1]; positionSon=i+1; i=-1; > > > > else break; > > if (ptr->leaf==true) < if (ptr->count>(t-1)) removeFromNode(key,ptr); else removeLeaf(key, ptr); > else remove(key, ptr); >

Вот, как-то так. Надеюсь, кому-то статья будет полезной. Спасибо за внимание.

• c++
• структуры данных
• B-tree
• Б-дерево
• алгоритмы обработки данных

Сбалансированное бинарное дерево из отсортированного массива

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

Дерево поиска с минимальной высотой как раз и называется сбалансированным, т.е. таким, в котором высота левого и правого поддеревьев отличаются не более чем на единицу.

Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.

Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.

�� Веду телеграм-канал с еженедельными разборами задач для собеседований.

Каким образом реализовать алгоритм?

Можно каждый раз начинать вставку нового элемента с корня, рекурсивно обходя все дерево для поиска места для нового узла.

Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.

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

Алгоритм получился примерно такой:

• выбрать средний элемент массива в качестве корня
• начинать создавать левое поддерево из левой части массива
• начинать создавать правое поддерево из правой части массива
• повторить рекурсивно, пока не закончатся элементы в массиве

Реализация получилась довольно простой. Единственное на что нужно обратить внимание — смещение на единицу при выборе границ частей массива.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.

Балансировка — Алгоритмы на деревьях

Древовидные структуры достаточно гибкие по своей задумке. Один и тот же набор значений можно расположить в виде дерева, если использовать разные топологические решения. В итоге два дерева с одинаковым содержимым будут обладать противоположными характеристиками, например, по скорости поиска узлов.

Ученые еще в середине прошлого века заинтересовались вопросом оптимизации хранения данных в деревьях. Они хотели обеспечить максимальную скорость поиска в них. Так появились сбалансированные деревья.

В этом уроке мы детально познакомимся с балансировкой деревьев, способами ребалансировки при добавлении новых узлов, а также рассмотрим новые виды древовидных структур.

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

Идеальная сбалансированность — это свойство дерева, при котором все его уровни, иногда кроме последнего, полностью заполнены.

Для сравнения рассмотрим два бинарных дерева поиска, которые будут представлять собой одну последовательность элементов — 1,2,3,4,5,6. Из этой последовательности можно построить несколько деревьев, например:

В дереве (б) каждый из уровней, кроме левой ветки узла 1, заполнены. Значит, дерево (б) — идеально сбалансированное дерево. Что нельзя сказать о дереве (а).

Дерево (а) и дерево (б) можно отнести к бинарным деревьям поиска. Но для худшего случая — поиска в дереве элемента №6 в дереве (а) — требуется выполнить шесть операций перехода между вершинами, а в случае (б) — только три.

Дерево с максимально возможной высотой (а) называется разбалансированным или вырожденным деревом. Оно не отличается от двусвязного списка, значит, теряет свое основное преимущество — скорость поиска.

Для разбалансированных деревьев скорость составляет

. А для идеально сбалансированного дерева (б) поиск будет завершен за число шагов, которые не превышают высоту дерева или за

Состояние идеальной сбалансированности в дереве трудно поддерживать. Любое добавление или удаление узла в сбалансированном дереве может привести к ситуации, когда дерево выйдет из идеально сбалансированного состояния. В таком случае скорость поиска будет значительно деградировать после каждой вставки или удаления узла.

Чтобы вернуть дерево в сбалансированный вид, его перестраивают после каждой манипуляции с составом узлов. Рассмотрим пример с добавлением элемента №7 в наше дерево. Это можно сделать несколькими способами:

В случае (б) дерево вышло из состояния идеальной сбалансированности, так как оба нижних уровня не заполнены полностью. В таком случае поиск элемента №7 будет выполнен за четыре операции.

В случае (а) элементы были перераспределены, чтобы сохранить сбалансированное состояние. В таком случае поиск элемента №7 будет выполнен всего за три операции.

На таких маленьких примерах выигрыш в одну операцию во время поиска может показаться слишком незначительным, чтобы постоянно перестраивать дерево. Но при работе с деревьями из миллионов узлов и повышенных требованиях к скорости выборки такое перестроение может себя оправдать. Пользователям очень нравится, когда приложение работает со скоростью человеческой мысли.

Ресурсы вычислительных машин не безграничны. Чтобы снизить нагрузку на них и одновременно с этим максимально сохранить преимущества идеально сбалансированного дерева, придумали новые виды деревьев. Среди них особенно выделяются АВЛ-деревья и красно-черные деревья, с которыми мы познакомимся подробнее.

АВЛ-деревья

Этот вид деревьев представили в 1962 году двое советских ученых: Адельсон-Вельский Г.М. и Ландис Е.М. Именно по сокращению от их фамилий АВЛ-деревья и получили такое название.

АВЛ-деревья отличаются от идеально сбалансированных. АВЛ-дерево считается сбалансированным, если для каждого узла дерева высота его правого и левого поддеревьев отличаются не более чем на единицу. Если модификация структуры узлов приводит к нарушению сбалансированности дерева, то необходимо выполнить его балансировку.

Поиск в АВЛ-дереве выполняется аналогично работе с бинарным деревом поиска. При этом благодаря поддержке возможности ребалансировки при вставки и удалении узлов в АВЛ-деревьях есть особенности реализации.

В качестве индикатора наличия разбалансированности в поддереве на узел выносят показатель баланса, который принимает значения от -1 до +1. Их значения:

• –1 — в правом поддереве больше вершин
• 0 — поддеревья равной высоты
• +1 — вершин больше в левом поддереве

В итоге код нашего узла принимает следующий вид:

class AvlTreeNode  constructor(value, parent)  this.left = null; //ссылка на левый дочерний узел this.right = null; //ссылка на правый дочерний this.balanceFactor = 0; //показатель сбалансированности this.parent = parent; //ссылка на родителя this.value = value; //полезная нагрузка > >

class AvlTreeNode  public AvlTreeNode left = null; // ссылка на левый дочерний узел public AvlTreeNode right = null; // ссылка на правый дочерний public int balanceFactor = 0; // показатель сбалансированности public AvlTreeNode parent; // ссылка на родителя public Object value; // полезная нагрузка AvlTreeNode(Object value, AvlTreeNode parent)  this.parent = parent; this.value = value; > >

class AvlTreeNode: def __init__(self, value, parent=None): self.left = None # ссылка на левый дочерний узел self.right = None # ссылка на правый дочерний узел self.balance_factor = 0 # показатель сбалансированности self.parent = parent # ссылка на родителя self.value = value # полезная нагрузка

Этот фрагмент кода определяет базовый скелет узла нашего будущего дерева. Чтобы превратить его в полноценное АВЛ-дерево, нужно добавить возможность искать и модифицировать узлы. Операцию поиска можно переиспользовать из бинарных деревьев поиска, а изменение в структуре дерева потребует дополнительной частичной ребалансировки.

Далее мы подробно поговорим об операциях добавления и удаления узлов в АВЛ-деревьях.

Модификация структуры узлов

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

Ребалансировка деревьев осуществляется при помощи специальных механизмов — методов вращения. Вращения бывают двух видов: левое и правое.

Вращение вправо выполняется за три шага:

1. Текущий корень поддерева (D) заменяется на левый дочерний узел (B)
2. Предыдущий корень (D) становится правым дочерним узлом для (B)
3. Предыдущее правое поддерево узла (B) становится левым поддеревом для (D)

Вращение влево выполняется аналогично:

1. Текущий корень поддерева (D) заменяется на правый дочерний узел ©
2. Предыдущий корень (D) становится левым дочерним узлом для ©
3. Предыдущее левое поддерево узла © становится правым поддеревом для (D)

В зависимости от того, куда добавили новую вершину, возможны различные комбинации выполнения вращений. Они помогут вернуть дерево в сбалансированное состояние.

Всего выделяется четыре варианта развития событий:

• Левое поддерево левой дочерней вершины
• Левое поддерево правой дочерней вершины
• Правое поддерево левой дочерней вершины
• Правое поддерево правой дочерней вершины

Рассмотрим пример, который описывает первый случай — вставку в левое поддерево левой дочерней вершины. Изображенные треугольники представляют собой сбалансированные АВЛ-поддеревья. Они могут содержать большое количество вершин. У вершины В дерево не сбалансировано, поскольку поддерево А1 в вершине А на два уровня выше, чем поддерево В2:

Чтобы сбалансировать дерево, необходимо совершить правое вращение — заменить вершину В вершиной А и сделать поддерево А2 левым поддеревом вершины В. После такого преобразования наше поддерево примет следующий вид:

Четвертый сценарий будет выглядеть аналогично кроме замены способа вращения на левое.

Для второго и третьего сценариев необходимо выполнить вращение дважды:

Удаление узлов также осуществляется при помощи механизмов вращения. При возврате во время рекурсивного спуска осуществляется вычисление balanceFactor. Если он отклоняется от допустимых значений, то выполняется ребалансировка аналогично добавлению узла.

Другим видом автоматически балансирующихся деревьев являются красно-черные деревья, с которыми мы познакомимся дальше.

Красно-черные деревья

Красно-черные деревья — одни из наиболее активно используемых на практике самобалансирующихся деревьев. Они так называются из-за наличия на узле дополнительного поля, в котором размещается цвет узла. В качестве стандартных цветов используют обычно красные и черные узлы, а сам цвет узла используется во время балансировки.

Так как красно-черные деревья самобалансирующиеся, то среднее и худшее время поиска тоже составляют

. А операции вставки и удаления узла могут потребовать поворот поддерева.

Для красно-черного дерева наш код узла примет следующий вид:

class RBTreeNode  constructor(value, parent)  this.left = null; //ссылка на левый дочерний узел this.right = null; //ссылка на правый дочерний this.isRed = false; //цвет узла. Если не красный, то считаем что узел черный this.parent = parent; //ссылка на родителя this.value = value; //полезная нагрузка > >

class RBTreeNode  public RBTreeNode left = null; // ссылка на левый дочерний узел public RBTreeNode right = null; // ссылка на правый дочерний public boolean isRed = false; // Цвет узла // Если узел не красный, то считаем что он черный public RBTreeNode parent; // ссылка на родителя public Object value; // полезная нагрузка RBTreeNode(Object value, RBTreeNode parent)  this.parent = parent; this.value = value; > >

class RBTreeNode: def __init__(self, value, parent=None): self.left = None # ссылка на левый дочерний узел self.right = None # ссылка на правый дочерний узел self.is_red = False # цвет узла. Если не красный, то считаем что узел черный self.parent = parent # ссылка на родителя self.value = value # полезная нагрузка

В отличие от других видов деревьев в листовых узлах красно-черных деревьев не хранят полезную нагрузку. А цвет листовых узлов без данных всегда считается черным. Такая особенность позволяет считать ссылку на null валидным узлом. Эта особенность позволит сэкономить память. А само дерево принимает следующий вид:

Помимо особенностей работы с листовыми узлами к свойствам красно-черного так же относят:

1. Корень красно-черного дерева черный
2. Две красные вершины не могут идти подряд ни на одном пути. Оба потомка каждого красного узла — черные
3. Для каждой вершины, в каждом исходящем из нее пути, одинаковое число черных вершин

Иногда при работе с узлами красно-черного дерева используют черную высоту — количество черных вершин на исходящих из нее путях, не включая саму исходную вершину.

Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются пустыми узлами и предполагаются черными. После вставки красим узел в красный цвет. Далее смотрим на предка и проверяем, не нарушается ли свойства дерева, которые описали выше. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.

Сбалансированность этих деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.

Благодаря этим преимуществам сфера применения красно-черных деревьев существенно шире. Так, например, в стандартной библиотеке шаблонов языка C++ STL и TreeMap в Java применяются именно красно-черные деревья.

АВЛ-дерево

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

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

Высота дерева

АВЛ-дерево с [math]n[/math] ключами имеет высоту [math]h = O(\log n)[/math] .

Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .

Пусть [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] , тогда [math]m_h = F_ — 1[/math] , где [math]F_h — h[/math] -ое число Фибоначчи.

Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_ = m_ + m_h + 1[/math] . Равенство [math]m_h = F_ — 1[/math] докажем по индукции.

База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .

Допустим [math]m_h = F_ — 1[/math] — верно.

Тогда [math]m_ = m_h + m_ + 1 = F_ — 1 + F_ — 1 + 1 = F_ — 1[/math] .

[math]F_h = \Omega(\varphi^h)[/math] , [math]\varphi = \dfrac< \sqrt+1>[/math] . То есть

[math]n \geqslant \varphi^[/math]

Логарифмируя по основанию [math]\varphi[/math] , получаем

[math]\log_n \geqslant h[/math]

Балансировка

Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) — h(R)| = 2[/math] , изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) — h(R)| \leqslant 1[/math] , иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева [math]diff[i] = h(L) — h(R)[/math]

Для балансировки вершины используются один из 4 типов вращений:

[math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

[math]diff[a] = -2[/math] и [math]diff[b] = 0[/math] .

[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

[math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math] .

[math]diff[a] = 0[/math] , [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 1[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 0[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

Малый левый поворот:

function rotateLeft(Node a): Node b = a.right a.right = b.left b.left = a корректировка высоты a корректировка высоты b

Большой левый поворот пишется проще:

function bigRotateLeft(Node a): rotateRight(a.right) rotateLeft(a)

Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [math]1[/math] и не может увеличиться.

Все вращения, очевидно, требуют [math]O(1)[/math] операций.

Операции

Добавление вершины

Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math] , то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log) [/math] операций.

Удаление вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её, иначе найдём самую близкую по значению вершину [math]a[/math] , переместим её на место удаляемой вершины и удалим вершину [math]a[/math] . От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным [math]2[/math] или [math]-2[/math] , следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [math] O(h) [/math] операций. Таким образом, требуемое количество действий — [math] O(\log) [/math] .

Поиск вершины, минимум/максимум в дереве, etc.

Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

Слияние двух AVL-деревьев

Дано два дерева [math]T_1[/math] и [math]T_2[/math] , все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math] , [math]h(T_1) \leqslant h(T_2)[/math] .

В дереве [math]T_1[/math] удаляем самую правую вершину, назовём её [math]b[/math] . Высота дерева [math]T_1[/math] может уменьшиться на единицу. В дереве [math]T_2[/math] идём от корня всегда в левое поддерево и, когда высота этого поддерева [math]P[/math] будет равна высоте дерева [math]T_1[/math] , делаем новое дерево [math]S[/math] , корнем [math]S[/math] будет вершина [math]b[/math] , левым поддеревом будет дерево [math]T_1[/math] , а правым дерево [math]P[/math] . Теперь в дереве [math]T_2[/math] у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево [math]S[/math] и запускаем балансировку. Таким образом, дерево [math]T_2[/math] будет результатом слияния двух АВЛ-деревьев.

Дерево [math]T_1[/math] и [math]T_2[/math] до слияния

Дерево [math]T_2[/math] после слияния

Алгоритм разделения AVL-дерева на два

Алгоритм первый

Пусть у нас есть дерево [math]T[/math] . Мы должны разбить его на два дерева [math]T_[/math] и [math]T_[/math] такие, что [math]T_ \leqslant x[/math] и [math]x \lt T_[/math] .

Предположим, что корень нашего дерева [math]\leqslant x[/math] , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_[/math] . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math] ). Если же корень оказался [math]\gt x[/math] , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

Пусть мы пришли в поддерево [math]S[/math] , корень которого [math]\leqslant x[/math] . В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_[/math] . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math] , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL’ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math] ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math] . Теперь нам нужно объединить его с уже построенным ранее [math]T_[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math] ). Для этого мы ищем в дереве [math]T_[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math] , сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_[/math] меньше ключей в [math]T'[/math] , поэтому мы можем это сделать). Теперь в дереве [math]T_[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math] , правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

Если мы пришли в поддерево [math]Q[/math] , корень которого [math]\gt x[/math] , совершаем аналогичные действия: делаем NULL’ами ссылки на корень [math]Q[/math] , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_[/math] .

Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_[/math] . [math]x = 76[/math] .

Рис. 1. Разделение АВЛ-дерева на два.

Корень дерева [math]\leqslant x[/math] , поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_[/math] . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math] , [math]T'[/math] становится [math]T_[/math] . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math] . Следовательно, строим из него и его правого поддерева [math]T_[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math] . Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_[/math] (рис. 3).

Рис. 2. Создание T’.

Рис. 3. Объединение T’ и T1.

Далее действуем по алгоритму и в итоге получаем (рис. 4):

Рис. 4. АВЛ-деревья после разделения.

Данный алгоритм имеет сложность [math]O(\log^ n)[/math] .

Алгоритм второй

Рассмотрим решение, которое имеет сложность [math]O(\log)[/math] .

Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_[/math] и [math]T_[/math] , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math] . Тогда сольем его с уже построенным на тот момент [math]T_[/math] ( [math]T_[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_[/math] и [math]h(T_) \leqslant h(S)[/math] ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math] , высота которого равна высоте [math]T_[/math] . Тогда сделаем новое дерево [math]T'[/math] , корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_[/math] , левым — [math]K[/math] . И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math] . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math] , все аналогично.

Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math] . Ключ больше [math]x[/math] , поэтому эта вершина станет деревом [math]T_[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math] . Он со своим левым поддеревом станет деревом [math]T_[/math] и мы снова поднимемся наверх в узел [math]70[/math] . Он со своим левым поддеревом снова должен отойти в дерево [math]T_[/math] , и так как теперь дерево [math]T_[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)

После мы поднимемся в вершину с ключом [math]80[/math] . Она с правым поддеревом отойдет в дерево [math]T_[/math] (рис. 6).

И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math] , он с левым поддеревом отойдет в дерево [math]T_[/math] , после чего алгоритм завершится.

Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math] . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_[/math] (она может быть не равна [math]1[/math] , если мы придём в [math]x[/math] ). Его мы передаем наверх и вставляем в поддерево высотой [math]H_[/math] . [math]H_ \leqslant H_[/math] , так как разница высот поддеревьев у любой вершины не больше [math]1[/math] , и мы при переходе от [math]H_[/math] к [math]H_[/math] поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за [math]H_ — H_[/math] , получим в итоге дерево высоты не большей, чем [math]H_[/math] . Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за [math]H_ — H_[/math] и так далее. Таким образом мы получим [math](H — H_) + (H_ — H_) + (H_ — H_) + \cdots + (H_ — H_) = H — H_ = O(\log)[/math] .

Итоговая асимптотика алгоритма — [math]O(\log)[/math] .

АВЛ-дерево с O(1) бит в каждом узле

Идея

В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на [math]1[/math] , то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём фактор баланса. Таким образом в каждом узле будет храниться [math]1[/math] — если высота правого поддерева выше левого, [math]0[/math] — если высоты равны, и [math]-1[/math] — если правое поддерево выше левого.

Операции

Операция добавления
Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Пересчитываем баланс данного узла [math]a[/math] . Если он оказался [math]0[/math] , то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева изменилась, и подъём продолжается. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]-1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.

Операция удаления
Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math] , поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева не изменилась, и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

Балансировка

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math] . Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math] , если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math] . На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]

2 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]

3 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]

2 вариант: [math]balance[a] = 1[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

3 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

Примеры

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.