西安企业seo外包服务公司,西安网站推广优化,发布网站的流程,免费咨询服务合同范本1.1 概念
平衡二叉树就是为了让二叉搜索树的平均查找长度更短#xff0c;时间复杂度更靠近logN,如果一个二叉搜索树不平衡了就会出现图1情况#xff0c;完全变成一个数组#xff0c;时间复杂度也变为了O(N)。 平衡因子#xff1a;平衡因子就是针对于树中某一结点#xff…1.1 概念
平衡二叉树就是为了让二叉搜索树的平均查找长度更短时间复杂度更靠近logN,如果一个二叉搜索树不平衡了就会出现图1情况完全变成一个数组时间复杂度也变为了O(N)。 平衡因子平衡因子就是针对于树中某一结点它的左子树高度减去右子树的高度所得结果就是它的平衡因子如果这个平衡因子的绝对值等于2的话那么这个树就认为出现了不平衡状况我们就需要修正这个树缩小它的平衡因子,缩小平衡因子也就是让树的左右两端高度更均匀平衡让高度越靠近log2N1(N个结点构成的二叉树的高度)。
查找长度查找长度就是查找运算中需要比较的次数树的高度越小查找长度就越小查找效率就越高。它的定义如下
n为查找表中元素个数Pi为查找第i个元素的概率通常假设每个元素查找概率相同Pi1/nCi是找到第i个元素的比较次数显然AVL树中每个节点的比较次数与它所在的层数有关,AVL树本质还是二叉搜索树二叉搜索树又与线性二分查找一样。 这个集合中找到每个数的概率都相同为1/9第一次查找就是数组中间那个元素也就是5第二次查找有两个方向向右或者向左指向2或者7第三次查找有四种可能(1 or 3 or 6 or 8 ) 第四次有两种可能(4 or 9) 于是可以算出期望1x1/92x2/93x4/94x2/925/9,也就是我们给出一个数平均要比较两次就能找到将这个数组抽象为二叉搜索树通过查找长度公式也能得出这棵树的平均查找长度是25/9。
1.2 修正树缩小平衡因子的方法
第一种(左旋) 如果插入一个结点(插入点)到另一个结点A的左儿子的左子树而导致树失衡的话也就是三点连成一条直线(A,A左儿子,插入点)那么我们采用左旋来解决这种情况我们旋转时以谁为支点旋转它的子树呢是以最先发现树不平衡的那位结点也就是从下往上第一个平衡因子为2的那个结点。 首先8肯定是最先发现树不平衡的结点此时以8为支点将它的子树向左(顺时针)移动想象着把他它的子树装进麻袋里看作一个整体来进行移动最后移动到位置后再拆开此时树结构会发生变化由于5结点的right指向了86这个点变得孤立无援但由于树结构发生变化点8的left是空着的于是就让支点8的left的来指向它。 左旋模板 第二种(右旋) 如果插入一个结点(插入点)到另一个结点A的右儿子的右子树而导致树失衡的话也就是三点连成一条直线(A,A右儿子,插入点)那么我们采用左旋来解决这种情况。 右旋模板 可以看见A与A的右儿子B以及插入点这三点构成向右的一条直线 第三种 左右旋如果插入一个结点(插入点)到另一个结点A的左儿子的右子树而导致树失衡的话也就是三点连不成一条直线(A,A左儿子,插入点)那么我们采用左右旋来解决这种情况左右旋实际就是以A的左儿子为支点对它的右子树进行一次右旋然后以A为支点对它左子树进行一次左旋 第四种 右左旋如果插入一个结点(插入点)到另一个结点A的右儿子的左子树而导致树失衡的话也就是三点连不成一条直线(A,A右儿子,插入点)那么我们采用右左旋来解决这种情况右左旋实际就是以A的右儿子为支点对它的左子树进行一次左旋然后以A为支点对它右子树进行一次右旋 java代码实现
class AVLTree {Tree root;public void Insert(int Data){rootTree.InsertNode(root,Data);}public void Inorder(){Tree.Inorder(root);}public int Height(){return Tree.MaxHeight(root);}
}public class Tree {Tree left;Tree right;int Data;public Tree(int Data){this.DataData;}public static Tree InsertNode(Tree root, int Data){if(rootnull){Tree node new Tree(Data);return node;}else {if (Data root.Data) {//插入的是右子树root.right InsertNode(root.right, Data);if(MaxHeight(root.left)-MaxHeight(root.right)-2){if(Dataroot.right.Data)//右旋rootrightTrans(root);elserootright_left_Trans(root);}} else if (Data root.Data) {//插入的左子树root.left InsertNode(root.left, Data);if(MaxHeight(root.left)-MaxHeight(root.right)2){if(Dataroot.left.Data)//左旋rootrightTrans(root);elserootleft_right_Trans(root);}}}return root;}public static Tree Delete(Tree node, int Data){if(nodenull){return null; //未找到}//先找到要删除的节点if(Datanode.Data){node.right Delete(node.right,Data);}elseif(Datanode.Data){node.left Delete(node.left,Data);}else{//找到了if(node.left!null node.right!null){node.DatafindInsteadNode(node.left);Delete(node.left,Data);}else{if(node.right!null)nodenode.right;elseif(node.left!null)nodenode.left;elsenodenull;}}return node;}public static int findInsteadNode(Tree node){if(node.right!null)return findInsteadNode(node.right);elsereturn node.Data;}public static void Inorder(Tree node){if(node!null){Inorder(node.left);System.out.println(node.Data );Inorder(node.right);}}//高度计算函数public static int MaxHeight(Tree node){int leftHeight,rightHeight;if(node!null){leftHeightMaxHeight(node.left);rightHeightMaxHeight(node.right);return (leftHeightrightHeight ?leftHeight:rightHeight)1;}return 0;}//右旋public static Tree rightTrans(Tree A){Tree BA.right;A.rightB.left;B.leftA;return B;}//左右旋public static Tree left_right_Trans(Tree A){Tree BA.left;A.leftrightTrans(B);return leftTrans(A);}//左旋public static Tree leftTrans(Tree A){Tree BA.left;A.leftB.right;B.rightA;return B;}//右左旋public static Tree right_left_Trans(Tree A){Tree BA.right;A.rightleftTrans(B);return rightTrans(A);}public static void main(String[] args) {AVLTree avlTree new AVLTree();avlTree.Insert(10);avlTree.Insert(15);avlTree.Insert(5);avlTree.Insert(3);avlTree.Insert(8);avlTree.Insert(6);}
}
