Russian Qt Forum

#ifndef AVLTREE_H
#define AVLTREE_H

///#include "math.h"
#include "QString"

#define LEFTHEAVY -1
#define RIGHTHEAVY 1
#define BALANCED 0

class AVLTree;
class AVLTreeGraph;

class AVLTreeNode {	// Элемент дерева

protected:

    AVLTreeNode* left;		// Левое поддерево
    AVLTreeNode* right;		// Правое поддерево
    signed char Balance;		// Разность высот левого и правого поддеревьев.
    friend class AVLTree;
    friend class AVLTreeGraph;

public:
    int key;				// Ключ
    QString data;

    AVLTreeNode(int Key, QString Data) {	// Конструктор
	key = Key;
	data = Data;
	left = NULL;
	right = NULL;
	Balance = 0;
    }
};

class AVLTree {

protected:

    AVLTreeNode* root;   // Вершина дерева																		// Корень
    int size;		    // Размер дерева																	// Размер дерева (=количество элементов)

    void InsertNode(AVLTreeNode* &cur_root,AVLTreeNode* node, int &reviseBalancefactor);	// Фактическия вставка
    void DeleteTree(AVLTreeNode* &node);														// Удаляет все элементы начиная с текущего
    AVLTreeNode* _find(int key,AVLTreeNode* start_pos);					// Фактический рекурсивный поиск
    void DelNode(AVLTreeNode* &cur_root, int key, int &reviseBalancefactor);			// Удалить по ключу

    void SingleRotateLeft (AVLTreeNode* &p);							// Одиночное вращение налево
    void SingleRotateRight (AVLTreeNode* &p);						// Одиночное вращение направо
    void DoubleRotateLeft (AVLTreeNode* &p);							// Двойное вращение налево
    void DoubleRotateRight (AVLTreeNode* &p);						// Двойное вращение направо
    void UpdateLeftTree (AVLTreeNode* &tree, int &reviseBalanceFactor);			// Балансировать левое дерево
    void UpdateRightTree (AVLTreeNode* &tree, int &reviseBalanceFactor);			// Балансировать правое дерево

    void CopyNode(AVLTreeNode* &Cur, AVLTreeNode* const &Another);			// Копирование дерева
    AVLTreeNode* RemoveLastRight(AVLTreeNode* &cur_root, int &reviseBalancefactor);	// Отсекает самый правый узел и возвращает указатель на него.

    int _getHigh(AVLTreeNode* el);								// Рекурсивное получение высоты дерева

    friend class AVLTreeGraph;

public:

    AVLTree();																					// Конструктор
    AVLTree(int Key, QString FirstEl);																// Еще конструктор
    virtual ~AVLTree();																			// Деструктор

    int getSize();																				// Получить размер дерева

    virtual int getHigh();																		// Получить высоту дерева
    virtual void Insert(int Key, QString Data);														// Добавить элемент
    virtual void Delete(int Key);																// Удаление элемента по ключу
    AVLTreeNode* Find(int Key);																// Поиск
    void clear(); // Очистка дерева
};

// Конструктор ================================================================================================
AVLTree::AVLTree() {
    root = NULL;
    size = 0;
}

// Еще конструктор ================================================================================================
AVLTree::AVLTree(int Key, QString FirstEl) {
    root = new AVLTreeNode(Key, FirstEl);
    root->left = NULL;
    root->right = NULL;
    root->Balance = BALANCED;
    size = 1;
}

// Деструктор ================================================================================================
AVLTree::~AVLTree() {
    DeleteTree(root);
    root = NULL;
    size = 0;
}

// Очистка дерева ================================================================================================
void AVLTree::clear() {
    DeleteTree(root);
}

// Получение размера дерева ========================================================================================
int AVLTree::getSize() {
    return size;
}


