企业官网建设流程全解析

建设网站 费用吗,做音乐下载网站,制作自助网站,WordPress中文标题不显示平衡二叉树的定义 平衡因子#xff1a;balance factor#xff0c;一般定义为左子树高度减去右子树高度 平衡二叉树#xff1a;AVL树#xff0c;就是每个节点的balance factor的绝对值小于等于1的二叉树#xff0c;需要在每次插入删除操作之后调整最小不平衡树以维护每个节…平衡二叉树的定义平衡因子balance factor一般定义为左子树高度减去右子树高度平衡二叉树AVL树就是每个节点的balance factor的绝对值小于等于1的二叉树需要在每次插入删除操作之后调整最小不平衡树以维护每个节点的balance factor在-101之间最小不平衡树插入后破坏平衡的节点为问题节点trouble离问题节点trouble最近的balance factor不正常的祖先节点就是发现者finder最小不平衡树就是以finder为根节点的不平衡的二叉树实现原理无论是插入还是删除都可能产生最小不平衡树需要对最小不平衡树进行调整以维护平衡因子有时即便不需要调整树的结构也需要更改平衡因子节点的结构需要在节点中增加bf平衡因子以判断以这个节点为根节点的树是否平衡struct TreeNode{ DataType data; struct TreeNoe* left,*right; int bf; }调整策略有左旋和右旋两种操作调整树的结构这里把空节点也看作一个节点即每个非空节点都有两个儿子可能有“空儿子”左旋设需要调整的树的根节点为TT的左儿子为LL的右儿子为Lr需要让Lr移给T作为T的左儿子再让T作为L的右儿子调整后原来的L作为调整后的树的根节点[[左旋.png]]图中三角形代表子树若Lr为空[[左旋_1.png]]N代表“空儿子”TreeNode* LeftRotate(TreeNode* T){ TreeNode* Rt-right; T-rightR-left; R-leftT; return R; }右旋设需要调整的树的根节点为TT的右儿子为RR的左儿子为Rl需要让Rl作为T的右儿子再让T作为R的左儿子调整后原来的R作为调整后的树的根节点[[右旋.png]]TreeNode* RightRotate(TreeNode* T){ TreeNode* LT-left; T-leftL-right; L-rightT; return L }最小不平衡树的调整最小不平衡树有两种情况一种是左子树高度大于右子树高度即根节点的bf大于1另一种是右子树高度大于左子树高度即根节点的bf小于-1设最小不平衡树的根节点为finder调整最小平衡树后需要维护bf值根节点的bf大于1很明显问题出在finder的左子树上需要讨论finder的左儿子的bf设finder的左儿子为L由于finder是离trouble最近的bf不正常的节点所以finder的子孙节点的bf都是正常的也就是-101三种情况finder的左儿子L的bf只可能为-1或1不可能为0假设插入前L的bf为1finder的bf为1插入节点插在L的右子树上插入之后L的bf变为0但以L为根节点的子树的高度没有改变finder的bf就不会改变也就是插入之后没有产生最小不平衡树[[L的bf为0的假设.png]]图中m表示子树的高度根节点的左儿子的bf为1说明插入节点在L的左儿子上L的bf与finder的bf同号只需要对finder进行右旋调整调整之后原来的finder节点和L节点的bf变为0[[L的bf为1.png]]根节点的左儿子的bf为-1说明插入节点在L的右儿子上L的bf与finder的bf异号若直接对finder进行右旋调整之后仍然不平衡需要先对L进行左旋再对finder进行右旋调整需要根据L的右儿子Lr的bf值来更改最终调整后的原来的L节点和finder节点的bf的值Lr节点调整后的bf值为0[[L的bf为-1.png]]Lr的bf为0最终调整后L的bf和finder的bf都为0Lr的bf为1最终调整后L的bf为0finder的bf为-1Lr的bf为-1最终调整后L的bf为1finder的bf为0实现TreeNode* LeftAdjust(TreeNode* finder){ TreeNode* Lfinder-left; if(L-bf1){ T-bfL-bf0; return RightRotate(finder); //直接对finder右旋 } else { //L-bf-1 TreeNode* LrL-right; if(Lr-bf0){ L-bffinder-bf0; } else if(Lr-bf1){ L-bf0; finder-bf-1; } else if(Lr-bf-1){ L-bf1; finder-bf0; } Lr-bf0; finder-leftLeftRotate(L); //对L左旋 return RightRotate(finder); //对finder右旋 } }根节点的bf小于-1与根节点的bf大于1的LeftAdjust类似设R为根节点finder的右儿子根节点的右儿子的bf为-1R的bf和finder的bf同号直接将finder左旋根节点的右儿子的bf为1R的bf和finder的bf不同号先将R右旋再将finder左旋Rl为R的左儿子Rl的bf为0最终调整后R的bf和finder的bf都为0Rl的bf为-1最终调整后R的bf为0finder的bf为1Rl的bf为1最终调整后R的bf为-1finder的bf为0实现TreeNode* RightAdjuct(TreeNode* finder){ TreeNode* Rfinder-right; if(R-bf-1){ finder-bfR-bf0; return LeftRotate(finder); } else { //R-bf1 TreeNode* RlR-left; if(Rl-bf0){ R-bffinder-bf0; } else if(Rl-bf-1){ R-bf0; finder-bf1; } else if(Rl-bf1){ R-bf-1; finder-bf0; } Rl-bf0; finder-rightRightRotate(R); return LeftRotate(finder); } }AVL树的插入继承二叉树递归插入的思想若需要插入的树为空则增加一个节点并插入思路为了找到finder需要增加一个布尔型变量isTaller若树增高了isTaller为true否则为false每次调用插入函数都需要更改isTaller来表示以当前的节点为根节点的子树高度是否增加特殊的在一个空树插入节点后原本是空树的高度增加了0-1finder是离trouble最近的bf不正常的祖先节点为了找到finder可以利用递归插入的特性每次深一层的函数结束后退回浅一层的函数实际上就是从儿子节点的插入函数退回到父节点的插入函数只需要在父节点的插入函数浅一层的函数调用子节点的插入函数深一层的函数后检查isTaller是否为真isTall若为真说明插入的子树的高度增加了需要再检查当前的节点的bf若插在了左子树上若该节点的bf为1左子树高度增加后bf会失衡需要对该节点LeftAdjust调整以后以该节点为根节点的子树的高度不变与插入前一样若该节点的bf为0左子树高度增加后bf变为1仍然平衡但以该节点为根节点的子树高度增加了若该节点的bf为-1左子树高度增加后bf变为0仍然平衡且以该节点为根节点的子树高度不变若插在了右子树上若该节点的bf为-1右子树高度增加后bf会失衡需要对该节点RightAdjust调整以后以该节点为根节点的子树高度不变与插入前一样若该节点的bf为0右子树高度增加后bf变为-1仍然平衡但以该节点为根节点的子树高度增加了若该节点的bf为1右子树高度增加后bf变为0仍然平衡且以该节点为根节点的子树高度不变实现bool isInserttrue; //是否插入成功 bool isTaller; //树高度是否增加 TreeNode* InsertAVL(TreeNode* t,DataType key){ if(!t){ TreeNode* pnew TreeNode; p-datakey; p-leftp-rightnullptr; p-bf0; isTallerture; //树高增加 return p; } if(keyt-data){ //递归在左子树插入 t-leftInsertAVL(t-left,key); if(!isInsert)return t; //插入失败就不做处理直接返回 if(isTaller){ if(t-bf1){ t-bf0; isTallerfalse; return LeftAdjust(t); } else if(t-bf0){ t-bf1; isTallertrue; } else if(t-bf-1){ t-bf0; isTallerfalse; } } } else if(keyt-data){ //递归在右子树插入 t-rightInsert(t-right,key); if(!isInsert)return t; //插入失败就直接返回 if(isTaller){ if(t-bf-1){ t-bf0; isTaller0; return RightAdjust(t); } else if(t-bf0){ t-bf-1; isTallertrue; } else if(t-bf1){ t-bf0; isTallerfalse; } } } else { //插入失败 isInsertfalse; isTallerfalse; } return t; }AVL树的删除也是继承二叉树的删除思想思路二叉树的删除有两种情况要删除的节点左右子树至少有一个为空让另一个儿子替换要删除的节点即便另一个儿子也是空的要删除的节点左右子树都不空对于一般的二叉树来说用左子树的最小值或右子树的最大值来替换该节点的方案都可以但对于AVL树需要先检查该节点的bf若该节点的bf为1说明左子树比右子树高假设找右子树的最大值与该节点交换data再删除右子树原来最大值的那个节点可能造成右子树高度减小导致该节点的bf大于1所以选择左子树的最小值与该节点交换若该节点的bf为0处理方式就设置为与bf为1时一样若该节点的bf为-1同理需要找右子树的最大值与该节点交换与插入类似需要一个isShorter来记录树的高度是否降低每次递归的调用子树的删除函数后检查isShorter是否为真若isShorter为真说明删除后的子树高度减小了需要再检查当前节点的bf根据bf-101和在哪个子树上删除左子树右子树来决定删除后以该节点为根节点的子树高度是否减小删除后该节点的bf如何改变实现bool isDeleteture; bool isShorter; TreeNode* DeleteAVL(TreeNode* t,key){ if(!t){ //删除失败 isDeletefalse; isShorterfalse; return t; } if(keyt-left){ t-leftDeleteAVL(t-left,key); if(!isDelete)return t; //删除失败直接返回 if(isShorter){ if(t-bf-1){ t-bf0; isShorterfalse; return RightAdjust(t); } else if(t-bf0){ t-bf-1; isShorterfalse; } else if(t-bf1){ t-bf0; isShortertrue; } } } else if(keyt-left){ t-rightDeleteAVL(t-right,key); if(!isDelete)return t; //删除失败直接返回 if(isShorter){ if(t-bf1){ t-bf0; isShorterfalse; return LeftAdjust(t); } else if(t-bf0){ t-bf1; isShorterfalse; } else if(t-bf-1){ t-bf0; isShortertrue; } } } else { //找到了需要删除的节点 if(t-leftt-right){ //左右子树都存在 if(t-bf1){ TreeNode* leftMinfindMin(t-left); t-dataleft-data; t-leftDelete(t-left,left-data); if(isShorter)t-bf0; //根据isShorter修改bf值 } else if(t-bf0){ TreeNode* leftMinfindMin(t-left); t-dataleft-data; t-leftDelete(t-left,left-data); if(isShorter)t-bf-1; //根据isShorter修改bf值 } else if(t-bf-1){ TreeNode* rightMaxfindMax(t-right); t-datarightMax-data; t-rightDelete(t-right,rightMax-data); if(isShorter)t-bf0; //根据isShorter修改bf值 } } else if(t-left){ //左子树存在 TreeNode* tmpt; tt-left; delete tmp; isShorttrue; } else { //右子树存在(即便为空) TreeNode* tmpt; tt-right; delete tmp; isShortture; } } return t; }由BST建AVL利用二叉查找树已经有序的特性通过对原来的BST中序遍历得到有序序列从小到大通过有序序列递归地建树每次选取序列段中的下标在中间的节点进行插入然后递归地通过这个节点在序列中的左边的序列段建立这个节点的左子树通过这个节点在序列中的右边的序列段建立这个节点的右子树假设给定一颗二叉查找树root需要建立avl树vectorTreeNode* inorder; //记录有序序列 TreeNode* getAVL(TreeNode* root){ InOrderTraversal(root); return buildAVL(0,inorder.size()-1); } void InOrderTraversal(TreeNode* root){ InOrderTraversal(root-left); inorder.push_back(); InOrderTraversal(root-right); } TreeNode* buildAVL(int left,int right){ if(leftright)return nullptr; int middle(leftright)/2; TreeNode* tnew TreeNode; t-valinorder[middle]-val; t-leftbuildAVL(left,middle-1); t-rightbuildAVL(middle1,right); return t; }