平衡二叉树

二叉树是 n 个结点的有限集合，该集合为空集，或由一个根节点和两颗互不相交的、分别称为根节点的左子树与右子树的二叉树组成。

• 所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树，这两者统称为斜树
• 一颗二叉树中，若所有分支节点都存在左子树与右子树，并且所有叶子节点都在同一层次上，这样的二叉树称为满二叉树
• 对一颗具有 n 个节点的二叉树按层次编号，若编号 i (1 < i < n) 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树

AVL树：最先发明的自平衡二叉查找树，所有节点的左子树与右子树的高度差不超过1，也被称为高度平衡树。查询数据效率非常高。

• 右单旋

  //左斜树进行右单旋
  //
  //	    k2            k1
  //     /             /  \
  //    k1      ->    N    k2
  //   /
  //  N

  （1）将 k1 的右子树保存在 k2 的左子树中

  （2）将 k1 的右子树置为 k2

• 左单旋

  //右斜树进行左单旋
  //
  //    k2                  k1
  //      \                /  \
  //       k1      ->     k2   N
  //         \
  //          N

  （1）将 k1 的左子树保存在 k2 的右子树中

  （2）将 k1 的左子树置为 k2

• 右左旋

  //    k2            k2              N
  //      \             \            / \
  //       k1    ->      N     ->   k2  N
  //      /               \
  //     N                 k1

  当造成不平衡的是右子树，并且右子树的左子树比较高：

  先以 k2 的右子树为根节点右旋，再以 k2 为根节点左旋

• 左右旋

  //     k2           k2         N
  //    /            /          / \
  //   k1     ->    N     ->   k1  k2
  //     \         /
  //      N       k1

  当造成不平衡的为左子树，并且左子树的右子树比较高：

  先以 k2 的左子树为根节点左旋，再以 k2 为根节点右旋

以下是 AVL 树的类定义及实现代码

//平衡二叉树的类定义及实现
#include<iostream>
class CAlTree {
public:
	CAlTree():m_pRoot(nullptr){}
	~CAlTree() {}
	typedef struct _NODE {
		int nData;//节点的数据元素
		_NODE* pLeft;//节点的左指针
		_NODE* pRight;//节点的右指针
	}NODE, *PNODE;
	bool Insert(//向一颗二叉树中添加一个数据
		int nEle//要插入的数据
	);
	bool Delete(//从一颗二叉树中删除一个数据
		int nEle//要删除的数据
	);
	void PreOrder();//前序遍历
	void InOrder();//中序遍历
	void PostOrder();//后序遍历
	
private:
	bool InsertNode(//向一颗二叉树中添加一个数据
		int nEle,//要添加的数据
		PNODE& pNode//要插入的子树
	);
	bool DeleteNode(//从一棵二叉树中删除一个数据      
		int nEle,
		PNODE& pTree//要删除的子树
	);
	int GetHeight(//获取一颗子树的高度
		PNODE pTree
	);
	bool GetMax(//获取一颗子树的最大值
		PNODE pTree,
		int& nMax//用于得到最大值
	);
	bool GetMin(//获取一颗子树的最小值
		PNODE pTree,
		int& nMin//用于得到最小值
	);
	bool SingleL(//以此节点为圆心左旋
		PNODE& pNode//要旋转的节点
	);
	bool SingleR(//以此节点为圆心右旋
		PNODE& pNode//要旋转的节点
	);
	bool DoubleLR(//以此节点为圆心左右旋
		PNODE& pNode//要旋转的节点
	);
	bool DoubleRL(//以此节点为圆心右左旋
		PNODE& pNode//要旋转的节点
	);

	void PreOrderTraverse(PNODE& pNode);//前序遍历
	void InOrderTraverse(PNODE& pNode);//中序遍历
	void PostOrderTraverse(PNODE& pNode);//后序遍历

	PNODE m_pRoot;//根节点
};

