Fivt_Intro_3/task-3_1/26.11.2017 (TL)

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>

template <typename Data, class T>
struct TreeNode {
	Data key;
	T* l;
	T* r;
	TreeNode(Data _key, T* _l, T* _r) :
			key(_key),
			l(_l),
			r(_r)
	{
	}
};

struct AVLTreeNode : public TreeNode<int, AVLTreeNode> {
	size_t height;
	AVLTreeNode(const int _key, AVLTreeNode* _l, AVLTreeNode* _r) :
			TreeNode(_key,_l,_r),
			height(1)
	{
	}
	int HeightDiff() const;
	void CorrectHeight();
};


size_t Height(AVLTreeNode* p) {
	if (p == nullptr) {
		return 0;
	} else {
		return p->height;
	}
}


int AVLTreeNode::HeightDiff() const {
	int right_height = Height(this->r);
	int left_height = Height(this->l);
	return (right_height - left_height);
}


size_t RightOffspringsNumber(AVLTreeNode* node) {
	size_t node_offspring_number = 0;
	if (node == nullptr) {
		return 0;
	} else {
		++node_offspring_number;
	}
	if (node->l != nullptr) {
		node_offspring_number += RightOffspringsNumber(node->l);
	}
	if (node->r != nullptr) {
		node_offspring_number += RightOffspringsNumber(node->r);
	}
	return node_offspring_number;
}


void AVLTreeNode::CorrectHeight() {
	size_t height_left = Height(this->l);
	size_t height_right = Height(this->r);
	this->height = ((height_left > height_right) ? height_left : height_right ) +1;
}


template <typename Data, class T>
class Tree {
private:
	T* root;
public:
	virtual T* Add(T* node, int key) = 0;
	explicit Tree(Data root_key);
	T* GetRoot() const;
	T*& SetRoot();
	~Tree();
};


template <typename Data, class T>
Tree<Data,T>::Tree(Data root_key) {
	root = new T(root_key, nullptr, nullptr);
}


template <typename Data, class T>
T *Tree<Data, T>::GetRoot() const {
	return  root;
}


template <typename Data, class T>
Tree<Data,T>::~Tree() {
	std::queue<T*> queue;
	queue.push(GetRoot());
	while (!queue.empty()) {
		T* node_from_queue = queue.front();
		queue.pop();
		if (node_from_queue->l != nullptr) {
			queue.push(node_from_queue->l);
		}
		if (node_from_queue->r != nullptr) {
			queue.push(node_from_queue->r);
		}
		delete node_from_queue;
	}
}


template <typename Data, class T>
T*& Tree<Data,T>::SetRoot() {
	return root;
}


class AVLTree : public Tree<int,AVLTreeNode> {
private:
	AVLTreeNode* SmallLeftRotation(AVLTreeNode* node);
	AVLTreeNode* SmallRightRotation(AVLTreeNode* node);
	AVLTreeNode* Balance(AVLTreeNode* node);
	AVLTreeNode* RemoveMin(AVLTreeNode* root);
	AVLTreeNode* FindMin(AVLTreeNode* root);
public:
	explicit AVLTree(int root_key);
	AVLTreeNode* Add(AVLTreeNode* node, int key) override;
	AVLTreeNode* Delete(AVLTreeNode* node, int key);
	void RemoveByPosition(int position);
	size_t GetArrayPosition(int key);
};

AVLTree::AVLTree(int root_key) :
	Tree(root_key)
{
}


AVLTreeNode *AVLTree::SmallLeftRotation(AVLTreeNode *node) {
	AVLTreeNode* right_child = node->r;
	node->r = right_child->l;
	right_child->l = node;
	node->CorrectHeight();
	right_child->CorrectHeight();
	return right_child;
}


AVLTreeNode* AVLTree::SmallRightRotation(AVLTreeNode *node) {
	AVLTreeNode* left_child = node->l;
	node->l = left_child->r;
	left_child->r = node;
	node->CorrectHeight();
	left_child->CorrectHeight();
	return left_child;
}


