資料結構之平衡二叉樹AVL

平衡二次樹AVL：是二叉查找樹的改進版，不會像二叉查找樹一樣，在碰到序列有序是糟糕成達到O（n），平很二叉樹在每次插入的時候，都會試圖檢查左右子樹的高度差是不超過1（包括1），如果超過了，就會調整樹的結構，使樹一直保持平衡，以至于達到非常好的效率，O(logn).

#include <iostream>
using namespace std;
typedef struct BBNode
{
	int m_data;
	// 平衡因子，如果【左子樹的深度】減去【右子樹的深度】,右因為平衡二叉樹左右子樹的深度查不超過1（包括一），是以factor的值為【-1, 0, 1】
	int m_factor;
	BBNode* m_lchild;
	BBNode* m_rchild;
}BBNode, *BBSTree;
           

/*
         a             b
        /             / \
       b      =>     c   a
      /
     c
*/
// 向右旋轉
void R_Rotate(BBSTree& tree)
{
 // 左孩子
 BBNode* lchild = tree->m_lchild;
 // 【左孩子】已經有指針指向了，是以可以指向别的地方了,那麼就指向根【左孩子】的【右孩子】
 tree->m_lchild = lchild->m_rchild;
 // 【左孩子】的【右孩子】已經有指針指向了，那麼可以指向根結點了
 lchild->m_rchild = tree;
 tree = lchild;
}
           

/*
	a		       b
	 \		      / \
	  b	   =>    a   c
	   \
	    c
*/
// 向左旋轉
void L_Rotate(BBSTree& tree)
{
	BBNode* rchild = tree->m_rchild;
	tree->m_rchild = rchild->m_lchild;
	rchild->m_lchild = tree;
	tree = rchild;
}
           

/*
	 a		      a			    c
	/		     /			   / \
   b	=>      c	     =>	    b   a
	\		   /
	 c		  b
*/
// 調整左子樹的平衡
// 1：單旋轉-右旋轉
// 2: 雙旋轉-【左子樹】先左旋轉-再右旋轉
void LeftBalance(BBSTree& tree)
{
	BBNode* lchild = tree->m_lchild;
	// 如果是偏向一邊的(根->左孩子->左孩子)，隻需要單旋轉
	if (lchild->m_factor == 1)
	{
		tree->m_factor = 0;
		lchild->m_factor = 0;
		R_Rotate(tree);
	}
	// 如果不是偏向一邊(根->左孩子->右孩子),則需要雙選
	// 即先将【左子樹】左旋轉，再将樹右旋轉
	else if (lchild->m_factor == -1)
	{
		BBNode* lchild_rchild = lchild->m_rchild;
		// 修改【根結點】和【左孩子】的【平衡因子】
		switch (lchild_rchild->m_factor)
		{
		case -1:
			{
				tree->m_factor = 0;
				lchild->m_factor = 1;
			}break;
		case 0:
			{
				tree->m_factor = 0;
				lchild->m_factor = 0;
			}break;
		case 1:
			{
				tree->m_factor = -1;
				lchild->m_factor = 0;
			}break;
		}
		lchild_rchild->m_factor = 0;
		L_Rotate(lchild);
		R_Rotate(tree);
	}
}
           

/*
       a                   a                       c
	    \                   \                     / \
         b       =>          c          =>       a   b
	    /                     \
	   c                       b
*/
// 調整右子樹的，兩種情況
// 1：隻需要單旋轉-左旋轉
// 2: 雙旋轉-【右子樹】先右旋轉-再左旋轉
void RightBalance(BBSTree& tree)
{
	BBNode* rchild = tree->m_rchild;
	// 如果是偏向一邊的(根->右孩子->右孩子)
	if (rchild->m_factor == -1)
	{
		tree->m_factor = 0;
		rchild->m_factor = 0;
		L_Rotate(tree);
	}
	// 如果不是偏向一邊的(根->右孩子->左孩子)
	else if (rchild->m_factor == 1)
	{
		BBNode* rchild_lchild = rchild->m_lchild;
		switch (rchild_lchild->m_factor)
		{
		case -1:
			{
				tree->m_factor = 1;
				rchild->m_factor = 0;
			}break;
		case 0:
			{
				tree->m_factor = 0;
				rchild->m_factor = 0;
			}break;
		case 1:
			{
				tree->m_factor = 0;
				rchild->m_factor = -1;
			}break;
		}
		rchild_lchild->m_factor = 0;
		L_Rotate(rchild);
		R_Rotate(tree);
	}
}
           

