/* AVL 樹（為了效率不從二叉搜索樹繼承）
 * 
 */

#ifndef AVL_TREE_CLASS
#define AVL_TREE_CLASS

#include <stdlib.h>
#include "avltreenode.h"

// 表明結(jié)點(diǎn)平衡因子的常量
const int leftheavy = -1;
const int balanced = 0;
const int rightheavy = 1;

template <class T>
class AVLTree
{
	private:
		// 指向樹根及當(dāng)前結(jié)點(diǎn)的指針
		AVLTreeNode<T> *root;
		AVLTreeNode<T> *current;
		
		// 樹中數(shù)據(jù)項(xiàng)個(gè)數(shù)
		int size;
		
		// 用于復(fù)制構(gòu)造函數(shù)及賦值運(yùn)算符
		AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t);
		
		// 用于析構(gòu)函數(shù)，賦值運(yùn)算符及 ClearList 方法
		void DeleteTree(AVLTreeNode<T> *t);
		
		// 在函數(shù) Find 和 Delete 中用來定位結(jié)點(diǎn)及其雙親在樹中的位置
		AVLTreeNode<T> *FindNode(const T& item, AVLTreeNode<T>* & parent) const;
		
		// 供 Insert 和 Delete 方法在結(jié)點(diǎn)加入子樹或從子樹中刪除時(shí)重建 AVL 樹
		void SingleRotateLeft (AVLTreeNode<T>* &p);
		void SingleRotateRight (AVLTreeNode<T>* &p);
		void DoubleRotateLeft (AVLTreeNode<T>* &p);
		void DoubleRotateRight (AVLTreeNode<T>* &p);
		void UpdateLeftTree (AVLTreeNode<T>* &tree,	bool &reviseBalanceFactor);
		void UpdateRightTree (AVLTreeNode<T>* &tree, bool &reviseBalanceFactor);
		
		// AVL 樹的 Insert 和 Delete 方法
		void AVLInsert(AVLTreeNode<T>* &tree,
            AVLTreeNode<T>* newNode, bool &reviseBalanceFactor);
		void AVLDelete(AVLTreeNode<T>* &tree,
            AVLTreeNode<T>* newNode, bool &reviseBalanceFactor);
		
	public:
		// 構(gòu)造函數(shù)，析構(gòu)函數(shù)
		AVLTree(void);
		AVLTree(const AVLTree<T>& tree);
		~AVLTree(void);
		
		// 賦值運(yùn)算符
		AVLTree<T>& operator= (const AVLTree<T>& tree);
		
		// 標(biāo)準(zhǔn)的表處理函數(shù)
		bool Find(T& item);
		void Insert(const T& item);
		void Delete(const T& item); 
		void ClearList(void);
		bool ListEmpty(void) const;
		int ListSize(void) const;
		
		// 樹的特殊方法
		void Update(const T& item);
		AVLTreeNode<T> *GetRoot(void) const;
};

template <class T>
AVLTreeNode<T> *AVLTree<T>::CopyTree(AVLTreeNode<T> *t)
{
	AVLTreeNode<T> *newlptr, *newrptr, *newNode;
	
	if (t == NULL)
		return NULL;
	
	if (t->left != NULL) 
		newlptr = CopyTree(t->left);
	else
		newlptr = NULL;
	
	if (t->right != 0) 
		newrptr = CopyTree(t->right);
	else
		newrptr = NULL;
	
	newNode = new AVLTreeNode(t->data, newlptr, newrptr);
	return newNode;
}

// 刪除當(dāng)前對象存儲的樹
template <class T>
void AVLTree<T>::DeleteTree(AVLTreeNode<T> *t)
{
    if (t != NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        delete t;
    }
}

// 刪除樹中的所有結(jié)點(diǎn)
template <class T>
void AVLTree<T>::ClearList(void)
{
    DeleteTree(root);
    root = current = NULL;
    size = 0;
}

