#pragma once
#include <iostream>
#include <algorithm>
using namespace std;

template<class T>
class BinarySearchTree
{
private:
	struct Node {
		T key_;
		Node* left_;
		Node* right_;
		Node* p_;
		int size_;
		Node(const T& key, Node *left = NULL, Node *right = NULL, Node *p = NULL, int index = 0) :
			key_(key), left_(left), right_(right), p_(p), size_(index) {  }
	};

	Node* root_;

public:

	// Êîíñòðóêòîð "ïî óìîë÷àíèþ" ñîçäàåò ïóñòîå äåðåâî
	BinarySearchTree() : root_(NULL) {}

	// Äåñòðóêòîð îñâîáîæäàåò ïàìÿòü, çàíÿòóþ óçëàìè äåðåâà
	~BinarySearchTree() { deleteSubtree(root_); }

	// Ïå÷àòü ñòðîêîâîãî èçîáðàæåíèÿ äåðåâà â âûõîäíîé ïîòîê out
	void print(ostream & out) const { printNode(out, root_); out << endl; }

	// Ôóíêöèÿ ïîèñêà ïî êëþ÷ó â áèíàðíîì äåðåâå ïîèñêà
	bool iterativeSearch(const T & key)  const {
		return (iterativeSearchNode(key) != NULL);
	}

	// Âñòàâêà íîâîãî ýëåìåíòà â äåðåâî, íå íàðóøàþùàÿ ïîðÿäêà
	// ýëåìåíòîâ. Âñòàâêà ïðîèçâîäèòñÿ â ëèñò äåðåâà
	void insert(const T& key) {
		if (root_ == NULL)
			root_ = new Node(key);
		else
			//insert(key, root_);
			iterativeInsert(key);
	}

	// Óäàëåíèå ýëåìåíòà èç äåðåâà, íå íàðóøàþùåå ïîðÿäêà ýëåìåíòîâ
	void deleteKey(const T & key) {
		if (iterativeSearch(key))
			deleteKey(root_, key);
	}

	// Îïðåäåëåíèå êîëè÷åñòâà óçëîâ äåðåâà
	int count() const {
		return countSubTree(this->root_);
	}
	// Îïðåäåëåíèå âûñîòû äåðåâà
	int height() const {
		return heightSubTree(this->root_);
	}

	T foundIndex(int index) const {
		return foundIndex(index, root_);
	}

	T foundIndex(int index, Node* node) const {
		int x = index;
		if (node->right_ != NULL)
			x += (node->right_->size_ + 1);
		if (x == node->size_) {
			return node->key_;
		}
		else {
			if (x < node->size_) {
				if (node->left_ == NULL) {
					cout << "Wrong Index\n";
				}
				else {
					return foundIndex(index, node->left_);
				}
			}
			else {
				if (node->right_ == NULL) {
					cout << "Wrong Index\n";
				}
				else {
					if (node->left_ != NULL) {
						index -= (node->left_->size_ + 2);
					}
					else {
						index -= 1;
					}
					return foundIndex(index, node->right_);
				}
			}
		}
	}

private:
	// Ôóíêöèÿ ïîèñêà àäðåñà óçëà ïî êëþ÷ó â áèíàðíîì äåðåâå ïîèñêà
	Node * iterativeSearchNode(const T & key) const {
		Node* node = root_;
		while (node != NULL && node->key_ != key) {
			if (key < node->key_)
				node = node->left_;
			if (key > node->key_)
				node = node->right_;
		}
		return node;
	}

	//
	// Ðåêóðñèâíûå ôóíêöèè, ïðåäñòàâëÿþùèå
	// ðåêóðñèâíûå òåëà îñíîâíûõ èíòåðôåéñíûõ ìåòîäîâ
	//

