AVLTree.hpp

#pragma once

#ifndef AVLTREE_H
#define AVLTREE_H

/// @brief Óçåë ÀÂË äåðåâà.
struct AVLNode
{
	int Key;
	size_t Height	= 1;
	AVLNode* Left	= nullptr;
	AVLNode* Right	= nullptr;
};

/// @brief ÀÂË äåðåâî.
struct AVLtree
{
	AVLNode* RootNode;
};

/// @brief Èíèöèàëèçàöèÿ äåðåâà.
/// @param tree Äåðåâî.
void InitializeTree(AVLtree*& tree);

/// @brief Ïîëó÷åíèå âûñîòû.
/// @param treeNode Óçåë.
/// @return			Âûñîòà.
size_t GetHeight(AVLNode* treeNode);

/// @brief Ïîëó÷åíèå ôàêòîðà áàëàíñà.
/// âûñîòà ïðàâîãî ìèíóñ âûñîòà ëåâîãî.
/// @param treeNode Óçåë.
/// @return			Ôàêòîð áàëàíñà.
int GetBalanceFactor(AVLNode* treeNode);

/// @brief Âîññòàíîâëåíèå êîððåêòíîãî çíà÷åíèå âûñîòû.
/// @param treeNode Óçåë.
void FixHeight(AVLNode* treeNode);

/// @brief Ëåâûé ïîâîðîò âîêðóã treeNode.
/// @param treeNode Óçåë.
/// @return			Íîâûé Êîðåíü.
AVLNode* RotateLeft(AVLNode* treeNode);

/// @brief Ïðàâûé ïîâîðîò âîêðóã treeNode.
/// @param treeNode Óçåë.
/// @return			Íîâûé Êîðåíü.
AVLNode* RotateRight(AVLNode* treeNode);

/// @brief Áàëàíñèðîâêà 
/// @param treeNode Óçåë.
/// @return			Íîâûé Êîðåíü.
AVLNode* Balance(AVLNode* treeNode);

/// @brief Âñòàâêà.
/// @param treeNode Óçåë. 
/// @param key		Çíà÷åíèå.
/// @return			Íîâûé Êîðåíü.
AVLNode* Insert(AVLNode* treeNode, int key);

/// @brief Ïîèñê ìèíèìóìà.
/// @param treeNode Óçåë.
/// @return			Íîâûé Êîðåíü.
AVLNode* FindMinimal(AVLNode* treeNode);

/// @brief Óäàëåíèå ìèíèìàëüíîãî ýëåìåíòà.
/// @param treeNode Óçåë.
/// @return			Íîâûé Êîðåíü.
AVLNode* RemoveMinimal(AVLNode* treeNode);

/// @brief Óäàëåíèå.
/// @param treeNode Óçåë.
/// @param key		Çíà÷åíèå.
/// @return			Íîâûé Êîðåíü.
AVLNode* Remove(AVLNode* treeNode, int key);

/// @brief Ïîèñê.
/// @param treeNode Óçåë. 
/// @param key		Çíà÷åíèå.
/// @return			Óçåë ñî çíà÷åíèåì key.
AVLNode* Find(AVLNode* treeNode, int key);

/// @brief Óäàëåíèå äåðåâà.
/// @param treeNode Óçåë êîðíÿ.
void FreeTree(AVLNode* treeNode);

#endif //AVLTREE_H