#ifndef _AVLTREE_H_ // sentry
#define _AVLTREE_H_

#include "bstree.h"
#include <string>
using namespace std;

class AVLTree; // forward declaration

class AVLNode : public BinarySearchNode
{
private:
	int balance;
public:
	AVLNode(string data); // constructor
	void print(); // overloaded print member

	friend class AVLTree;
};

class AVLTree : public BinarySearchTree
{
public:
	//AVLTree(); // constructor (not needed?)
	//~AVLTree(); // destructor (not needed?)

	// overloaded insert function
	void insert(string addme);

private:

	// internal functions
	AVLNode * insert(AVLNode * &node, string addme);

	void update_balance(AVLNode * node);

	AVLNode * LL_rotate(AVLNode * LL_hvy);
	AVLNode * RR_rotate(AVLNode * RR_hvy);
	AVLNode * LR_rotate(AVLNode * LR_hvy);
	AVLNode * RL_rotate(AVLNode * RL_hvy);
};


#endif