	// Ðåêóðñèâíàÿ ôóíêöèÿ äëÿ îñâîáîæäåíèÿ ïàìÿòè
	void deleteSubtree(Node *node) {
		if (node == NULL)
			return;
		if (node->left_ != NULL) {
			node->size_ -= (node->left_->size_ + 1);
			deleteSubtree(node->left_);
			node->left_ = NULL;
		}
		if (node->right_ != NULL) {
			node->size_ -= (node->right_->size_ + 1);
			deleteSubtree(node->right_);
			node->right_ = NULL;
		}
		delete node;
	}

	// Ðåêóðñèâíàÿ ôóíêöèÿ îïðåäåëåíèÿ êîëè÷åñòâà óçëîâ äåðåâà
	int countSubTree(Node *node) const {
		if (node == NULL)
			return 0;
		return (1 + countSubTree(node->left_) +
			countSubTree(node->right_));
	}

	// Ðåêóðñèâíàÿ ôóíêöèÿ îïðåäåëåíèÿ âûñîòû äåðåâà
	int heightSubTree(Node *node) const {
		if (node == NULL)return 0;
		return 1 + max(heightSubTree(node->left_), heightSubTree(node->right_));
	}

	// Ðåêóðñèâíàÿ ôóíêöèÿ äëÿ âûâîäà èçîáðàæåíèÿ äåðåâà â âûõîäíîé ïîòîê
	void printNode(ostream & out, Node *root) const {
		// Èçîáðàæåíèå äåðåâà çàêëþ÷àåòñÿ â êðóãëûå ñêîáêè.
		out << '(';
		if (root) {
			// Äëÿ óçëîâ äåðåâà äîëæíà áûòü îïðåäåëåíà (èëè ïåðåîïðåäåëåíà)
			// îïåðàöèÿ âûâîäà â âûõîäíîé ïîòîê <<
			out << root->key_;
			printNode(out, root->left_);
			printNode(out, root->right_);
		}
		out << ')';
	}

	// Ðåêóðñèâíàÿ ôóíêöèÿ äëÿ îðãàíèçàöèè îáõîäà óçëîâ äåðåâà.
	void inorderWalk(Node *node) const {
		if (node != NULL) {
			inorderWalk(node.left_);
			inorderWalk(node.right_);
		}
	}

	void insert(const T& key, Node* node) {
		if (key < node->key_) {
			if (node->left_ == NULL)
				node->left_ = new Node(key, NULL, NULL, node);
			else
				insert(key, node->left_);
		}
		if (key >= node->key_) {
			if (node->right_ == NULL)
				node->right_ = new Node(key, NULL, NULL, node);
			else
				insert(key, node->right_);
		}
	}

	void iterativeInsert(const T& key) {
		Node* node = root_;
		bool isInsert = 0;
		while (isInsert == 0) {
			node->size_++;
			if (key < node->key_) {
				if (node->left_ == NULL) {
					node->left_ = new Node(key, NULL, NULL, node);
					isInsert = 1;
				}
				else
					node = node->left_;
			}
			else {
				if (node->right_ == NULL) {
					node->right_ = new Node(key, NULL, NULL, node);
					isInsert = 1;
				}
				else
					node = node->right_;
			}
		}
	}

	void deleteKey(Node* root, const T& key) {
		if (root == NULL)
			return;
		root->size_--;
		if (key < root->key_)
			deleteKey(root->left_, key);
		else if (key > root->key_)
			deleteKey(root->right_, key);
		else if (root->left_ != NULL && root->right_ != NULL) {
			root->key_ = minimum(root->right_)->key_;
			deleteKey(root->right_, root->key_);
		}
		else
			if (root->left_ != NULL) {
				root = root->left_;
			}
			else if (root->right_ != NULL) {
				root = root->right_;
			}
			else {
				(root->p_->key_ > root->key_) ? root->p_->left_ = NULL : root->p_->right_ = NULL;
				delete root;
			}
	}

	Node* minimum(Node* x) {
		if (x->left_ == NULL)
			return x;
		return minimum(x->left_);
	}


};