//************************************
// Method:    GetHeight
// FullName:  CAlTree::GetHeight
// Access:    private 
// Returns:   int
// Function: 获取一颗子树的高度
// Parameter: PNODE pTree
//************************************
int CAlTree::GetHeight(PNODE pTree) {
	if (pTree == nullptr)
		return 0;
	int nLeftHeight = GetHeight(pTree->pLeft);//递归获取左子树高度
	int nRightHeight = GetHeight(pTree->pRight);//递归获取右子树高度
	return (nLeftHeight > nRightHeight ? nLeftHeight : nRightHeight) + 1;
}


//************************************
// Method:    GetMax
// FullName:  CAlTree::GetMax
// Access:    private 
// Returns:   bool
// Function: 获取一颗子树的最大值
// Parameter: PNODE pTree
// Parameter: int & nMax
//************************************
bool CAlTree::GetMax(PNODE pTree, int& nMax) {
	if (pTree == nullptr)
		return false;
	while (pTree) {
		//根据左节点小于根节点，右节点大于根节点的规则，
		//右子树叶节点或无右节点的根节点数据最大
		nMax = pTree->nData;
		pTree = pTree->pRight;
	}
	return true;  
}

//************************************
// Method:    GetMin
// FullName:  CAlTree::GetMin
// Access:    private 
// Returns:   bool
// Function: 获取一颗子树的最小值
// Parameter: PNODE pTree
// Parameter: int & nMin
//************************************ 
bool CAlTree::GetMin(PNODE pTree, int& nMin) {
	if (pTree == nullptr)
		return false;
	while (pTree) {
		nMin = pTree->nData;
		pTree = pTree->pLeft;
	}
	return true;
}

//************************************
// Method:    SingleL
// FullName:  CAlTree::SingleL
// Access:    private 
// Returns:   bool
// Function: 左单旋
// Parameter: PNODE & pNode
//************************************
bool CAlTree::SingleL(PNODE& pNode) {
	PNODE k2 = pNode;
	PNODE k1 = pNode->pRight;
	//将 k1 的左子树保存在 k2 的右子树中
	//将 k1 的左子树置为 k2
	k2->pRight = k1->pLeft;
	k1->pLeft = k2;
	pNode = k1;
	return true;
}

//************************************
// Method:    SingleR
// FullName:  CAlTree::SingleR
// Access:    private 
// Returns:   bool
// Function: 右单旋
// Parameter: PNODE & pNode
//************************************
bool CAlTree::SingleR(PNODE& pNode) {
	PNODE k2 = pNode;
	PNODE k1 = pNode->pLeft;
	//将 k1 的右子树保存在 k2 的左子树中
	//将 k1 的右子树置为 k2
	k2->pLeft = k1->pRight;
	k1->pRight = k2;
	pNode = k1;
	return true;
}

//************************************
// Method:    DoubleLR
// FullName:  CAlTree::DoubleLR
// Access:    private 
// Returns:   bool
// Function: 左右旋
// Parameter: PNODE & pNode
//************************************
bool CAlTree::DoubleLR(PNODE& pNode) {
	//先以 k2 的左子树为根节点左旋，再以 k2 为根节点右旋    
	SingleL(pNode->pLeft);
	SingleR(pNode);
	return true;
}

//************************************
// Method:    DoubleRL
// FullName:  CAlTree::DoubleRL
// Access:    private 
// Returns:   bool
// Function: 右左旋
// Parameter: PNODE & pNode
//************************************
bool CAlTree::DoubleRL(PNODE& pNode) {
	//先以 k2 的右子树为根节点右旋，再以 k2 为根节点左旋    
	SingleL(pNode->pRight);
	SingleR(pNode);
	return true;
}

//************************************
// Method:    Insert
// FullName:  CAlTree::Insert
// Access:    public 
// Returns:   bool
// Function: 向树中插入一个数据
// Parameter: int nEle
//************************************
bool CAlTree::Insert(int nEle) {
	return InsertNode(nEle, m_pRoot);
}