template <class T>
AVLTree<T>& AVLTree<T>::operator= (const AVLTree<T>& rhs)
{
    // 不能將樹復(fù)制到自身
    if (this == &rhs)
        return *this;
	
	ClearList();
	root = CopyTree(ths.root);
	
	current = root;
	size = ths.size;
	return *this;
}

// 在樹中搜索 item，若找到，則將結(jié)點(diǎn)數(shù)據(jù)賦給 item
template <class T>
bool AVLTree<T>::Find(T& item)
{
    // 使用 FindNode，它需要 parent 參數(shù)
    AVLTreeNode<T> *parent;
	
    // 在樹中搜索 item，將匹配的結(jié)點(diǎn)賦給 current
    current = FindNode(item, parent);
    
    // 若找到，則將數(shù)據(jù)賦給 item 并返回 True
    if (current != NULL)
    {
        item = current->data;
        return true;
    }
    else
		// 在樹中沒找到 item，返回 False
        return false;
}

// 指示樹是否為空
template <class T>
bool AVLTree<T>::ListEmpty(void) const
{
    return (size == 0);
}

// 返回樹中的數(shù)據(jù)項(xiàng)個(gè)數(shù)
template <class T>
int AVLTree<T>::ListSize(void) const
{
    return size;
}

template <class T>
AVLTree<T>::AVLTree(void):root(NULL), current(NULL), size(0)
{}

template <class T>
AVLTree<T>::AVLTree(const AVLTree<T>& tree)
{
	root = CopyTree(tree.root);
	current = root;
	size = tree.size;
}

template <class T>
AVLTree<T>::~AVLTree(void)
{
    ClearList();
}

// 在樹中搜索數(shù)據(jù)項(xiàng)，若找到，則返回結(jié)點(diǎn)地址及指向其雙親的指針；否則，返回 NULL
template <class T>
AVLTreeNode<T> *AVLTree<T>::FindNode(const T& item, AVLTreeNode<T>* & parent) const
{   
    // 用指針 t 從根開始遍歷樹
    AVLTreeNode<T> *t = root;
    
    // 根的雙親為 NULL
    parent = NULL;
    
    // 若子樹為空，則循環(huán)結(jié)束
    while(t != NULL)
    {
        // 若找到鍵值，則退出
        if (item == t->data)
            break;
        else 
        {
            // 修改雙親指針，并移到左子樹或右子樹
            parent = t;
            if (item < t->data)
                t = t->left;
            else 
                t = t->right;
        }
    }
    
    // 返回指向結(jié)點(diǎn)的指針；若沒找到，則返回 NULL
    return t;
}

template <class T>
void AVLTree<T>::SingleRotateLeft (AVLTreeNode<T>* &p)
{
	AVLTreeNode<T> *rc = p->right;
	
	p->balanceFactor = balanced;
	rc->balanceFactor = balanced;
	
	p->right = rc->left;
	rc->left = p;
	p = rc;
} 

// 繞結(jié)點(diǎn) p 順時(shí)針旋轉(zhuǎn)；使 lc 成為新軸
template <class T>
void AVLTree<T>::SingleRotateRight (AVLTreeNode<T>* & p)
{
	// p 的左子樹“超重”，將 p 的左子樹給 lc
	AVLTreeNode<T> *lc = p->left;
	
	// 修改雙親結(jié)點(diǎn)及左孩子的平衡因子
	p->balanceFactor = balanced;
	lc->balanceFactor = balanced;
	
	// lc 的右子樹 st 應(yīng)繼續(xù)為 lc 右子樹的一部分，將它改為 p 的左子樹
	p->left = lc->right;
	
	// 旋轉(zhuǎn) p 使其為 lc 的右子樹，lc 成為新軸
	lc->right = p;
	p = lc;
}

template <class T>
void AVLTree<T>::DoubleRotateLeft (AVLTreeNode<T>* &p)
{
	AVLTreeNode<T> *rc, *np;
	
	rc = p->right;
	np = rc->left;
	if (np->balanceFactor == leftheavy)
	{
		p->balanceFactor = balanced;
		rc->balanceFactor = leftheavy;
	}
	else if (np->balanceFactor == balanced)
	{
		p->balanceFactor = balanced;
		rc->balanceFactor = balanced;
	}
	else
	{
		p->balanceFactor = leftheavy;
		rc->balanceFactor = balanced;
	}
	np->balanceFactor = balanced;
	rc->left = np->right;
	np->right = rc;
	p->right = np->left;
	np->left = p;
	p = np;
}