// @tree:平衡二叉樹
// @e:要插入的元素
// @taller:是否增高了
int insertAVL(BBSTree& tree, int e, bool& taller)
{
	// 如果tree不存，則在此處插入結點
	if (!tree)
	{
		BBNode* node = new BBNode;
		node->m_data = e;
		node->m_factor = 0;	//新結點沒有左右孩子，factor自然為0
		node->m_lchild = 0;
		node->m_rchild = 0;
		tree = node;
		// 隻要是新結點，taller都标記為true，但是它實際上存在着下面三種情況的:
		// 1:如果父節點沒有左右孩子，則插入node，真的右增高
		// 2:如果父節點存在左孩子，插入node作為右孩子，則實際上并未增高
		// 3:如果父節點存在右孩子，插入node作為左孩子，則實際上并未增高
		// 但是這些都留待上一層的函數裡去處理
		taller = true;
	}
	else
	{
		// 要插入的元素小于目前結點
		if (e < tree->m_data)
		{
			// 将元素插入到目前結點的左子樹中
			if (!insertAVL(tree->m_lchild, e, taller))
			{
				// 如果插入失敗
				return 0;
			}
			// 子樹是不是增高了
			if (taller)
			{
				switch (tree->m_factor)
				{
				// 如果之前【右子樹】高于【左子樹】
				case -1:
					{
						// 因為插入的是【左子樹】，是以兩邊的深度相等了
						tree->m_factor = 0;
						// 當然，因為插入元素之後，高度不變
						taller = false;
					}break;
				// 如果之前【左子樹】高度等于【右子樹】
				case 0:
					{
						// 因為插入的是【左子樹】，是以目前【左子樹】高于【右子樹】
						// 但是還未超過【平衡二叉樹】【左右子樹】高度差不大于1的限制
						tree->m_factor = 1;
						taller = true;
					}
				// 如果之前【左子樹】高度大于【右子樹】
				case 1:
					{
						// 目前插入的是【左子樹】，是以目前【左子樹】高于了【右子樹】，
						// 并且超過了【平衡二叉樹】【左右子樹】高度差不大于1的限制
						// 是以要調整下
						LeftBalance(tree);
						taller = false;
					}
				}  // switch
			}  // if(taller)
		}
		else if (e == tree->m_data)
		{
			return 0;
		}
		else
		{
			if (!insertAVL(tree->m_rchild, e, taller))
			{
				return 0;
			}
			if (taller)
			{
				switch(tree->m_factor)
				{
				// 如果之前【左子樹】低于【右子樹】
				case -1:
					{
						// 因為目前插入的是【右子樹】，是以【右子樹】的高度
						// 超過了【平衡二次樹】的【左右子樹】深度差不超過1的限制
						// 是以要調整下
						RightBalance(tree);
						taller = false;
					}break;
				// 如果之前【左子樹】高度等于【右子樹】
				case 0:
					{
						// 因為目前插入的是【右子樹】，是以【右子樹】的高度增高了，
						// 但是不會超過【平衡二次樹】的【左右子樹】深度差不超過1的限制
						tree->m_factor = -1;
						taller = true;
					}break;
				// 如果之前【左子樹】高于【右子樹】
				case 1:
					{
						// 因為目前插入的是【右子樹】，是以兩邊的高度相等了
						tree->m_factor = 0;
						taller = false;
					}break;
				}
			}
		}  // else
	}  // else
	return 1;
}
 
           

// 中序周遊
void orderTraver(BBSTree tree)
{
	if (tree)
	{
		orderTraver(tree->m_lchild);
		cout<<tree->m_data<<" ";
		orderTraver(tree->m_rchild);
	}
}
           

int main()
{
	BBSTree tree = 0;
	bool taller;
	insertAVL(tree, 1, taller);
	insertAVL(tree, 2, taller);
	insertAVL(tree, 3, taller);
	insertAVL(tree, 4, taller);
	insertAVL(tree, 5, taller);
	insertAVL(tree, 6, taller);
	orderTraver(tree);
	return 0;
}