//************************************
// Method:    InsertNode
// FullName:  CAlTree::InsertNode
// Access:    private 
// Returns:   bool
// Function: 向树中插入一个数据
// Parameter: int nEle
// Parameter: PNODE & pNode
//************************************
bool CAlTree::InsertNode(int nEle, PNODE& pNode) {
	bool bSuccess = true;
	//1.判断是否是要插入的节点
	if (pNode == nullptr) {
		//从根节点开始寻找，若找到了要插入的位置，就新建一个子节点
		pNode = new NODE;
		pNode->pLeft = nullptr;
		pNode->pRight = nullptr;
		pNode->nData = nEle;
		return true;
	}
	//2.要插入的数据和当前节点比较大小
	if (nEle > pNode->nData) {
		//若要插入的数据大，则与该节点的右子节点进行大小比较
		bSuccess = InsertNode(nEle, pNode->pRight);//递归调用
	}
	else if (nEle < pNode->nData) {
		//若要插入的数据小，则与该节点的左子节点进行大小比较
		bSuccess = InsertNode(nEle, pNode->pLeft);
	}
	else {
		return false;
	}
	if (bSuccess == false) {
		return bSuccess;
	}

	//3.判断插入之后本节点是否平衡
	int nLHeight = GetHeight(pNode->pLeft);//左子节点高度 
	int nRHeight = GetHeight(pNode->pRight);//右子节点高度
	int nSub = nLHeight - nRHeight;//高度差
	//3.1若左子节点与右子节点高度差大于1
	if (nSub == 2) {
		//3.1.1需要右旋              
		nLHeight = GetHeight(pNode->pLeft->pLeft);
		nRHeight = GetHeight(pNode->pLeft->pRight);
		if (nLHeight >= nRHeight) {//左子节点高度大于等于右子节点，右单旋
			SingleR(pNode);
		}
		//3.1.2需要左右旋
		else
			DoubleLR(pNode);
	}
	//3.2若右边高
	else if (nSub == -2) {
		//3.2.1需要左旋
		nLHeight = GetHeight(pNode->pRight->pLeft);
		nRHeight = GetHeight(pNode->pRight->pRight);
		if (nLHeight <= nRHeight) {//左单旋
			SingleL(pNode);
		}
		//3.2.2需要右左旋
		else
			DoubleRL(pNode);
	}
	return true;
}

//************************************
// Method:    Delete
// FullName:  CAlTree::Delete
// Access:    public 
// Returns:   bool
// Function: 平衡二叉树的删除
// Parameter: int nEle
//************************************
bool CAlTree::Delete(int nEle) {
	return DeleteNode(nEle, m_pRoot);
}

