平衡二叉树的查找

基于平衡二叉排序树的查找（AVL树）

这一篇博客里总结一下基于平衡二叉树的查找，为什么会有这种查找呢？平衡二叉树又是什么东西呢？现在就来仔细理解一下！

在基于二叉排序树的查找里，我们可以得到的时间复杂度是在O(log2(n)到O(n))之间，当二叉排序树只有一颗子树的时候，所谓的基于排序二叉树的查找就退化成了顺序查找了，有什么办法能改善一下这种情况吗？有！，我们可以控制二叉排序树，让二叉排序树的左右子树均衡一些，比如，让二叉排序树的左右子树的节点数目相差的绝对值不超过1（小于或者等于1），这样，就控制住了二叉排序树的左右子树均衡程度，使基于二叉排序树的查找不至于退化成了顺序查找

 

 

有了以上思路，下面，就可以给出平衡二叉排序树（AVL树）的定义：

　　　　1.平衡二叉排序树左右子树高度差的绝对值小于或者等于1

　　　　2.平衡二叉排序树的左右子树也是一颗平衡二叉排序树

 

有了以上的定义，可以发现，实际上，折半查找中分析算法比较次数的二叉判定树实际上就是这个平衡二叉排序树

 

好了，接下来，就是平衡二叉排序树的定义了，为了描述左右子树的高度差，引入了一个概念：平衡因子。平衡因子的值就是右子树高度值减去左子树的的高度值，由此可见，平衡因子的值在-1到1之间

下面是定义

typedef struct _TreeNode
{
	struct  _TreeNode *leftNode;
	struct  _TreeNode *rightNode;
	int    blance;//平衡因子：右子树深度减去左子树深度的值
	DataType data;
}TreeNode,*TreeRoot;

　接下来就是：将一个值插入到平衡二叉排序树中何合适的位置，并将保持平衡二叉排序树的平衡性。最后返回新插入的结点

　　将以上的任务分为几个步骤来完成。

　　　1.判断根节点是否为空，若为空，直接建立一个新结点，返回根节点，程序结束，若不为空，进入第二步

　　　2.寻找应该正确插入的位置，在寻找过程中记录距离插入位置最近的平衡因子不为0的根节点A_Node及其父节点Parent_ANode，如果在寻找过程中找到等于被插入数值的结点，返回空节点，程序结束（这个时候不需要插入），否则记录下应该插入的结点（为空）Node及其父节点Parent_Node，进入第三步

　　　3.根据第二部中找到Parent_node插入建立新结点并插入

　　　4.修改A_node的平衡因子，并根据被插入数据和A_Node值对比的结果记录A_Node的左孩子或者右孩子B_Node

　　　5.修改从B_Node到被插入结点add的平衡因子

　　　6.根据被插入类型LR,RL,LL,RR进行相对应的操作

 

 

下面是代码

