数据结构——平衡二叉树

                                   二叉平衡树

       上一篇博客写到了二叉排序树，二叉排序树在最好的情况下，其时间复杂度为O(logn)，而在最坏的情况下，二叉排序树变成一个线性表，查找也就变成了顺序查找，时间复杂度为O(n)，所以二叉排序树的查找效率取决于树的形状，而树的形状又取决于构造树节点的元素序列，如果这个序列是完全有序的，那边构造出来的二叉排序树就是一个线性表了。如果能把二叉排序树整理得深度尽量小，那么查找的效率也就会比较高，其实二叉排序树在查找中比较的次数就是二叉树的层数。要想层数尽可能小，就需要树比较平衡。树中平衡概念是指根节点的左右子树的高度之差的绝对值不大于1，并且左右子树都是平衡的。有这种特性的树叫二叉平衡树，也叫AVL树。构造二叉平衡树用来查找，查找的速度会更快，查找的时间复杂度为O(logn)。

       对于二叉排序树，由于添加删除节点可能会改变树的结构，所以添加删除节点做相应的处理来维持树的平衡。当添加节点时，每经过一个节点，就把这个节点入栈，这里用栈的好处是插入后要进行回溯来检查平衡是否被破坏。像二叉平衡树一样(参照二叉排序树)找到要插入的位置，插入成功后进行回溯，检查所经过的节点的平衡因子，这个平衡因子是指以这个节点为根的树的所有叶子节点深度之差的最大值，如果树是平衡的，那么树中的每个节点的平衡因子的绝对值都小于等于1。在回溯的过程中，如果发现有哪个节点的平衡因子的绝对值大于1，就说明树的平衡被破坏了。当平衡被破坏后，就要进行相应的旋转处理来恢复平衡。

       恢复平衡的旋转有单左旋和单右旋。

       图中是单左旋。

       单左旋的过程是，当B的右子树上添加了新节点，这时A节点的平衡因子为-2，失去平衡，通过左单旋，把B的左子树BL设置成A的右子树，再把A设置成B的左孩子，把B变成树的根节点。由于B为根的树的所有节点的元素都大于A，所以把BL变成A的右子树不会破坏二叉排序树的特性。A是小于B的，所以A可以成为B的左子节点，所以这种旋转不破坏二叉排序树的特性。由于这样变换了，BR上添加的节点所导致的不平衡被解决了，BR上添加的节点增加的深度被A来低效掉了。

       这个过程可以简单地理解为为B为支点，把A向左下拉，然后把BL和B的连边断开，把BL连到A的右子节点上去，B就到了最上方，成为了根节点。

      这个图中显示的是单右旋

      当在BL子树中添加了节点后，A的平衡因子为2，以A为根的树失去平衡。单右旋时，把BR变成A的左子树，再把A变成B的右子树。和上同理，这样不会破坏二叉排序树的特性，并且A抵消了由于在BL中添加节点增加的深度。

      这个过程也可以简单地理解成以B为支点，把A向右下方拉，再把BR和B的连线断开，让BR成为A的左子树。这时B上升为最高的点，成为根节点。

而如果像如下图这样

     在根节点A的左子节点B的右子树中添加节点导致C子树中的深度比AR中的节点的深度大于1时，树就失去了平衡。这时需要先在B处做一次左旋，得到如下图形状

再在A处做一次右旋最终得到平衡树

       同理，如果向A的右子节点B的左子树中添加了节点添加B的左子树节点的深度比A的左子树节点的深度大1时，树的平衡也被破坏，这时先在B处做一次右旋处理，再在A处做一次左旋处理，又可以让树恢复平衡，这和上一种情况呈镜像处理。

下面是二叉平衡树的实现代码

#pragma once
#ifndef BINAVLTREE
#define BINAVLTREE
const int LH = 1;
const int EH = 0;
const int RH = -1;
namespace dataStructure
{
	template<typename T>
	struct BinAVLTreeNode
	{
		T data;
		int bf = 0;//平衡因子
		BinAVLTreeNode<T> *lc = NULL;
		BinAVLTreeNode<T> *rc = NULL;
	};

	template<typename T>
	class BinAVLTree
	{
	public:
		BinAVLTree();
		~BinAVLTree();
		BinAVLTreeNode<T>* Search(const T &t)const;
		bool Insert(const T &t);
		bool Delete(const T &t);

	protected:
		int size;
		BinAVLTreeNode<T> *root;
		BinAVLTreeNode<T>* SearchHelper(const T &t, BinAVLTreeNode<T> *&f);
		BinAVLTreeNode<T>* SearchHelper(const T &t, BinAVLTreeNode<T> *&f, BinAVLTreeNode<T> **stack, int &stackIndex);
		/**
		* 以subRoot为根节点的树左旋，执行后subRoot指向执行前subRoot的左子节点
		*/
		void LeftRotate(BinAVLTreeNode<T> *&subRoot);

