flash网站镇江做网站的

flash网站,镇江做网站的,微信公众号登录不上,在线网页制作系统小彬AVL树一.概念:1.二叉搜索树2.所有子树高度差至多为13.左右子树都是AVL树4.空树也是AVL树二.特点1.有(或没有)平衡因子,平衡因子 右子树高度 - 左子树高度 1/ 0/ -12.两个logN:高度和时间复杂度3.高度平衡三.结构1.结点(AVLTreeNode):父母,左子树,右子树,平衡因子,值2.AVL树(A…AVL树一.概念:1.二叉搜索树2.所有子树高度差至多为13.左右子树都是AVL树4.空树也是AVL树二.特点1.有(或没有)平衡因子,平衡因子 右子树高度 - 左子树高度 1/ 0/ -12.两个logN:高度和时间复杂度3.高度平衡三.结构1.结点(AVLTreeNode):父母,左子树,右子树,平衡因子,值2.AVL树(AVLTree):结点四.插入1.比较插入值kv的first从根节点的first向下开始比较,走到指定的叶子结点的子节点2.插入后某些结点的平衡因子可能会发生改变,要进行更新:插入到左子树,平衡因子-1;插入到右子树,平衡因子1;依次往上更新3.更新后的平衡因子必有以下几种情况:(正常情况下,插入结点一定有平衡因子发生改变)a 平衡因子变成-1:继续往上判断b 平衡因子变成0:正常结束完美结局c 平衡因子变成-2:坏结局,开始旋转4.若发生旋转,再次更新平衡因子五.旋转a 右单旋(左边彻底高)旋转条件: 平衡因子 -2 -15的右给10的左,5成为10的父母b 左单旋(右边彻底高)旋转条件: 平衡因子 2 115的左给10的右,15做10的父母注意:10结点有两种情况:为根节点和非根节点b树可能为空定义两个结点parent 10 subL5先改变各结点的指向,再更新平衡因子c 左右双旋(先左高,再右高)旋转条件: 2 -1 -1先左旋5再右旋10最终结果:8的左给5的右,8的右给10的左,5和10做8的左右d右左双旋(先右高再左高)12的左给10的右,12的右给15的左,10和15为12的左右用到三个结点parent,subL,subLR先执行subR的左单旋,再执行parent的右单旋最后更新平衡因子判断条件为subRL(12)的平衡因子