AVL деревья - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Понятие AVL дерева

image

АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log2(n + 1) до 1.44 log2(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.

Структура узла

struct Node {
	T data;
	int height;
	Node* left;
	Node* right;
	Node(T _data) {
		data = _data;
		height = 1;
		left = nullptr;
		right = nullptr;
	}
};

Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.

Определим три вспомогательные функции, связанные с высотой. Первая является оберткой для поля height, она может работать и с нулевыми указателями (с пустыми деревьями):

int Height(Node* node)
{
	return node ? node->height : 0;
}

Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):

int Bfactor(Node* node)
{
	return  Height(node->right) - Height(node->left);
}

Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):

void commitHeight(Node* node)
{
	if (!node)
	{
		return;
	}
	int left = Height(node->left);
	int right = Height(node->right);
	node->height = (left > right ? left : right) + 1;
}

Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).

Хранение инфы про баланс

Можно делать так:

  • хранить в каждом узле высоту
  • хранить в каждом узле его баланс-фактор
  • красить узлы/связи для гарантии балансировки( как в кч дереве)

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

В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает расбалансировка поддерева. Для выправления ситуации применяются хорошо нам известные повороты вокруг тех или иных узлов дерева. Напомню, что простой поворот вправо (влево) производит следующую трансформацию дерева: image

Код реализующий правый поворот выглядит так:

void RightRotation(Node*& p)
{

	Node* q = p->left;
	p->left = q->right;
	q->right = p;
	commitHeight(p);
	commitHeight(q);
	p = q;
}

Левый поворот является симметричной копией правого:

void LeftRotation(Node*& p)
{
	Node* q = p->right;
	p->right = q->left;
	q->left = p;
	commitHeight(p);
	commitHeight(q);
	p = q;
}

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.

image

Анализ возможных случаев в рамках данной ситуации показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).

image

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

image

Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:

void balance(Node*& p)
{
	commitHeight(p);
	int bfactor = Bfactor(p);
	if (bfactor == 2)
	{
		if (Bfactor(p->right) < 0)
			RightRotation(p->right);
		LeftRotation(p);
	}

	if (bfactor == -2)
	{
		if (Bfactor(p->left) > 0)
			LeftRotation(p->left);
		RightRotation(p);
	}
}

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

Вставка элементов

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

private:
void Insert(Node*& node, T elem) {
	if (node == nullptr) {
		node = new Node(elem);
	}
	else if (elem < node->data) {
		Insert(node->left, elem);
	}
	else {
		Insert(node->right, elem);
	}
	balance(node);
}
public:
void Insert(T elem) {
	Insert(root, elem);
}

Удаление ключей

С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в левом поддереве находим самый большой ключ max, и заменяем узел p на узел max.

Идея вот отсюда

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

void remove(Node*& node) {
	if (node) {
		if (node->left && node->right) {
			T succ = succesor(node->left);
			node->data = succ;
		}
		else if (node->left && !node->right) {
			Node* temp = node;
			node = node->left;
			delete temp;
			temp = nullptr;
		}
		else if (!node->left && node->right) {
			Node* temp = node;
			node = node->right;
			delete temp;
			temp = nullptr;
		}
		else if (!node->left && !node->right) {
			delete node;
			node = nullptr;
			return;
		}
		balance(node);
	}
}

Не забываем сбалансировать дерево после внесенный изменений.

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

⚠️ **GitHub.com Fallback** ⚠️