精华内容
下载资源
问答
  • 这一篇博客里总结一下基于平衡二叉树的查找,为什么会有这种查找呢?平衡二叉树又是什么东西呢?现在就来仔细理解一下! 在基于二叉排序树的查找里,我们可以得到的时间复杂度是在O(log2(n)到O(n))之间,当二叉排序...

    基于平衡二叉排序树的查找(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))了,最好的排序算法也不过如此了!

     

     

     

     

    转载于:https://www.cnblogs.com/YTYMblog/p/6131868.html

    展开全文
  • 平均二叉树,计算平均查找长度 二叉树的删除
  • 1、平衡二叉树的插入: 2、平衡二叉树的查找

    1、平衡二叉树的插入:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    2、平衡二叉树的查找

    在这里插入图片描述

    展开全文
  • 平衡二叉树查找关键字结点

    千次阅读 2018-08-21 14:57:47
    二叉排序树的定义: ...平衡二叉树的性质: (1)根结点的左子树和右子树的深度最多相差1。 (2)根结点的左子树和右子树叶都是一棵平衡二叉树。 平衡二叉树查找关键字是否存在? 解析思路:...

    二叉排序树的定义:
    (1)若它的左子树不为空,则左子树所有结点均小于它的根结点的值;
    (2)若它的右子树不为空,则右子树所有结点均大于它的根结点的值;
    (3)它的左右子树都是二叉排序树。

    平衡二叉树本质上是二叉排序树。
    平衡二叉树的性质
    (1)根结点的左子树和右子树的深度最多相差1
    (2)根结点的左子树和右子树叶都是一棵平衡二叉树。

    平衡二叉树查找关键字是否存在?
    解析思路:
    (1)先根据结点个数计算平衡二叉树深度,根据深度将不符合要求的排除
    计算过程如下:
    ni表示深度为h的平衡二叉树中含有的最少结点数,有n0=0,n1=1,n2=2;
    计算公式为:这里写图片描述
    递归的计算平衡二叉树中含有的最少结点数。
    (2)根据平衡二叉树的性质,选择符合要求的选项
    性质:若存在左子树则左子树小于根结点,若存在右子树则右子树大于根结点。

    实例:
    1、在含有15个结点的平衡二叉树上,查找关键字为28(存在该结点)的结点,则依次比较的关键字可能是()。
    A.30,36
    B.38,48,28
    C.48,18,38,28
    D.60,30,50,40,38,36
    答案:C
    解析如下:
    n0=0,n1=1,n2=2,
    n3=n2+n1+1=4
    n4=n3+n2+1=7
    n5=n4+n3+1=12
    n6=n5+n4+1=20>15

    高度为6的平衡二叉树最少有20个结点,因此15个结点的平衡二叉树高度为5,而最小的叶子结点的层数为3.

    各选项构成的平衡二叉树
    如上图所示,根据D的元素构成的二叉树深度为6,显然不合要求;
    A在查找30后应该指向左孩子,而不是右孩子;B的错误同样。

    而C的查找路径,如下图所示:
    这里写图片描述
    [上图的来源]
    (https://www.ppkao.com/daan/7007317/255767F11A95606E51099B40301AF0F3)

    2、在含有14个结点的平衡二叉树上,查找关键字为40的结点,则依次比较的关键字可能是()
    A.27,48,25,43,40
    B.47,45,18,27,36,40
    C.46,42,18,20,28,40
    D.15.45.40
    答案:D

    解析如下:
    n0=0,n1=1,n2=2,
    n3=n2+n1+1=4
    n4=n3+n2+1=7
    n5=n4+n3+1=12
    n6=n5+n4+1=20>14
    因此平衡二叉树的高度为5.
    如下图所示:
    各选项构成的二叉树如下:

    各选项构成的二叉树

    显然,A选项中蓝色圆圈的25元素比根结点27小,不符合平衡二叉树的定义。
    B,C选项的树高均为6,不满足平衡二叉树的深度为5的要求。
    D选项符合要求。

    展开全文
  • 1、平衡二叉树定义是一种二叉排序树(二叉查找树、二叉搜索树),其中每个节点的左子树和右子树的高度差不大于1。(左右子树也是平衡二叉树)平衡因子BF = ...平衡二叉树的查找、插入和删除的时间复杂度都是O(logn)...

    1、平衡二叉树定义

    是一种二叉排序树(二叉查找树、二叉搜索树),其中每个节点的左子树和右子树的高度差不大于1。(左右子树也是平衡二叉树)

    平衡因子BF = 二叉树节点的左子树深度减去右子树深度 = 节点的平衡因子(BF)

    最小不平衡子树:距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树。

    为了提高查找效率,把二叉排序树构造成平衡二叉树。平衡二叉树的查找、插入和删除的时间复杂度都是O(logn),最坏情况下,二叉排序树的查找时间复杂度是O(n)即非常不平衡的斜树。所以要构造平衡二叉树提高查找效率。

    2、平衡二叉树的构建方法:

    若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,原有其他所有不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树。

    失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于 1 的结点作为根的子树。假设用 A 表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况。

    ( 1 ) RR 型平衡旋转法(右旋)

    由于在 A 的左孩子 B 的左子树上插入结点 F ,使 A 的平衡因子由 1 增至 2 而失去平衡。故需进行一次顺时针旋转操作。 即将 A 的左孩子 B 向右上旋转代替 A 作为根结点, A 向右下旋转成为 B 的右子树的根结点。而原来 B 的右子树则变成 A 的左子树。

    ( 2 ) LL 型平衡旋转法(左旋)

    由于在 A 的右孩子 C  的右子树上插入结点 F ,使 A 的平衡因子由 -1 减至 -2 而失去平衡。故需进行一次逆时针旋转操作。即将 A 的右孩子 C 向左上旋转代替 A 作为根结点, A 向左下旋转成为 C 的左子树的根结点。而原来 C 的左子树则变成 A 的右子树。

    ( 3 ) LR 型平衡旋转法(左右)

    由于在 A 的左孩子 B 的右子数上插入结点 F ,使 A 的平衡因子由 1 增至 2 而失去平衡。故需进行两次旋转操作(先逆时针,后顺时针)。即先将 A 结点的左孩子 B 的右子树的根结点 D 向左上旋转提升到 B 结点的位置,然后再把该 D 结点向右上旋转提升到 A 结点的位置。即先使之成为 LL 型,再按 LL 型处理 。

    如图中所示,即先将圆圈部分先调整为平衡树,然后将其以根结点接到 A 的左子树上,此时成为 LL 型,再按 LL 型处理成平衡型。

    ( 4 ) RL 型平衡旋转法(右左)

    由于在 A 的右孩子 C 的左子树上插入结点 F ,使 A 的平衡因子由 -1 减至 -2 而失去平衡。故需进行两次旋转操作(先顺时针,后逆时针),即先将 A 结点的右孩子 C 的左子树的根结点 D 向右上旋转提升到 C 结点的位置,然后再把该 D 结点向左上旋转提升到 A 结点的位置。即先使之成为 RR 型,再按 RR 型处理。

    如图中所示,即先将圆圈部分先调整为平衡树,然后将其以根结点接到 A 的左子树上,此时成为 RR 型,再按 RR 型处理成平衡型。

    平衡化靠的是旋转。 参与旋转的是 3 个节点(其中一个可能是外部节点 NULL ),旋转就是把这 3 个节点转个位置。注意的是,左旋的时候 p->right 一定不为空,右旋的时候 p->left 一定不为空,这是显而易见的。

    如果从空树开始建立,并时刻保持平衡,那么不平衡只会发生在插入删除操作上,而不平衡的标志就是出现 bf == 2 或者 bf == -2 的节点。

    展开全文
  • 一棵平衡的二叉树的平衡因子只能是1,0,-1如何构建一棵平衡二叉树呢?对一棵平衡的二叉树进行插入操作,插入后,可能导致不平衡,对不平衡的二叉树应该进行旋转操作,将其旋转为平衡二叉树平衡二叉树应该具有...
  • 什么是平衡二叉树? 搜索树结点不同插入次序,将导致不同的深度和平均查找...设 nh 高度为h的平衡二叉树的最少结点数。结点数最少时: 给定结点数为n的AVL树的最大高度为O(log2n) 平衡二叉树的调整 1.RR 旋转(右单
  • 2 平衡二叉查找树平衡二叉查找树不仅满足上面平衡二叉树的定义,还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL 树。AVL 树严格符合平衡二叉查找树的定义,即任何节点的左右子树高度相差不超过1,是一种...
  • 具体功能 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分裂六种操作供选择每种操作均提示输入关键字每次插入或删除一个结点后更新平衡二叉树的显示 平衡二叉树的显示采用凹入表现形式 合并两棵平衡二叉树 ...
  • 平衡二叉树

    2007-12-10 21:16:13
    以利用平衡二叉树实现动态表的查找,本程序实现平衡二叉树的查找,插入,删除,以及各种变化后的平衡处理
  • 平衡二叉树的节点删除比较有意思,删除后,涉及剩余结点的连接和平衡问题。总结一下从平衡二叉树中删除结点可以分为以下三步:找到要删除的结点完成节点的删除找到因为删除而导致不满足平衡二叉树要求的子树并对其...
  • 3. 由TXT文本中读入一系列数据,建立一棵平衡二叉树,并实现查找任何数据功能,并能打印出结点访问路径。 (Makefile编译)
  • 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能问题) 上边 BST 存在问题分析: 左子树全部为空,从形式上看,更像一个单链表. 插入速度没有影响 查询速度明显降低(因为需要依次比较), 不...
  • 在讲B+树之前必须先了解二叉查找树、平衡二叉树(AVLTree)和平衡多路查找树(B-Tree),B+树即由这些树逐步优化而来。 二叉树是每个结点最多有两个子树树结构。通常子树被称作“左子树”(...
  • 平衡二叉树 刚开始接触平衡二叉树,没有什么...平衡二叉树就是每个节点子树高度差不超过1二叉树。可以快速搜索数值一种算法,最糟情况就是一直找到底,但也是log(n)。还是快很多。 #include<stdlib...
  • 19.平衡二叉树

    2020-05-02 17:13:18
    因为平衡二叉树的查找性能不是很稳定,但是如果改造成平衡二叉树时间复杂度就稳定为O(logn)。 平衡二叉树的调整方法: 1.LL旋转 (顺时针):插入点在树的左子树的根节点的左子树上插入 2.RR旋转 (逆时针):插入...
  • 数据结构实验之查找二:平衡二叉树 ...根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 输入 输入一组测试数据。数据的第1行给出一个正整数N(n 输出 输出平衡二叉树的树根。
  • 平衡二叉树(树旋转)

    万次阅读 多人点赞 2018-08-15 23:10:07
    1.概念 平衡二叉树建立在二叉排序树的基础上,目的是使二叉...平衡二叉树的递归定义:平衡二叉树是一棵二叉树,其可以为空,或满足如下2个性质:①左右子树深度之差的绝对值不大于1。②左右子树都是平衡二叉树。 平...
  • 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它左右两个子树高度差绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好解决了二叉查找树...
  • 构造方法平衡二叉树对于二叉查找树,尽管查找、插入及删除操作的平均运行时间为O(logn),但是它们的...二叉树的的平衡因子BF为:该结点的左子树的深度减去它的右子树的深度,则平衡二叉树的所有结点的平衡因子为只...
  • 查找——平衡二叉树

    2015-12-11 21:58:48
    /* *Copyright (c) 2015 , 烟台大学... *All right resvered . *文件名称:平衡二叉树.cpp *作 者: 郑兆涵 *查找——平衡二叉树 */ 问题:平衡二叉树相关算法理解与分析 编程代码: #include #include
  • 文章目录1、什么是二叉树(Binary Tree)2、二叉树的存储方式3、二叉树的遍历4、二叉查找树(Binary Search Tree)4.1 查找操作4.2 插入操作4.3 删除操作5、平衡二叉树(AVL Tree) 1、什么是二叉树(Binary Tree)   ...
  • 一、什么是平衡二叉树平衡二叉树(Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree)译为 自平衡二叉查找树或者高度平衡二叉查找树,简称平衡二叉树,也叫 AVL 树,是一种二叉排序树...
  • 查找-平衡二叉树

    2018-10-16 13:19:42
    当用户进行二叉排序树创建时,对于同一组数据,不同插入次序序列生成不同形态二叉排序树。 ...平衡二叉树(AVL树):所有结点左右子树深度之差绝对值&lt;=1 . 平衡因子:该结...
  • 二叉树每个节点度都不大于2 节点:在树结构中,每一个元素都称之为节点 度:节点子节点个数称之为该节点二叉树结构图 2.二叉查找树 二叉查找树特点 二叉查找树又称二叉搜索树 每个节点度都不...
  • 通过上一篇二叉查找树的文章,相信大家已经掌握了二叉查找树的相关概念和操作,如果忘了...平衡二叉树的前世今生在二叉查找树中,我们知道通过二叉查找树可以提高搜索效率,但是同一个序列,可以构成不同的二叉查找...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,481
精华内容 2,192
关键字:

平衡二叉树的查找