AVLTreeNode* AVLTree::Balance(AVLTreeNode* node) {

	node->CorrectHeight();

	if (node->HeightDiff() == 2) {
		if (node->r->HeightDiff() < 0) {
			node->r = SmallRightRotation(node->r);
		}
		return SmallLeftRotation(node);
	}

	if (node->HeightDiff() == -2) {
		if (node->l->HeightDiff() > 0) {
			node->l = SmallLeftRotation(node->l);
		}
		return SmallRightRotation(node);
	}

	return node;
}


AVLTreeNode* AVLTree::Add(AVLTreeNode* node, const int key) {
	if (node == nullptr) {
		return new AVLTreeNode(key, nullptr, nullptr);
	}
	if (key < node->key) {
		node->l = Add(node->l, key);
	}
	else {
		node->r = Add(node->r, key);
	}
	return Balance(node);
}


AVLTreeNode* AVLTree::RemoveMin(AVLTreeNode *root) {
	if( root->l == nullptr ) {
		return root->r;
	}
	root->l = RemoveMin(root->l);
	root->CorrectHeight();
	return  root;
}


AVLTreeNode* AVLTree::FindMin(AVLTreeNode *root) { // конец левой ветки
	if ( root->l == nullptr) {
		return root;
	} else {
		return FindMin(root->l);
	}
}

AVLTreeNode* AVLTree::Delete(AVLTreeNode* node, int key) { //удаляет этот нод c key
	if (node == nullptr) {
		return nullptr;
	}
	else if (key < node->key) {
		node->l = Delete(node->l, key);
	}
	else if (key > node->key) {
		node->r = Delete(node->r, key);
	}
	else {
		AVLTreeNode* left_offspring = node->l;
		AVLTreeNode* right_offspring = node->r;

		delete node;

		if (right_offspring == nullptr) {
			return left_offspring;
		}

		AVLTreeNode* min_in_right_subtree = FindMin(right_offspring); // находим узел с наименьшим ключом в правом поддереве
		min_in_right_subtree->r = RemoveMin(right_offspring); // удаление мин. ключа
		min_in_right_subtree->l = left_offspring;

		return Balance(min_in_right_subtree);
	}
	return Balance(node);
}


void AVLTree::RemoveByPosition(int position) {
	AVLTreeNode* current_node = GetRoot();
	while (current_node != nullptr) {
		if (GetArrayPosition(current_node->key) == position) {
			this->SetRoot() = Delete(GetRoot(), current_node->key); // нашел нужный ключ
			return;
		}
		else {
			if (GetArrayPosition(current_node->key) < position) {
				current_node = current_node->l;
			} else {
				current_node = current_node->r;
			}
		}
	}
	std::cerr<<" Can't find this position ";
	exit(1);
}


size_t AVLTree::GetArrayPosition(const int key) {

	AVLTreeNode* current_node = GetRoot();
	size_t  position = 0;
	while (current_node->key != key) {
		if (key < current_node->key) {
			position += RightOffspringsNumber(current_node->r) + 1;
			current_node = current_node->l;
		} else if (key > current_node->key) {
			current_node = current_node->r;
		}
		if (current_node == nullptr) {
			std::cerr<<" Can't find key in AVLTree ";
			exit(1);
		}
	}
	if (current_node == GetRoot()) {
		return RightOffspringsNumber(current_node->r);
	} else {
		return  position + RightOffspringsNumber(current_node->r);
	}
}


int main() {


	int n;
	std::cin>>n;

	int instruction, value;
	std::cin>>instruction>>value;
	if (instruction != 1) {
		std::cerr<<"Can't create AVLTree";
		exit(1);
	}
	AVLTree avl_tree(value);
	std::vector<int> result;
	result.push_back(avl_tree.GetArrayPosition(value));

	for (int i = 1; i < n; ++i) {
		std::cin>>instruction>>value;
		if (instruction == 1) {
			avl_tree.SetRoot() = avl_tree.Add(avl_tree.GetRoot(), value);
			result.push_back(avl_tree.GetArrayPosition(value));
		}
		else if (instruction == 2){
			avl_tree.RemoveByPosition(value);
		}
		else {
			std::cerr<<"Undefined instruction";
			exit(1);
		}
	}

	for(auto i: result) {
		std::cout<<i<<'\n';
	}


	return  0;
}