TreeNode *Insert_Blance_Tree(TreeRoot &root,DataType key)
{
	if (root==nullptr)
	{
		root=new TreeNode;
		root->leftNode=nullptr;
		root->rightNode=nullptr;
		root->data=key;
		root->blance=0;
		return root;
	}
	//寻找插入位置
	else
	{
		TreeNode *node=root;
		TreeNode *parent_node=nullptr;
		TreeNode *A_Node=root;
		TreeNode *parent_A=nullptr;
		while (node!=nullptr)
		{
			if (node->blance!=0)
			{
				A_Node=node;
				parent_A=parent_node;
			}
			parent_node=node;
			if (node->data==key)
			{
				return nullptr;//一样的，不用插入了！！！
			}
			else if (node->data<key)
			{
				node=node->rightNode;
			}
			else
			{
				node=node->leftNode;
			}
		}
		//构造并插入结点
		TreeNode *add=new TreeNode;
		add->data=key;
		add->leftNode=nullptr;
		add->rightNode=nullptr;
		add->blance=0;
		//注意一下，这里为什么要用parent_node而不能直接修改node
		if (parent_node->data>key)
		{
			parent_node->leftNode=add;
		}
		else
		{
			parent_node->rightNode=add;
		}

		//接下来就是重点了!
		/*
		1.修改从距离被插入结点add最近的失衡节点A到add父节点的平衡因子
		2.判断失衡的类型，LL,LR,RR,RL，并做对应的处理
		*/

		
		TreeNode *B_Node;
		//1.修改最近失衡结点A的平衡因子，并确定B结点
		if (key>A_Node->data)
		{
			B_Node=A_Node->rightNode;
			A_Node->blance++;
		}
		else
		{
			B_Node=A_Node->leftNode;
			A_Node->blance--;
		}

		//修改从B结点到add结点的平衡因子
		TreeNode *p=B_Node;
		while (p!=add)
		{
			if (p->data>key)
			{
				p->blance=-1;
				p=p->leftNode;
			}
			else
			{
				p->blance=1;
				p=p->rightNode;
			}
		}


		//判断失衡类型并做相应的处理

		//LL类型
		if (A_Node->blance==-2&&B_Node->blance==-1)
		{
			A_Node->leftNode=B_Node->rightNode;
			B_Node->rightNode=A_Node;
			if (parent_A->data>A_Node->data)
			{
				parent_A->leftNode=B_Node;
			}
			else
			{
				parent_A->rightNode=B_Node;
			}
			A_Node->blance=0;
			B_Node->blance=0;
		}



		//RR类型
		if (A_Node->blance==2&&B_Node->blance==1)
		{
			A_Node->rightNode=B_Node->leftNode;
			B_Node->leftNode=A_Node;
			if (parent_A->data>A_Node->data)
			{
				parent_A->leftNode=B_Node;
			}
			else
			{
				parent_A->rightNode=B_Node;
			}
			A_Node->blance=0;
			B_Node->blance=0;

		}
		//LR类型
		if (A_Node->blance==-2&&B_Node->blance==1)
		{
			TreeNode *C_Node=B_Node->rightNode;
			B_Node->rightNode=C_Node->leftNode;
			A_Node->leftNode=C_Node->rightNode;
			C_Node->leftNode=B_Node;
			C_Node->rightNode=A_Node;
			if (parent_A->data>A_Node->data)
			{
				parent_A->leftNode=C_Node;
			}
			else
			{
				parent_A->rightNode=C_Node;
			}
			if (C_Node->blance==-1)
			{
				C_Node->blance=0;
				A_Node->blance=1;
				B_Node->blance=0;
			}
			else if (C_Node->blance==1)
			{
				C_Node->blance=0;
				A_Node->blance=0;
				B_Node->blance=-1;
			}
			else if (C_Node->blance==0)
			{
				C_Node->blance=0;
				A_Node->blance=0;
				B_Node->blance=0;
			}
		}

		//RL类型
		if (A_Node->blance==2&&B_Node->blance==-1)
		{
			TreeNode *C_Node=B_Node->leftNode;
			A_Node->rightNode=C_Node->leftNode;
			B_Node->leftNode=C_Node->rightNode;
			C_Node->leftNode=A_Node;
			C_Node->rightNode=B_Node;
			if (C_Node->blance==-1)
			{
				C_Node->blance=0;
				A_Node->blance=0;
				B_Node->blance=1;
			}
			else if (C_Node->blance==1)
			{
				C_Node->blance=0;
				A_Node->blance=-1;
				B_Node->blance=0;
			}
			else if (C_Node->blance==0)
			{
				C_Node->blance=0;
				A_Node->blance=0;
				B_Node->blance=0;
			}
		}
		return add;
	}

　　

 

以上的代码是向平衡二叉排序树插入结点的代码，下面是建立平衡二叉排序树的代码，实际上依然和建立二叉排序树的概念是一样的

void Create_Balance_Tree(TreeRoot & root)
{
	DataType key;
	while (std::cin>>key)
	{
		Insert_Blance_Tree(root,key);
	}


}

　　

然后查找的过程也是类似的

TreeNode* findBy_BlanceTree(TreeRoot root,DataType key)
{
	if (root)
	{
		if (key==root->data)
		{
			return root;
		}
		else if (key<root->data)
		{
			return findBy_BlanceTree(root->leftNode,key);
		}
		else
		{
			return findBy_BlanceTree(root->rightNode,key);
		}
	}
}

　　

 

接下里依然是算法分析！

如果不看建立平衡排序二叉树的过程，单纯看基于平衡二叉排序树的查找过程，我们会发现，卧槽，那种退化为顺序查找的可能性完全消失了，基于平衡排序二叉树的时间复杂度为O（log2(n)）

 

如果考察一下平衡二叉排序树的插入过程，我们会发现，时间复杂度会比之前多一点，大概是2O(log2(n)),不过，这依然是O(log2(n))

 

然后，建立平衡二叉排序树的过程依然类似，也就是O(nlog2(n))

 

好了，写到这里，基于树的查找也差不多写完了，我们会发现，不管是二叉排序树还是平衡二叉排序树，我们的时间复杂度都是一个不断逼近折半查找的过程，最后的平衡二叉排序树的查找过程时间复杂度也确实和折半查找一样了，那么为什么要花这么多力气去建立一个平衡二叉排序树，并且不断地维持他呢？

 

其实很简单，因为折半查找需要元素关键字事先有序啊！而且还必须顺序存储

平衡二叉排序树就没这么娇气了，事实上，平衡二叉排序树也算是事先有序了，事先建立平衡二叉排序树的过程，实际上就是排序嘛！，而且这个时间复杂度也就是O(nlog2(n))了，最好的排序算法也不过如此了！