// Добавить элемент ========================================================================================
void AVLTree::Insert(int Key, QString Data) {
    if (root == NULL) {
	root = new AVLTreeNode(Key, Data);
	root->Balance = BALANCED;
	root->left = NULL;
	root->right = NULL;
	size = 1;
	return;
    }

    AVLTreeNode* cur_root = root, *new_node = new AVLTreeNode(Key, Data);

    new_node->left = NULL;
    new_node->right = NULL;
    new_node->Balance = BALANCED;

    int reviseBalancefactor = 0; // флаг, используемый функцией AVLInsert для перебалансировки узлов

    InsertNode(cur_root, new_node, reviseBalancefactor); // Фактическая вставка

    root = cur_root;
    size++;
}

// Получаение высоты дерева ========================================================================================
int AVLTree::getHigh() {
    return _getHigh(root);
}

// Получаение высоты дерева ========================================================================================
int AVLTree::_getHigh(AVLTreeNode* el) {
    if (el == NULL)
	return 0;
    return 1 + std::max(_getHigh(el->left), _getHigh(el->right));
}

// Фактичекое добавление элемента =================================================================================================
void AVLTree::InsertNode(AVLTreeNode* &cur_root, AVLTreeNode* new_node, int &reviseBalancefactor) {
    int rebalanceCurrNode; // флаг "Показатель сбалансированности был изменен"

    // встретилось пустое поддерево. Пора вставлять новый узел
    if (cur_root == NULL) {
	cur_root = new_node;
	reviseBalancefactor = 1;
    }
    else {
	if(new_node->key < cur_root->key) { // Спускаться по левому поддереву, если новый узел меньше текущего
	    InsertNode(cur_root->left, new_node, rebalanceCurrNode);
	    if(rebalanceCurrNode) {	// проверить, нужно ли корректировать balanceFactor
		if (cur_root->Balance == LEFTHEAVY)	//мы вставляем в левое поддерево, да еще в и лево перевешивает, следовательно однозначно нужно подправить дерево.
		    UpdateLeftTree(cur_root, reviseBalancefactor);
		else
		    if(cur_root->Balance == RIGHTHEAVY) { // вставка слева от узла, перевешивающего вправо.
		    cur_root->Balance = BALANCED;
		    reviseBalancefactor = 0;
		}
		else {
		    cur_root->Balance = LEFTHEAVY;
		    reviseBalancefactor = 1;
		}
	    }
	    else
		reviseBalancefactor = 0;
	}
	else if (new_node->key > cur_root->key) { // иначе рекурсивно спускаться по правому поддереву
	    InsertNode(cur_root->right, new_node, rebalanceCurrNode);
	    if(rebalanceCurrNode) { // проверить, нужно ли корректировать balanceFactor
		if (cur_root->Balance == RIGHTHEAVY)//мы вставляем в правое поддерево, да еще в и право перевешивает, следовательно однозначно нужно подправить дерево.
		    UpdateRightTree(cur_root, reviseBalancefactor);
		else
		    if(cur_root->Balance==LEFTHEAVY) { //вставка справа от узла,перевешивающего влево=> узел станет сбалансированным
		    cur_root->Balance = BALANCED;
		    reviseBalancefactor = 0;
		}
		else {
		    cur_root->Balance = RIGHTHEAVY;
		    reviseBalancefactor = 1;
		}
	    }
	    else
		reviseBalancefactor = 0;
	}
    }
}

// Удаление элемента по ключу ========================================================================================
void AVLTree::Delete(int Key) {
    int reviseBalancefactor = 0;
    DelNode(root, Key, reviseBalancefactor);
}

// Поиск элемента ========================================================================================
AVLTreeNode* AVLTree::Find(int Key) {
    return _find(Key, root);
}

// Одиночное вращение налево ==============================================================================
void AVLTree::SingleRotateLeft (AVLTreeNode* &p) {
    AVLTreeNode *rc = p->right;
    p->Balance = BALANCED;
    rc->Balance = BALANCED;
    p->right = rc->left;
    rc->left = p;
    p = rc;
}

// Одиночное вращение направо ==============================================================================
void AVLTree::SingleRotateRight (AVLTreeNode* &p) {
    AVLTreeNode *lc;
    lc = p->left;
    p->Balance = BALANCED;
    lc->Balance = BALANCED;
    p->left = lc->right;
    lc->right = p;
    p = lc;
}