//************************************
// Method:    DeleteNode
// FullName:  CAlTree::DeleteNode
// Access:    private 
// Returns:   bool
// Function: 从一棵二叉树中删除一个数据    
// Parameter: int nEle
// Parameter: PNODE & pTree
//************************************
bool CAlTree::DeleteNode(int nEle, PNODE& pTree) {
	bool bSuccess = true;
	//1.判断节点是否为空
	if (pTree == nullptr) {
		return false;
	}
	//2.判断要删除的数据比当前子树的根节点大，在右子树中继续删除
	if (nEle > pTree->nData) {
		bSuccess = DeleteNode(nEle, pTree->pRight);
	}
	//3.若比根节点小，则在左子树中继续删除
	else if (nEle < pTree->nData) {
		bSuccess = DeleteNode(nEle, pTree->pLeft);
	}
	//4.判断要删除的数据和当前子树根节点一样大，则删除
	else {
		 //4.1要删除的节点是叶子节点
		if (pTree->pLeft == nullptr && pTree->pRight == nullptr) {
			delete pTree;
			pTree = nullptr;
			return true;
		}
		//4.2要删除的节点不是叶子结点，而是树干
		//4.2.1分别获取此节点的左子树高和右子树高
		int nLeftHeight = GetHeight(pTree->pLeft);
		int nRightHeight = GetHeight(pTree->pRight);
		//4.2.2比较俩子树高度
		if (nLeftHeight > nRightHeight) {
			//左高，直接获取左子树的最大值，并到左子树中删除最大值
			int nMax = 0;
			GetMax(pTree->pLeft, nMax);
			pTree->nData = nMax;
			bSuccess = DeleteNode(nMax, pTree->pLeft);
		}
		else {
			//右边高，直接获取右子树的最小值，并到右子树中删除最小是
			int nMin = 0;
			GetMin(pTree->pRight, nMin);
			pTree->nData = nMin;
			bSuccess = DeleteNode(nMin, pTree->pRight);
		}
	}
	if (bSuccess == false)
		return bSuccess;

	//5.判断删除之后，节点是否平衡
	int nLHeight = GetHeight(pTree->pLeft);
	int nRHeight = GetHeight(pTree->pRight);
	int nSub = nLHeight - nRHeight;
	//5.1若左边高
	if (nSub == 2) {
		//5.1.1需要右旋
		nLHeight = GetHeight(pTree->pLeft->pLeft);
		nRHeight = GetHeight(pTree->pLeft->pRight);
		if (nLHeight >= nRHeight)
			SingleR(pTree);
		//5.1.2需要左右旋
		else
			DoubleLR(pTree);
	}
	//5.2若右边高
	else if (nSub == -2) {
		nLHeight = GetHeight(pTree->pRight->pLeft);
		nRHeight = GetHeight(pTree->pRight->pRight);
		//5.2.1需要左旋
		if (nLHeight <= nRHeight)
			SingleL(pTree);
		//5.2.2需要右左旋
		else
			DoubleRL(pTree);
	}
	return true;
}

//前序遍历
void CAlTree::PreOrder() {
	PreOrderTraverse(m_pRoot);
}

//************************************
// Method:    PreOrderTraverse
// FullName:  CAlTree::PreOrderTraverse
// Access:    private 
// Returns:   void
// Function: 前序遍历
// Parameter: PNODE & pNode
//************************************
void CAlTree::PreOrderTraverse(PNODE& pNode) {
	if (pNode == nullptr)
		return;
	printf("%d ", pNode->nData);//输出节点的数据
	PreOrderTraverse(pNode->pLeft);//递归遍历左子树
	PreOrderTraverse(pNode->pRight);//递归遍历右子树
}

//中序遍历
void CAlTree::InOrder() {
	InOrderTraverse(m_pRoot);
}

//************************************
// Method:    InOrderTraverse
// FullName:  CAlTree::InOrderTraverse
// Access:    private 
// Returns:   void
// Function: 中序遍历
// Parameter: PNODE & pNode
//************************************
void CAlTree::InOrderTraverse(PNODE& pNode) {
	if (pNode == nullptr)
		return;
	InOrderTraverse(pNode->pLeft);//递归遍历左子树
	printf("%d ", pNode->nData);//输出节点的数据
	InOrderTraverse(pNode->pRight);//递归遍历右子树
}

//后序遍历
void CAlTree::PostOrder() {
	PostOrderTraverse(m_pRoot);
}

//************************************
// Method:    PostOrderTraverse
// FullName:  CAlTree::PostOrderTraverse
// Access:    private 
// Returns:   void
// Function: 后序遍历
// Parameter: PNODE & pNode
//************************************
void CAlTree::PostOrderTraverse(PNODE& pNode) {
	if (pNode == nullptr)
		return;
	PostOrderTraverse(pNode->pLeft);//递归遍历左子树
	PostOrderTraverse(pNode->pRight);//递归遍历右子树
	printf("%d ", pNode->nData);//输出节点的数据
}

int main()
{
	CAlTree CTree;
	CTree.Insert(1);
	CTree.Insert(2);
	CTree.Insert(3);
	CTree.Insert(4);
	CTree.Insert(5);
	CTree.Insert(6);
	CTree.PreOrder();
	printf("\n");           
	CTree.InOrder();
	printf("\n");
	CTree.PostOrder();
	printf("\n");
	CTree.Delete(6);
	CTree.PreOrder();
	printf("\n");	
	return 0;
}