Фундаментальные структуры данных
АВЛ-деревья
Метод «преобразуй и властвуй»
АВЛ-деревья
АВЛ-деревья были открыты в 1962 г. двумя советскими математиками – Г.М. Адельсоном-Вельским и Е.М. Ландисом. АВЛ-деревом (AVL-TREE) называется такое бинарное дерево поиска, у которого высота поддеревьев для каждого узла различается не более чем на 1. Максимальная высота АВЛ-дерева с n узлами не превосходит 1,4405*log2(n+1)-0,3277, т.е. затраты на поиск не превосходят 1,45*O(log2n). АВЛ-дерево относится к классу сбалансированных деревьев. При включении и удалении узлов необходимо поддерживать сбалансированность дерева в целом.
АВЛ-деревья
В каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла h). Его значение равно разности высот левого и правого поддеревьев. Если вставка нового узла делает АВЛ-дерево несбалансированным, оно преобразуется при помощи поворота. Поворот в АВЛ-дереве представляет собой локальное преобразование поддерева, корень которого имеет показатель сбалансированности, равный +2 или -2; если таких узлов несколько, мы поворачиваем дерево с несбалансированным корнем, который наиболее близок к вновь вставленному листу.
АВЛ-деревья
Всего имеется только четыре типа поворотов, причем два из них представляют собой зеркальное отражение двух других. Одиночный правый поворот или R-поворот. Он выполняется после вставки нового ключа в левое поддерево левого дочернего узла корня, который перед вставкой имел показатель сбалансированности +1. Одиночный левый поворот или L-поворот. Он выполняется после вставки нового ключа в правое поддерево правого дочернего узла корня, который перед вставкой имел показатель сбалансированности -1.
АВЛ-деревья
R
C
C
T3
R
T1
T1
T2
T2
T3
АВЛ-деревья
Двойной лево-правый поворот или LR-поворот. Он представляет собой объединение двух поворотов: выполняется L-поворот левого поддерева корня r, за которым следует R-поворот нового поддерева, корнем которого является r. Он выполняется после вставки нового ключа в правое поддерево левого дочернего узла дерева, корень который перед вставкой имел показатель сбалансированности +1.
АВЛ-деревья
R
G
C
T4
C
R
G
T1
T1
T2
T4
T3
T2
T3
АВЛ-деревья
Двойной право-левый поворот или RL-поворот. Он представляет собой зеркальное отражение двойного LR-поворота. Он представляет собой объединение двух поворотов: выполняется R-поворот правого поддерева корня r, за которым следует L-поворот нового поддерева, корнем которого является r. Он выполняется после вставки нового ключа в левое поддерево правого дочернего узла корня, который перед вставкой имел показатель сбалансированности -1.
АВЛ-деревья
В каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла h). Его значение равно разности высот левого и правого поддеревьев. struct node { int DATA; int bal; struct node *LPTR,*RPTR; }; int h = 0;
/*Вставка узла в AVL-дерево*/ int insertAVL(int key, struct node **t, int *h) { struct node *t1,*t2,*T; int ret = 0; T = *t; if ( T == NULL) // Если дерево пустое { T=(struct node*) malloc(sizeof(struct node)); T->DATA = key; T->bal = 0; *h=1; T->LPTR = T->RPTR = NULL; }
else // Если дерево не пустое if (key < T->DATA) { insertAVL(key, &(T->LPTR), h); // В левое поддерево if (*h != 0) { switch (T->bal) { case 1: T->bal = 0; *h = 0; break; case 0: T->bal = -1; break; case -1: // балансировка { t1 = T->LPTR; if (t1->bal == -1) // L-поворот { T->LPTR = t1->RPTR; t1->RPTR = T; T->bal = 0; T = t1; }
else // LR-поворот { t2 = t1->RPTR; t1->RPTR = t2->LPTR; t2->LPTR = t1; T->LPTR = t2->RPTR; t2->RPTR = T; if (t2->bal == -1) T->bal = 1; else T->bal = 0; if (t2->bal == 1) t1->bal = -1; else t1->bal = 0; T = t2; } T->bal = 0; *h = 0; } } } }
else if (key > T->DATA) // В правое поддерево { insertAVL(key, &(T->RPTR), h); if (*h == 1) switch (T->bal) { case -1: T->bal = 0; *h = 0; break; case 0: T->bal = 1; break; case 1: // балансировка { t1=T->RPTR; if (t1->bal == 1) // R-поворот { T->RPTR = t1->LPTR; t1->LPTR = T; T->bal = 0; T = t1; }
else // RL-поворот { t2 = t1->LPTR; t1->LPTR = t2->RPTR; t2->RPTR = t1; T->RPTR = t2->LPTR; t2->LPTR = T; if (t2->bal == 1) T->bal = -1; else T->bal = 0; if (t2->bal == -1) t1->bal = 1; else t1->bal = 0; T = t2; } T->bal = 0; *h = 0; } } }
else { gotoxy(1,3); setcolor(RED); outtextxy(10,40,"The key is already in the Tree"); ret=-1; getch(); } *t = T; return ret; }
АВЛ-деревья
Итак, операции поиска и вставки в худшем случае выполняются за время Θ(log2n). Получить точную формулу для средней высоты AVL-дерева, построенного для случайного набора ключей, достаточно сложно, но из многочисленных экспериментом известно, что средняя высота AVL-дерева составляет примерно 1.011*log2n+0.1, за исключением малых значений n. Таким образом, поиск в AVL-дереве требует в среднем того же количества сравнений, что и поиск в отсортированном массиве при бинарном поиске.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
