AVL树双旋转疑问

1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis.AVL树种查找.插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.本文介绍了AVL树的设计思想和基本操作. 2. 基本术语 有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树

本文配套源码 /******************************************************************** created: 2007/08/28 filename: avltree.c author: Lichuang purpose: AVL树的实现代码, 参考资料<<数据结构与算法分析-C语言描述>>, 作者Allen Weiss **************************************************

二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树 深度为log(n)的二叉树 这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(n)+1). 我们将处于同一深度的节点归为一层.如果除最后一层外的其他层都被节点填满时,二叉树有最小深度log(n). 二

树的平衡,我们已经知道DWL算法,不过DWL算法需要从整体上平衡树,但是树的平衡也可以局部的进行,由Adel'son-Vel'skii-Landis提出了一种经典方法,称为AVL树. 1.概念:AVL树,或者说可适应树,是指树中每个节点的的平衡因子的绝对值不大于1,即只能为-1,0,1 平衡因子:节点的右子树的高度减去左子树的高度 2.AVL树的插入:从新插入节点到根的路径上,修改遇到的节点的平衡因子即可,对其他部分没影响 1)向右子女的右子树插入一个节点,单旋转就可以 2)向右子女的左子树插入

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明.谢谢!   二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树 深度为log(n)的二叉树 这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(

树旋转(Tree rotation)是二叉树中的一种子树调整操作,每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合. 左旋和右旋 树的旋转有两种基本的操作,即左旋(逆时针方向旋转)和右旋(顺时针方向旋转). 树旋转包括两个不同的方式,分别是左旋转(以P为转轴)和右旋转(以Q为转轴).两种旋转呈镜像,而且互为逆操作. 下图示意了两种树旋转过程中, 子树的初态和终态 +---+ +---+ | Q | | P | +---+ +---+ / \ righ

二叉查找树(BSTree)中进行查找.插入和删除操作的时间复杂度都是O(h),其中h为树的高度.BST的高度直接影响到操作实现的性能,最坏情况下,二叉查找树会退化成一个单链表,比如插入的节点序列本身就有序,这时候性能会下降到O(n).可见在树的规模固定的前提下,BST的高度越低越好. 平衡二叉树 平衡二叉树是计算机科学中的一类改进的二叉查找树. 平衡二叉树具有以下性质: (1)一棵空树是平衡二叉树 (2)如果树不为空,它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.

既然,我们已经证明,保持 AVL 树的平衡将会使性能得到很大的提升,那我们看看如何在程序中向树插入一个新的键值.因为所有的新键是作为叶节点插入树的,而新叶子的平衡因子为零,所以我们对新插入的节点不作调整.不过一旦有新叶子的插入我们必须更新其父节点的平衡因子.新叶子会如何影响父节点的平衡因子取决于叶节点是左子节点还是右子节点.如果新节点是右子节点,父节点的平衡因子减 1.如果新节点是左子节点,父节点的平衡因子将加 1.这种关系可以递归地应用于新节点的前两个节点,并有可能影响到之前的每一个甚至是根节

二叉搜索树        1.所有非叶子结点至多拥有两个儿子(Left和Right):        2.所有结点存储一个关键字:        3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树.        搜索:从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中:否则,如果查询关键字比结点关键字小,就进入左儿子:如果比结点关键字大,就进入右儿子:如果左儿子或右儿子的指针为空,则报告找不到相应的关键字. B-树 1. M阶B-树是一种多路平衡搜索树(并不是