// Двойное вращение налево ==============================================================================
void AVLTree::DoubleRotateLeft (AVLTreeNode* &p) {
    AVLTreeNode *rc = p->right, *np = rc->left;

    if (np == NULL) return;

    if(np->Balance == LEFTHEAVY) {
	p->Balance = BALANCED;
	rc->Balance = RIGHTHEAVY;
    }
    else {
	p->Balance = LEFTHEAVY;
	rc->Balance = BALANCED;
    }

    np->Balance = BALANCED;
    rc->left = np->right;
    np->right = rc;
    p->right = np->left;
    np->left = p;
    p = np;
}

// Двойное вращение направо ==============================================================================
void AVLTree::DoubleRotateRight (AVLTreeNode* &p) {
    AVLTreeNode *lc = p->left, *np = lc->right;

    if (np->Balance == RIGHTHEAVY) {
	p->Balance = BALANCED;
	lc->Balance = LEFTHEAVY;
    }
    else {
	p->Balance = RIGHTHEAVY;
	lc->Balance = BALANCED;
    }

    np->Balance = BALANCED;
    lc->right = np->left;
    np->left = lc;
    p->left = np->right;
    np->right = p;
    p = np;
}

// Балансировка левого дерева ==============================================================================
void AVLTree::UpdateLeftTree (AVLTreeNode* &tree, int &reviseBalanceFactor) {
    AVLTreeNode *lc;
    lc = tree->left;

    if (lc->Balance == LEFTHEAVY) {	// перевешивает левое поддерево?
	SingleRotateRight(tree);	// однократный поворот
	reviseBalanceFactor = 0;
    }
    else {
	if (lc->Balance == BALANCED) {
	    DoubleRotateRight(tree);	// выполнить двойной поворот
	    tree->Balance = LEFTHEAVY;
	    lc->Balance = LEFTHEAVY;
	    reviseBalanceFactor = 1;
	}
	else {
	    DoubleRotateRight(tree);	// выполнить двойной поворот
	    reviseBalanceFactor = 0;	// теперь корень уравновешен
	}
    }
}

// Балансировка правого дерева ==============================================================================
void AVLTree::UpdateRightTree (AVLTreeNode* &tree, int &reviseBalanceFactor)
{
    AVLTreeNode *rc;
    rc=tree->right;

    if (rc->Balance == RIGHTHEAVY) { //перевешивает ли правое поддерево?
	SingleRotateLeft(tree);
	reviseBalanceFactor=0;
    } else {
	if (rc->Balance == BALANCED) {
	    DoubleRotateLeft(tree);
	    tree->Balance = RIGHTHEAVY;//при двойном попороте, при условии, что правый сын сбалансирован перекосы становятся вправо.
	    rc->Balance = RIGHTHEAVY;
	    reviseBalanceFactor = 1;
	}
	else {
	    DoubleRotateLeft(tree);
	    reviseBalanceFactor = 0;
	}
    }
}

// Удалить начиная с текущего ==============================================================================
void AVLTree::DeleteTree(AVLTreeNode* &node) {
    if (node == NULL)
	return;

    if (node->left != NULL)
	DeleteTree(node->left);

    if (node->right != NULL)
	DeleteTree(node->right);

    delete[] node;

    node = NULL;
    size = 0;
}

// Рекурсивный поиск =======================================================================================
AVLTreeNode* AVLTree::_find(int key, AVLTreeNode* start_pos) {
    if (start_pos==0) {
	//throw err("There is no such element in tree");
	return NULL;
    }

    if (start_pos->key == key)
	return start_pos;

    if(key < start_pos->key)
	return _find(key, start_pos->left);
    else
	return _find(key, start_pos->right);
}

