重点实验室网站建设的研究现状,wordpress添加html页面,wordpress建立移动m站,网站建设项目的工作分解0x00、平衡二叉树的定义平衡二叉树(AVL树)是一种特殊的二叉搜索树#xff0c;只是在二叉搜索树上增加了对平衡的需求。假如一棵二叉搜索树#xff0c;按照“1,2,3,4,5”的顺序插入数据#xff0c;会发现二叉树甚至变成了一个线性的链表状结构#xff0c;这样查…0x00、平衡二叉树的定义平衡二叉树(AVL树)是一种特殊的二叉搜索树只是在二叉搜索树上增加了对平衡的需求。假如一棵二叉搜索树按照“1,2,3,4,5”的顺序插入数据会发现二叉树甚至变成了一个线性的链表状结构这样查找数据的时间复杂度就会达到O(n)为了优化这一点使二叉查找树时间复杂度保持O(log n)的级别我们就需要调整树的插入方式使之保持住树的结构。这里引入一个定义平衡因子二叉树的某个节点的左子树与右子树高度之差称为结点的平衡因子。而平衡二叉树就是要保证平衡因子绝对值不能超过1。也就是左子树高度比右子树高度最多大1。0x01、平衡二叉树的C语言实现首先定义平衡二叉树这和定义二叉搜索树有些不同定义的结构体必须加上当前子树的高度。也就是这样struct node{int data; //数据域int height; //当前子树高度node* lchild, *rchild; //左右孩子};这样定义的好处是方便上一节点计算平衡因子。计算平衡因子之前我们先定义计算高度的函数直接返回root-height即可。如果root为NULL说明是叶子节点返回0即可int getHeight(node* root){return root NULL ? 0 : root-height;}接着我们计算平衡因子即左子树比右子树高了多少int getBalanceFactor(node* root){return getHeight(root-lchild) - getHeight(root-rchild);}当我们执行了插入操作二叉树发生改变的时候我们需要重新计算高度。某节点的高度值等于左右子树高度值最大的加上1。(这是高度值的定义)更新高度值void updateHeight(node* root){root-height max(getHeight(root-lchild), getHeight(root-rchild)) 1;}0x02、平衡二叉树的查找AVL树的查找与一般二叉搜索树的查找方法一样。代码如下void search(node* root, int data){if(!root) return; //查找失败if(root-data data)//找到了printf(%d, root-data);if(root-data data) //大了访问左节点search(root-lchild, data);else search(root-rchild, data);}0x03、平衡二叉树的插入操作平衡二叉树的插入操作较为复杂我们为了保持二叉树的平衡状态就要在二叉树失衡的时候对二叉树进行旋转。常见的旋转方式有LL型(单次右旋)、RR型(单次左旋)、LR型(先左旋再右旋)、RL型(先右旋再左旋)下面我们进行详细介绍1、LL型(单次右旋)假设一棵平衡二叉树再插入数据后成了这个样子图中的 4 和 12 的高度分别是 3 和 1 高度差为 2 此时二叉树不平衡了。对于这种由根节点的左子树的左子树造成平衡因子为2的失衡我们要使用LL型旋转即单次右旋使其平衡。正确的旋转方式是使原二叉树的 根节点(K2) 的 左孩子(k1) 做为 新根节点新根节点(k1) 原来的 右子树(Y) 做为 原来的根节点(K2) 的左子树如果记不住的话可以按照这个思路来记忆既然左边高度比右边高就让左子树的根节点称为新根这样高度就减小了1我们把左子树K1揪起来让原根节点k2掉下去这样K1就多了一个孩子而X小于K1K2大于K1Y大于K1且Y小于K2这样把Y拽下来插到K2的左边仍然符合二叉搜索树的规则而且还处理好了K1的关系多么完美转转后K1和K2(新根与原来的根)的高度发生了变化而XYZ(三个子树)没有发生变化所以我们只需要更新K1和K2的高度值即可。用C语言实现就是void LLrotation(node* root){node* temp root-lchild; //让tempK1root-lchild temp-rchild; //让root的左节点变为Ytemp-rchild root; //让新根K1的右节点指向K2//以上旋转完毕updateHeight(temp); //更新新根的节点高度updateHeight(root); //更新老根的节点高度root temp; //把树的根换成我们定义的新根}2、RR型(单次左旋)假设一棵二叉树插入数据后的状态很显然失衡了。平衡因子为-2。对于这种根节点的右子树的右子树造成平衡因子为-2的失衡我们采用RR旋转即单次左旋。单次左旋的思路就是单次右旋倒过来想我们先将原根节点的右节点K2当做新根将K2的左子树当做原根K1的右子树。同样的只有K1和K2的高度发生了变化所以我们只需要更新K1和K2的高度即可。C语言实现void RRrotation(node* root){node* temp root-rchild; //另tempK2root-rchild temp-lchild; //旧根的右节点为新根的左节点temp-lchild root; //新根的右节点等于旧根//以上旋转完毕updateHeight(temp); //更新节点高度updateHeight(root);root temp; //重赋值}3、LR型(先单次左旋后单次右旋)一棵二叉树插入数据后形成了这个鬼样子4的高度为3 而12的高度为1平衡因子即高度差为2这是由于根节点的左子树的右子树造成了平衡因子为2的失衡通常采用LR型旋转即先左旋后右旋。先左旋也就是让K3的左孩子单次左旋以K1为根节点进行单次左旋使得K2成为根节点K1成为K2的左节点K2原来的左节点B成为K1的右节点。这样就完成了单次左旋接着对左旋后的二叉树以K3为根节点进行单次右旋让K3的左节点K2成为新根K2的右孩子C成为K3的左孩子让K3做K2的右孩子。这里K1、K2、K3的高度均发生了变化ABCD的高度没有发生变化。说起来很麻烦其实实现起来很简单。因为我们有了前面LL旋转和RR旋转的基础直接对子树操作即可。C语言实现void LRrotation(node* root){RRrotation(root-lchild); //先对根节点的左孩子单次左旋LLrotation(root);}4、RL型(先单次右旋后单次左旋)二叉树数据插入后此时的状态是由于根节点的右节点的左子树造成了平衡因子为-2的失衡我们通常采用RL型旋转即先单次右旋后单次左旋。其实就是把LR倒过来啦不做详细解释了。(敲键盘敲的手指好痛呜呜呜~~~~(_C语言实现void RLrotation(node* root){LLrotation(root-rchild); //先对根节点的左孩子单次左旋RRrotation(root);}写了这么多总结一下吧。根据这个表格进行判断AVL树以何种旋转类型保持平衡树型判定条件调整方法LL(单次右旋)BF(root) 2BF(root-lchild) 1对root单次右旋RR(单次左旋)BF(root) -2BF(root-rchild) -1对root单次左旋LR(先左后右)BF(root) 2BF(root-lchild) -1对root-lchild进行左旋再对root进行右旋RL(先右后左)BF(root) -2BF(root-rchild) 1对root-rchild进行右旋再对root进行左旋*BF代表平衡因子0x04、二叉平衡树的插入还记得二叉搜索树是怎样插入数据的吗void insert(node* root, int data){if(root NULL){root new node;root-data data;root-lchild root-rchild NULL;}if(root-data data)insert(root-rchild, data);else insert(root-lchild, data);}这段代码是不考虑平衡关系的插入代码。我们要做的是在这串代码上稍加修改使之能及时通过旋转保证平衡关系。我们的思路是沿用上面代码进行插入插入后更新树的高度接着判断平衡因子根据平衡因子判断四种类型的旋转最后执行旋转。C语言实现void insert(node* root, int data){if(root NULL){ //插入位置root new node;root-data data;root-lchild root-rchild NULL;root-height 1; //由于插入的时候是叶子节点所以初始高度为1return;}if(root-data data){ //节点数据大往左插入insert(root-lchild, data); //继续递归寻找插入位置updataHeight(root); //因为插入了一个节点所以树根的高度会发生变化if(getBalanceFactor(root) 2) //根节点平衡因子为2if(getBalanceFactor(root-lchild) 1) //根节点左孩子平衡因子为1根据表格采用LL型LLrotation(root);else if(getBalanceFactor(root-lchild) -1) //根节点左孩子平衡因子为-1LR型LRrotation(root);}else{ //节点数据小往右插入insert(root-rchild, data);updataHeight(root);if(getBalanceFactor(root) -2){if(getBalanceFactor(root-rchild) -1) //RR型RRrotation(root)else if(getBalanceFactor(root-rchild) 1)//RL型RLrotation(root);}}}这里往左插入后只需要判断平衡因子是否为2是因为如果树之前是平衡的往左插入的时候不可能造成平衡因子为-2只有往右插入的时候才会是-2所以判断平衡因子 是否为-2就多余了。