		/**
		* 以subRoot为根节点的树右旋，执行后subRoot指向执行前subRoot的右子节点
		*/
		void RightRotate(BinAVLTreeNode<T>* &subRoot);

		/**
		* 对subRoot为根节点的树插入时做左旋转，插入节点在subRoot的左子树上
		*/
		void InsertLeftBalance(BinAVLTreeNode<T>* &subRoot);

		/**
		* 对subRoot为根节点的树插入时做右旋转，插入节点在subRoot的右子树上
		*/
		void InsertRightBalance(BinAVLTreeNode<T>* &subRoot);

		/**
		* 插入节点进行回溯，并平衡
		*/
		void InsertBalance(const T &t, BinAVLTreeNode<T> **stack, int &stackIndex);

		void DeleteLeftBalance(BinAVLTreeNode<T>* &subRoot, bool &isShorter);
		void DeleteRightBalance(BinAVLTreeNode<T>* &subRoot, bool &isShorter);
		void DeleteBalance(const T &t, BinAVLTreeNode<T> **stack, int &stackIndex);
		void DeleteHelper(const T &t, BinAVLTreeNode<T>* &p, BinAVLTreeNode<T>** stack, int &stackIndex);


	};
	template<typename T>
	BinAVLTree<T>::BinAVLTree()
	{
		root = NULL;
		size = 0;
	}
	template<typename T>
	BinAVLTree<T>::~BinAVLTree()
	{

	}
	template<typename T>
	BinAVLTreeNode<T>* BinAVLTree<T>::Search(const T &t)const
	{

	}
	template<typename T>
	bool BinAVLTree<T>::Insert(const T &t)
	{
		BinAVLTreeNode<T> *f;
		BinAVLTreeNode<T> **stack = new BinAVLTreeNode<T>*[size+1];
		int stackIndex = 0;
		if (!SearchHelper(t, f, stack,stackIndex)) 
		{
			BinAVLTreeNode<T> *p;
			p = new BinAVLTreeNode<T>;
			p->data = t;
			p->bf = 0;
			if (size == 0)
			{
				root = p;
			}
			else if(t<f->data)
			{
				f->lc = p;
			}
			else
			{
				f->rc = p;
			}
			InsertBalance(t, stack,stackIndex);
			size++;
			return true;
		}
		else
		{
			return false;
		}

	}

	template<typename T>
	bool BinAVLTree<T>::Delete(const T &t)
	{

	}

	template<typename T>
	BinAVLTreeNode<T>* BinAVLTree<T>::SearchHelper(const T &t, BinAVLTreeNode<T> *&f)
	{
		return NULL;
	}

	template<typename T>
	BinAVLTreeNode<T>* BinAVLTree<T>::SearchHelper(const T &t, BinAVLTreeNode<T> *&f, BinAVLTreeNode<T> **stack, int &stackIndex)
	{
		BinAVLTreeNode<T>* p = root;
		f = NULL;
		while (p&&p->data != t)
		{
			f = p;
			stack[stackIndex++] = p;
			if (t<p->data)
			{
				p = p->lc;
			}
			else
			{
				p = p->rc;
			}
		}
		return p;
	}

	template<typename T>
	void BinAVLTree<T>::LeftRotate(BinAVLTreeNode<T> *&subRoot)
	{
		//左旋操作
		BinAVLTreeNode<T>* pr;
		pr = subRoot->rc;
		subRoot->rc = pr->lc;//把原根节点的右子节点的左子树变成原根节点的右子树
		pr->lc = subRoot;//把原根节点的右子节点的左子树变成原根节点
		subRoot = pr;//新平衡后的树的根节点设置成原根节点的右子节点
	}

	template<typename T>
	void BinAVLTree<T>::RightRotate(BinAVLTreeNode<T>* &subRoot)
	{
		//右旋操作
		BinAVLTreeNode<T>* pl;
		pl = subRoot->lc;
		subRoot->lc = pl->rc;//把原根节点的左子节点的右子树变成原根节点的左子树
		pl->rc = subRoot;//把原根节点变成原根节点的左子节点的右子树
		subRoot = pl;//把平衡后的树的根节点设置成原根节点的左子节点
	}

