RBTree.hpp

#pragma once

#ifndef RBTREE_H
#define RBTREE_H

/// @brief Öâåò óçëà.
enum class Color 
{
	Red,
	Black,
	DoubleBlack
};

/// @brief Óçåë Êðàñíî-÷åðíîãî äåðåâà.
struct Node
{
	int Data;
	Color Color		= Color::Red;
	Node* Left		= nullptr;
	Node* Right		= nullptr;
	Node* Parent	= nullptr;
};

/// @brief Êðàñíî-÷åðíîå äåðåâî.
struct RBTree
{
	Node* Root = nullptr;
};

/// @brief Ëåâûé ïîâîðîò âîêðóã node.
/// @param root Êîðåíü
/// @param node Óçåë.
void RotateLeft(Node*& root, Node*& node);

/// @brief Ïðàâûé ïîâîðîò âîêðóã node.
/// @param root Êîðåíü
/// @param node Óçåë.
void RotateRight(Node*& root, Node*& node);

/// @brief Áàëàíñèðîâêà âñòàâêè.
/// @param root Êîðåíü.
/// @param node Âñòàâëÿåìûé óçåë.
void FixInsertRBTree(Node*& root, Node*& node);

/// @brief Áàëàíñèðîâêà óäàëåíèÿ.
/// @param root Êîðåíü.
/// @param node Óäàëÿåìûé óçåë.
void FixDeleteRBTree(Node*& root, Node*& node);

/// @brief Ïîëó÷èòü öâåò.
/// @param node Óçåë.
/// @return		Öâåò.
Color GetColor(Node* node);

/// @brief Óñòàíîâèòü Öâåò.
/// @param node		Óçåë.
/// @param color	Öâåò.
void SetColor(Node*& node, Color color);

/// @brief Âñòàâêà çíà÷åíèÿ.
/// @param root		Êîðåíü
/// @param value	Çíà÷åíèå.
void InsertValue(Node*& root, int value);

/// @brief Âñòàâêà.
/// @param root Êîðåíü.
/// @param node Óçåë.
/// @return		Êîðåíü.
Node* InsertNode(Node*& root, Node*& node);

/// @brief Óäàëåíèå.
/// @param root Êîðåíü.
/// @param data Çíà÷åíèå.
/// @return		Êîðåíü.
Node* DeleteNode(Node*& root, int data);

/// @brief Óäàëåíèå ïî çíà÷åíèþ.
/// @param root Êîðåíü
/// @param data Çíà÷åíèå.
void DeleteValue(Node*& root, int data);

/// @brief Ìèíèìàëüíîå çíà÷åíèå.
/// @param node Óçåë.
/// @return		Óçåë ñ ìèíèìàëüíûì çíà÷åíèåì.
Node* MinValueNode(Node*& node);

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

/// @brief Óäàëåíèå äåðåâà.
/// @param node Óçåë.
void FreeTree(Node* node);

#endif //RBTREE_H