// 繞結(jié)點(diǎn) p 雙右旋
template <class T>
void AVLTree<T>::DoubleRotateRight (AVLTreeNode<T>* &p)
{
	// 被旋轉(zhuǎn)的兩個(gè)子樹
	AVLTreeNode<T> *lc, *np;
	
	// 在樹中，結(jié)點(diǎn)(lc) < 結(jié)點(diǎn)(np) < 結(jié)點(diǎn)(p)
	lc = p->Left();			// lc 為雙親的左孩子
	np = lc->Right();		// np 為 lc 的右孩子
	
	// 修改 p, lc 和 np 的平衡因子
	if (np->balanceFactor == rightheavy)
	{
		p->balanceFactor = balanced;
		lc->balanceFactor = rightheavy;
	}
	else if (np->balanceFactor == balanced)
	{
		p->balanceFactor = balanced;
		lc->balanceFactor = balanced;
	}
	else
	{
		p->balanceFactor = rightheavy;
		lc->balanceFactor = balanced;
	}
	np->balanceFactor = balanced;
	
	// 在 np 替代雙親 p 之前，注意卸掉其老子樹，連上新子樹
	lc->right = np->left;
	np->left = lc;
	p->left = np->right;
	np->right = p;
	p = np;
} 

template <class T>
void AVLTree<T>::UpdateLeftTree (AVLTreeNode<T>* &p, bool &reviseBalanceFactor)
{
	AVLTreeNode<T> *lc = p->left;	// 左子樹邊偏重
	
	if (lc->balanceFactor == leftheavy) 
	{
		SingleRotateRight(p);    // 需單旋轉(zhuǎn)
		reviseBalanceFactor = false;
	}
	// 右子樹偏重嗎？
	else if (lc->balanceFactor == rightheavy)
	{
		// 做一次雙旋轉(zhuǎn)
		DoubleRotateRight(p);
		// 此時(shí)，根結(jié)點(diǎn)平衡了
		reviseBalanceFactor = false;
	}
}

template <class T>
void AVLTree<T>::UpdateRightTree (AVLTreeNode<T>* &p, bool &reviseBalanceFactor)
{
	AVLTreeNode<T> *rc = p->right;
	
	if (rc->balanceFactor == rightheavy) 
	{
		SingleRotateLeft(p);
		reviseBalanceFactor = false;
	}
	else if (rc->balanceFactor == leftheavy) 
	{
		DoubleRotateLeft(p);
		reviseBalanceFactor = false;
	}
}