	template<typename T>
	void BinAVLTree<T>::InsertLeftBalance(BinAVLTreeNode<T>* &subRoot)
	{
		BinAVLTreeNode<T> *pl, *pr;
		pl = subRoot->lc;
		switch (pl->bf)
		{
		case LH:
			subRoot->bf = pl->bf = EH;
			RightRotate(subRoot);
			break;
		case RH:
			pr = pl->rc;
			switch (pr->bf)
			{
			case LH:
				subRoot->bf = RH;
				pl->bf = RH;
				break;
			case EH:
				subRoot->bf = pl->bf = EH;
				break;
			case RH:
				subRoot->bf = EH;
				pl->bf = LH;
				break;
			default:
				break;
			}
			pr->bf = 0;
			LeftRotate(subRoot->lc);    
			RightRotate(subRoot);
			break;
		default:
			break;
		}
	}

	template<typename T>
	void BinAVLTree<T>::InsertRightBalance(BinAVLTreeNode<T>* &subRoot)
	{
		BinAVLTreeNode<T> *pl, *pr;
		pr = subRoot->rc;
		switch (pr->bf)
		{
		case RH:
			subRoot->bf = pr->bf = EH;
			LeftRotate(subRoot);
			break;
		case LH:
			pl = pr->lc;
			switch (pl->bf)
			{
			case RH:
				subRoot->bf = LH;
				pr->bf = EH;
				break;
			case EH:
				subRoot->bf = pr->bf = EH;
				break;
			case LH:
				subRoot->bf = EH;
				pr->bf = RH;
				break;
			default:
				break;
			}
			pl->bf = 0;
			RightRotate(subRoot->rc);
			LeftRotate(subRoot);
			break;
		default:
			break;
		}
	}


	template<typename T>
	void BinAVLTree<T>::InsertBalance(const T &t, BinAVLTreeNode<T> **stack, int &stackIndex)
	{
		bool isTaller = true;
		while(stackIndex>0&&isTaller)
		{
			BinAVLTreeNode<T> *pc, *pp;
			pc = stack[--stackIndex];
			if (stackIndex == 0) 
			{
				pp = NULL;
			}
			else
			{
				pp = stack[stackIndex-1];
			}
			if(t<pc->data)
			{
				switch (pc->bf)
				{
				case LH:
					if (!pp) 
					{
						InsertLeftBalance(pc);
						root = pc;
					}
					else if(pp->lc == pc)
					{
						InsertLeftBalance(pp->lc);
					}
					else
					{
						InsertLeftBalance(pp->rc);
					}
					isTaller = false;
					break;
				case EH:
					pc->bf = LH;
					break;
				case RH:
					pc->bf = EH;
					isTaller = false;
					break;
				default:
					break;
				}
			}
			else
			{
				switch (pc->bf)
				{
				case RH:
					if(!pp)
					{
						InsertRightBalance(pc);
						root = pc;
					}
					else if(pp->lc == pc)
					{
						InsertRightBalance(pp->lc);
					}
					else
					{
						InsertRightBalance(pp->rc);
					}
					isTaller = false;
					break;
				case EH:
					pc->bf = RH;
					break;
				case LH:
					pc->bf = EH;
					isTaller = false;
					break;
				default:
					break;
				}
			}
		}
	}

	template<typename T>
	void BinAVLTree<T>::DeleteLeftBalance(BinAVLTreeNode<T>* &subRoot, bool &isShorter)
	{

	}

	template<typename T>
	void BinAVLTree<T>::DeleteRightBalance(BinAVLTreeNode<T>* &subRoot, bool &isShorter)
	{
	}

	template<typename T>
	void BinAVLTree<T>::DeleteBalance(const T &t, BinAVLTreeNode<T> **stack, int &stackIndex)
	{

	}

	template<typename T>
	void BinAVLTree<T>::DeleteHelper(const T &t, BinAVLTreeNode<T>* &p, BinAVLTreeNode<T>** stack, int &stackIndex) 
	{

	}

}
#endif

这里只实现也插入操作，其中删除操作跟插入操作的平衡差不多

下面是测试代码

#include "stdafx.h"
#include <iostream>
#include "binavltree.h"
using namespace std;
using namespace dataStructure;


int main()
{
	BinAVLTree<int> *aveTree = new BinAVLTree<int>;
	aveTree->Insert(46);
	aveTree->Insert(20);
	aveTree->Insert(68);
	aveTree->Insert(80);
	aveTree->Insert(90);
	system("pause");
	return 0;
}

可以执行完aveTree->Insert(80)后，树是平衡的，如下图(a)所示

       而再添加90的节点，则会导致树失去平衡，如图(b)所示，在Insert(90)中就通过旋转来平衡了树，得到如图(c)所示的结果，可以在main函数中添加相应的断点调试可以发现程序可以达到预期的效果。