avl map implementation with copy-on-change (incomplete)

Map.cc

#include "Map.hpp"
#include <iostream>

template <class Key, class T, class Compare>
Map<Key, T, Compare>::Node::Node(const value_type& _data) : data(_data) { 
	left = right = NULL;
	height = 1; 
}

/// Konstruktor kopiujacy tworzy gleboka kopie drzewa
template <class Key, class T, class Compare>
Map<Key, T, Compare>::Node::Node(Node& n) : data(n.data) { 
	left = new Node(*(n.left));
	right = new Node(*(n.right));
	height = n.height;
}

/// Aktualizacja wysokosci poddrzewa po obrocie
template <class Key, class T, class Compare>
void Map<Key, T, Compare>::Node::recountHeight()
{
	int hleft = (this->left ? this->left->height : 0);
	int hright = (this->right ? this->right->height : 0);
	this->height = 1 + ((hleft > hright) ? hleft : hright);
}

template <class Key, class T, class Compare>
int Map<Key, T, Compare>::Node::heightDiff() const
{
	return
		(this->left ? this->left->height : 0) 
		- (this->right ? this->right->height : 0);
}

// Obroty drzewa w lewo i prawo
template <class Key, class T, class Compare>
typename Map<Key, T, Compare>::Node* 
	Map<Key, T, Compare>::Node::rotateLeft()
{
	Node* pivot = this->right;
	this->right = pivot->left;
	pivot->left = this;
	this->recountHeight();
	pivot->recountHeight();
	return pivot;
}

template <class Key, class T, class Compare>
typename Map<Key, T, Compare>::Node* 
	Map<Key, T, Compare>::Node::rotateRight()
{
	Node* pivot = this->left;
	this->left = pivot->right;
	pivot->right = this;
	this->recountHeight();
	pivot->recountHeight();
	return pivot;
}

/// Realizacja balansowania AVL
template <class Key, class T, class Compare>
typename Map<Key, T, Compare>::Node* 
	Map<Key, T, Compare>::Node::avlBalance()
{
	int bal = this->heightDiff();
	if (bal < -1) {
		if (right->heightDiff() <= 0) {
			return this->rotateLeft();
		} else {
			right = right->rotateRight();
			return rotateLeft();
		}
	} else if (bal > 1) {
		if (left->heightDiff() >= 0) {
			return rotateRight();
		} else {
			left = left->rotateLeft();
			return rotateRight();
		}
	}
	return this;
}

template <class Key, class T, class Compare>
typename Map<Key, T, Compare>::Node* 
	Map<Key, T, Compare>::Node::treeAddRec(const value_type& v, Compare comp)
{
	bool cv = comp(data.first, v.first);
	if (cv)
		if (left)
			left = left->treeAddRec(v, comp);
		else
			left = new Node(v);
	else if (data.first == v.first) {
		return this;
	} else 
		if (right)
			right = right->treeAddRec(v, comp);
		else
			right = new Node(v);
	recountHeight();
	return this->avlBalance();
}

/// Jesli obiekt byl odwolaniem do istniejacego, utworz gleboka kopie
template <class Key, class T, class Compare>
void Map<Key, T, Compare>::writeRequired()
{
	if (*copy_count > 0) {
		root = new Node(*root);
		(*copy_count)--;
		copy_count = new int(0);
	}	
}

// Pozbadz sie jednej z kopii, usun drzewo jesli ostatnia
template <class Key, class T, class Compare>
void Map<Key, T, Compare>::disposeCopy()
{
	if (*copy_count == 0) {
		delete root;
		delete copy_count;
	} else
		(*copy_count)--;
}

template <class Key, class T, class Compare>
void Map<Key, T, Compare>::insert(const value_type& v)
{
	writeRequired();
	if (root)
		root = root->treeAddRec(v, comp);
	else
		root = new Node(v);
}

/// Znalezienie elementu w drzewie.
//  Zwraca NULL jeśli nie istnieje.
template <class Key, class T, class Compare>
typename Map<Key, T, Compare>::value_type* 
	Map<Key, T, Compare>::find(const Key& k) const
{
	Node* root = this->root;
	while (root != NULL) {
		bool cv = comp((root->data).first, k);
		if (cv)
			root = root->left;
		else if ((root->data).first == k)
			return &(root->data);
		else {
			root = root->right;
		}
	}
	return NULL;
}
	
/// Usun element z drzewa.
template <class Key, class T, class Compare>
void Map<Key, T, Compare>::erase(Key& k)
{
	writeRequired();
	Node** root = &(root);
	while (*root != NULL) {
		bool cv = comp(((*root)->data).first, k);
		if (cv)
			root = &((*root)->left);
		else if ((*root)->data.first == k) {
			if (!(*root)->left && !(*root)->right) { 
				// brak potomków
				delete *root;
				*root = NULL;
			} else if ((*root)->left && (*root)->right) { 
				// lewy i prawy potomek
				Node* tmp;
				Node** succ = &(*root)->right;
				while ((*succ)->left)
					succ = &(*succ)->left;
				(*root)->data = (*succ)->data;
				tmp = (*succ)->right;
				*succ.left = *succ.right = NULL;
				delete *succ;
				*succ = tmp;
			} else {
				// tylko lewy/prawy potomek
				Node* tmp = *root;
				if ((*root)->left)
					*root =(*root)->left;
				else
					*root =(*root)->right;
				*tmp.left = *tmp.right = NULL;
				delete tmp;
			}
		} else 
			root = &((*root)->right);
	}
}

template <class Key, class T, class Compare>
T& Map<Key, T, Compare>::operator[](const Key& k)
{
	value_type* f = find(k);
	if (!f) {
		insert(std::make_pair(k,T()));
		f = find(k);
	}
	return f;
}

template <class Key, class T, class Compare>
Map<Key, T, Compare>::Map(Map& m) 
{ 
	root = m.root; 
	copy_count = m.copy_count; 
	*copy_count++; 
}

template <class Key, class T, class Compare>
Map<Key, T, Compare>::~Map()
{
	disposeCopy();
}

template <class Key, class T, class Compare>
Map<Key, T, Compare>& Map<Key, T, Compare>::operator=(Map<Key, T, Compare>& m)
{
	if (this == &m) return *this;
	disposeCopy();
	root = m.root;
	copy_count = m.copy_count;
	(*copy_count)++;
}

Map.hpp

#include <utility>
#include <functional>

template <class Key, class T, class Compare = std::less<Key> >
class Map {
	public:
		typedef std::pair<const Key, T> value_type;

		Map() { root = NULL; copy_count = new int(0); }
		Map(Map& m);
		~Map();

		Map& operator=(Map& m);
		T& operator[](const Key& k);
		
		void insert(const value_type&);
		value_type* find(const Key&) const;
		void erase(Key&);

	private:
		struct Node {
			Node* left;
			Node* right;
			value_type data;
			int height;

			Node(const value_type& _data);
			Node(Node& n);
			~Node() { delete left; delete right; }

			void recountHeight();
			int heightDiff() const;

			Node* treeAddRec(const value_type& v, Compare comp);
			Node* rotateLeft();
			Node* rotateRight();
			Node* avlBalance();
		} ;

		Node* root;
		Compare comp;
		int* copy_count;

		void writeRequired();
		void disposeCopy();
} ;