// Фактическое удаление по ключу =======================================================================
void AVLTree::DelNode(AVLTreeNode* &cur_root, int key, int &reviseBalancefactor) {

    if (cur_root == 0) {
	reviseBalancefactor = 0;
	return;
    }

    int rebalanceCurNode;
    if (key < cur_root->key) {
	DelNode(cur_root->left, key, rebalanceCurNode);

	if(rebalanceCurNode) {
	    if(cur_root->Balance == RIGHTHEAVY) {
		UpdateRightTree(cur_root,reviseBalancefactor);
		reviseBalancefactor = !reviseBalancefactor;
	    }
	    else if(cur_root->Balance == BALANCED) {
		cur_root->Balance = RIGHTHEAVY;
		reviseBalancefactor = 0;
	    }
	    else {
		cur_root->Balance = BALANCED;
		reviseBalancefactor = 1;
	    }
	}
	else reviseBalancefactor = 0;
    }
    else if (key > cur_root->key) {

	DelNode(cur_root->right,key,rebalanceCurNode);

	if (rebalanceCurNode) {
	    if (cur_root->Balance == LEFTHEAVY) {
		UpdateLeftTree(cur_root, reviseBalancefactor);
		reviseBalancefactor = !reviseBalancefactor;
	    }
	    else if (cur_root->Balance == BALANCED) {
		cur_root->Balance = LEFTHEAVY;
		reviseBalancefactor = 0;
	    }
	    else {
		cur_root->Balance = BALANCED;
		reviseBalancefactor = 1;
	    }
	}
	else
	    reviseBalancefactor = 0;
    }
    else {
	--size;
	if (cur_root->left == NULL) {
	    if (cur_root->right == NULL) {
		delete cur_root;
		cur_root = NULL;
	    }
	    else {
		AVLTreeNode* temp = cur_root->right;
		delete cur_root;
		cur_root = temp;
	    }
	    reviseBalancefactor = 1;
	}
	else {
	    AVLTreeNode* temp = RemoveLastRight(cur_root->left, reviseBalancefactor);
	    cur_root->key = temp->key;
	    cur_root->data = temp->data;
	    delete temp;

	    if (reviseBalancefactor) {
		if (cur_root->Balance == LEFTHEAVY) {
		    cur_root->Balance = BALANCED;
		    reviseBalancefactor = 1;
		}
		else if (cur_root->Balance == BALANCED) {
		    cur_root->Balance = RIGHTHEAVY;
		    reviseBalancefactor = 0;
		}
		else {
		    UpdateRightTree(cur_root, reviseBalancefactor);
		    reviseBalancefactor = !reviseBalancefactor;
		}
	    }
	}
    }
}

// Копирование дерева =======================================================================
void AVLTree::CopyNode(AVLTreeNode* &Cur, AVLTreeNode* const &Another) {
    if (Cur == NULL)
	Cur = new AVLTreeNode(Another->key, Another->data);
    else {
	Cur->key=Another->key;
	Cur->data=Another->data;
    }

    Cur->Balance = Another->Balance;

    if (Another->left != NULL)
	CopyNode(Cur->left, Another->left);
    if (Another->right != NULL)
	CopyNode(Cur->right, Another->right);
}

// У заданного дерева отсекает самый правый узел и возвращает указатель на него ============================================
AVLTreeNode* AVLTree::RemoveLastRight(AVLTreeNode* &cur_root, int &reviseBalancefactor) {
    AVLTreeNode* temp = cur_root;
    if (cur_root->right == NULL) {
	if (cur_root->left == NULL) {
	    cur_root = NULL;
	    reviseBalancefactor = 1;
	    return temp;
	}
	else {
	    cur_root = temp->left;
	    reviseBalancefactor = 1;
	    return temp;
	}
    }
    else {
	int rebalanceCurNode;
	temp = RemoveLastRight(cur_root->right, rebalanceCurNode);
	if(rebalanceCurNode) {
	    if (cur_root->Balance == RIGHTHEAVY) {
		cur_root->Balance = BALANCED;
		reviseBalancefactor = 1;
	    }
	    else if(cur_root->Balance == LEFTHEAVY)
		UpdateLeftTree(cur_root, reviseBalancefactor);
	    else {
		cur_root->Balance = LEFTHEAVY;
		reviseBalancefactor = 0;
	    }
	}
	else
	    reviseBalancefactor = 0;
	return temp;
    }
}

#endif // AVLTREE_HPP