template <class T>
void AVLTree<T>:: AVLInsert(AVLTreeNode<T>* & tree,
							AVLTreeNode<T>* newNode, bool &reviseBalanceFactor)
{
	// 是否需修改結(jié)點(diǎn)的 balanceFactor 值的標(biāo)志
	bool rebalanceCurrNode;
	
	// 掃描到空子樹；此時(shí)應(yīng)插入新節(jié)點(diǎn)
	if (tree == NULL)
	{
		// 更新雙親結(jié)點(diǎn)使其指向新節(jié)點(diǎn)     
		tree = newNode;
		
		// 將新結(jié)點(diǎn)的 balanceFactor 賦值為 0
		tree->balanceFactor = balanced;
		
		// 廣播消息；balanceFactor 值被改變
		reviseBalanceFactor = true;       
	}
	// 若新結(jié)點(diǎn)的數(shù)據(jù)值 < 當(dāng)前數(shù)據(jù)值，則遞歸遍歷左子樹
	else if (newNode->data < tree->data)
	{
		AVLInsert(tree->left, newNode, rebalanceCurrNode);
		
		// 檢查是否應(yīng)修改 balanceFactor 值
		if (rebalanceCurrNode)
		{
			// 從左偏重的子樹往左，將違背 AVL 條件，進(jìn)行旋轉(zhuǎn)（情況3） 
			if (tree->balanceFactor == leftheavy)
				UpdateLeftTree(tree,reviseBalanceFactor);         

			// 從平衡結(jié)點(diǎn)往左，往左子樹增加結(jié)點(diǎn)，滿足 AVL 條件（情況 1）
			else if (tree->balanceFactor == balanced)
			{
				tree->balanceFactor = leftheavy;
				reviseBalanceFactor = true;
			}
			// 從右偏重子樹往左，將產(chǎn)生平衡子樹，滿足 AVL 條件（情況 2）
			else
			{
				tree->balanceFactor = balanced;
				reviseBalanceFactor = false;
			}
		}
		else
			// 不需平衡此結(jié)點(diǎn)，也不用平衡上結(jié)點(diǎn)
			reviseBalanceFactor = false;
	}
	// 否則，遞歸遍歷右子樹
	else
	{
		AVLInsert(tree->right, newNode, rebalanceCurrNode);
		
		// 檢查是否應(yīng)修改 balanceFactor 值
		if (rebalanceCurrNode)
		{
			// 從左偏重子樹往右，將平衡結(jié)點(diǎn)，滿足 AVL 條件（情況 2）
			if (tree->balanceFactor == leftheavy)
			{
				// 掃面右子樹，結(jié)點(diǎn)左偏重，則將成為平衡結(jié)點(diǎn)
				tree->balanceFactor = balanced;     
				reviseBalanceFactor = false;
			}
			// 從平衡子樹往右，將產(chǎn)生右偏重結(jié)點(diǎn)，滿足 AVL 條件（情況 1）
			else if (tree->balanceFactor == balanced)
			{
				// 結(jié)點(diǎn)原為平衡；將成為右偏重
				tree->balanceFactor = rightheavy;
				reviseBalanceFactor = true;
			}
			else
				// 從右偏重結(jié)點(diǎn)向右，將違背 AVL 條件，應(yīng)進(jìn)行旋轉(zhuǎn)（情況 3）
				UpdateRightTree(tree, reviseBalanceFactor);
		}
		else
			reviseBalanceFactor = false;
	}
}

template <class T>
void AVLTree<T>::Insert(const T& item)
{
	// 定義指向 AVL 樹結(jié)點(diǎn)的指針
	AVLTreeNode<T> *treeRoot = root, *newNode;
	
	// 供 AVLInsert 重新平衡結(jié)點(diǎn)的標(biāo)志
	bool reviseBalanceFactor = false;
	
	newNode = new AVLTreeNode<T>(item,NULL,NULL);
	
	// 調(diào)用遞歸函數(shù)實(shí)際插入元素
	AVLInsert(treeRoot, newNode, reviseBalanceFactor);
	
	// 賦新值給基類中的數(shù)據(jù)成員
	root = treeRoot;
	current = newNode;
	size++;
}

// 若當(dāng)前結(jié)點(diǎn)已定義且數(shù)據(jù)值與給定數(shù)據(jù)值相等，則將結(jié)點(diǎn)值賦給 item；否則，將 item 插入到樹中
template <class T>
void AVLTree<T>::Update(const T& item)
{   
    if (current != NULL && current->data == item)
		current->data = item;
    else
        Insert(item);
}

// 返回根結(jié)點(diǎn)的地址
template <class T>
AVLTreeNode<T> *AVLTree<T>::GetRoot(void) const
{
    return root;
}

template <class T>
void AVLTree<T>::AVLDelete(AVLTreeNode<T>* &tree, AVLTreeNode<T>* newNode, bool &reviseBalanceFactor)
{
	// 太過復(fù)雜，又不常用（AVL 樹應(yīng)主要用于初始化，因?yàn)槠洳迦牖騽h除的成本過高）
	throw "AVLTree::AVLDelete: Function not implement";
}

template <class T>
void AVLTree<T>::Delete(const T& item)
{
	throw "AVLTree::Delete: Function not implement";
}

#endif  // AVL_TREE_CLASS