建设局网站打不开,中文域名的网站,竞价代运营外包公司,wordpress创建页面路由目录前言一、AVL树二、AVL树的底层实现1. 结点类型的定义2. AVL树的定义3. 查找函数4. 插入函数(重难点)三、判断平衡树的方法前言 AVL树其实是在搜索树的基础上加上一些限制因素#xff0c;从而使搜索树的结构保持相对平衡#xff0c;通过前面我们对二叉搜索树的学习#x…
目录前言一、AVL树二、AVL树的底层实现1. 结点类型的定义2. AVL树的定义3. 查找函数4. 插入函数(重难点)三、判断平衡树的方法前言 AVL树其实是在搜索树的基础上加上一些限制因素从而使搜索树的结构保持相对平衡通过前面我们对二叉搜索树的学习我们知道如果我们向一棵二叉搜索树中插入一些有序的数据那么整棵树就会偏向于一边从而使整棵树失去平衡那么在查找的时候就会效率低下退化为顺序表的效率了今天我们学习的AVL树本质上就是为了解决二叉搜索树中失去平衡的问题为了控制二叉搜索树中的子树的左右子树的高度差保持相对平衡我们采取在树中的每一个结点中增加一个变量来记录每一个结点的平衡因子我们可以定义平衡因子为该子树的右子树的高度-左子树的高度。 一、AVL树
AVL树是一棵二叉搜索树并且除了具备二叉搜索树的性质还具备以下的性质
树的左右子树的高度差不超过1可以通过平衡因子进行控制树中的每一棵子树都是AVL树
二、AVL树的底层实现
1. 结点类型的定义
// AVL树的结点
template class K,class V
struct AVLTreeNode
{// 构造函数AVLTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}// 成员变量pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;// 平衡因子左右子树的高度差右子树高度-左子树高度int _bf;
};
AVL树中的结点需要包含三个指针即指向左子树的指针指向右子树的指针指向父亲结点的指针还需要一个存储数据的pair结构还需要有一个平衡因子其中的构造函数是对一个新生成的结点中的数据进行初始化新生成的结点中就是通过给定的kv来初始化_kv然后左子树和右子树和父亲结点均为空需要确定后再由外面手动更新其中的平衡因子是由该结点的左右子树的情况来决定的显然一个新的结点中不存在左右子树所以平衡因子显然为0。
2. AVL树的定义
template class K,class V
class AVLTree
{// 使用结点typedef AVLTreeNodeK, V Node;
public:// 成员函数private:// 成员变量Node* _root nullptr;
};和前面学习的树型结构的实现一样刚开始默认为空树所以_root给了一个缺省值在AVL树的类中需要使用到树的结点所以为了方便表示可以将树的结点进行重定义。
3. 查找函数
查找函数的实现比较简单和二叉搜索树中的查找函数的实现几乎一致只是需要知道这里的数据是pair类型pair类型中有first和second其中first是keysecond是value外面需要通过key去进行查找也就是需要通过kv.first去进行比较。 // 查找函数bool Find(const pairK, V kv){Node* cur _root;while (cur){if (kv.first cur-_kv.first){// 左子树找cur cur-_left;}else if(kv.firstcur-_kv.first){// 右子树找cur cur-_right;}else{// 找到了return true;}}return false;}4. 插入函数(重难点)
AVL树的插入函数的底层其实首先是按照搜索树的规则进行插入然后再通过平衡因子的调整使整棵树的高度保持相对平衡。
插入的过程
按照搜索树的规则进行插入更新平衡因子最坏的情况需要沿着路径一直更新到根如果孩子是插入在左边则父亲的平衡因子–如果孩子是插入在父亲的右边则平衡因子当父亲的平衡因子更新之后需要根据父亲更新后的平衡因子确定作何调整此时需要进行分类讨论
更新后父亲的平衡因子为0说明更新前父亲的平衡因子是1或者-1当更新前父亲的平衡因子是1使说明这棵子树的右子树比较高孩子插入在左子树上所以父亲的高度没有发生变化不需要继续更新当更新前父亲的平衡因子是-1时说明父亲的左子树比较高此时孩子插入在父亲的右子树上父亲的高度保持不变所以不需要更新。更新后父亲的平衡因子是1或者-1说明更新前父亲的平衡因子是0如果更新后父亲的平衡因子变成1说明孩子插入在父亲的右子树上导致此时父亲的右子树变高所以需要继续往上更新。如果更新后父亲的平衡因子变成-1说明孩子插入在父亲的左子树上导致父亲的左子树变高所以需要继续往上更新往上迭代的方式先更新cur结点再通过cur结点算其父亲。更新后父亲的平衡因子是2或者-2此时树的平衡因子不符合AVL树的规则需要进行调整旋转下面重点介绍四种旋转方式。 左旋适用于旋转的子树是整体是右边比较高首先需要先保存一些关键的结点指针分别是通过parent计算得出的爷爷结点(pparent)右子树(subR)右子树的左孩子(subRL)旋转的过程中需要注意两个细节parent可能是整棵树中的某一棵子树也可能是整棵树的根节点subRL不一定存在。在将parent-_right指向subRL之后需要更新subRL-_parent但是subRL不一定存在所以此时需要先判断一下。如果parent是根节点则旋转之后需要更新根节点为subR并且将subR-_parent指向nullptr。如果parent不是根则此时pparent结点就会发挥作用需要先判断parent是pparent的左孩子还是右孩子以确定是让pparent-_left还是pparent-_right托管subR然后再更新sub-_parent指向pparent。最后还需要更新平衡因子左旋的过程中动的只是parent和subR的孩子所以只需要更新这两个结点并且左旋的结果是使得它们均平衡所以最终的平衡因子都是0。右旋右旋和左旋是非常类似的首先需要先保存一些关键的结点指针通过parent计算得出的pparent(parent的父亲)subL(parent的左孩子)subLR(subL的右孩子)。旋转的过程中同样需要注意两个细节parent可能是整棵树的根节点也可能只是某一棵子树的根节点subLR可能存在也可能不存在。如果subLR不存在则不需要更新subRL-_parent。判断parent如果parent是整棵树的根节点则需要更新根节点为subL然后将根节点的父亲指向空指针如果parent不是根节点则此时pparent就会起作用此时判断parent是pparent-_left还是pparent-_right以决定让pparent-_left还是pparent-_right托管subL然后再更新subL-_parent指向pparent。最后更新平衡因子和左旋过程类似该过程中只是动了parent和subL的孩子所以只需要更新这两个结点并且最终都是平衡所以最终的平衡因子都是0。左右双旋这个双旋适合于parent的右子树高cur的左子树高的情况先保存一些关键的结点subR(parent-_right)subRL(subR-_left)旋转的过程首先让cur右旋使整棵子树保持右边高然后再让parent进行左旋。双旋之后subRL会到根的位置parent到根的左子树subR到根的右子树可以通过画图进行分析,最后调整平衡因子调整平衡因子需要根据旋转前的subRL的平衡因子保存为bf的情况进行分类讨论。如果bf 0则subRL是新插入的结点此时parent,subR,subRL的平衡因子都更新成0。 如果bf -1则新节点插入在subRL的左子树旋转过程中这个新节点会分给左边(parent)所以左边的平衡因子会被平衡故最终的平衡因子为parent-_bf 0,subR-_bf 1,subRL-_bf 0。如果bf 1则新结点插入在subR的右子树旋转过程中这个新节点会分给右边(subR)所以最终右边的平衡因子会被平衡故最终的平衡因子为parent-_bf -1,subR-_bf 0,subRL-_bf 0。右左双旋这个双旋适合于parent的左子树高cur的右子树高的情况先保存一些关键的结点:subL(parent-_left),subLR(parent-_left-_right),旋转过程先对subL进行左旋转化为整体的左子树比较高再对整体进行右旋使整棵树保持相对平衡。旋转的结果subLR到根的位置,parent到根的右子树subL到根的左子树再通过旋转前subLR的平衡因子(保存为bf)进行分类讨论如果bf 0则说明subLR是新插入的结点最终的平衡因子parent-_bf 0,subL-_bf 0,subLR-_bf 0,如果bf -1则说明新结点插入在subLR的左边这个新结点在旋转的过程中会分给左边(subL)所以左边的平衡因子会被平衡故最终的平衡因子为parent-_bf 1,subL-_bf 0,subLR-_bf 0如果bf 1说明新插入的结点插入在subLR的右边这个新节点在旋转的过程中会分给右边(parent)右边的平衡因子会被平衡所以最终的平衡因子为parent-_bf 0,subL-_bf -1,subLR-_bf 0 下面给出上述讲解过程中需要用到的操作的代码
左旋
// 左旋void RotateL(Node* parent){// 保存一些关键的结点指针Node* pparent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;if (parent _root){// parent是根_root subR;_root-_parent nullptr;}else{// parent不是根if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}// 更新平衡因子parent-_bf 0;subR-_bf 0;}右旋
// 右旋void RotateR(Node* parent){// 保存一些关键结点Node* pparent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;// 判断parent是否为根if (parent _root){// parent为根_root subL;_root-_parent nullptr;}else{// parent不是根if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}// 更新平衡因子parent-_bf 0;subL-_bf 0;}左右双旋
// 先左旋再右旋void RotateLR(Node* parent){// 先保存一些关键信息Node* subL parent-_left;Node* subLR subL-_right;// 旋转前先保存subLR的平衡因子int bf subLR-_bf;// 旋转RotateL(subL);RotateR(parent);// 更新平衡因子if (bf 0){// subLR就算新插入的结点parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else if (bf -1){// 新插入的结点插入在subLR的左边parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){// 新插入的结点插入在subLR的右边parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{// 其他错误assert(false);}}右左双旋
// 先右旋再左旋void RotateRL(Node* parent){// 保存一些关键信息Node* subR parent-_right;Node* subRL subR-_left;// 保存subRL的平衡因子int bf subRL-_bf;// 旋转RotateR(subR);RotateL(parent);// 更新平衡因子if (bf 0){// subRL是新插入的结点parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf -1){// 新插入的结点插入在subRL的左边parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){// 新插入的结点插入在subRL的右边parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{// 其他错误assert(false);}}三、判断平衡树的方法
思路采用递归的方法先判断当前树是否为平衡树本节采用平衡因子进行判断如果当前为平衡树则继续递归判断左子树和右子树是否为平衡树
代码
// 求树的高度的子函数size_t _TreeHeight(Node* root){if (root nullptr){// 空树return 0;}// 非空树// 先算左子树的高度size_t LeftHeight _TreeHeight(root-_left);// 再算右子树的高度size_t RightHeight _TreeHeight(root-_right);return LeftHeight RightHeight ? LeftHeight 1 : RightHeight 1;}// 判断平衡树的子函数bool _IsBalanceTree(Node* root){if (root nullptr){// 空树return true;}// 先算左子树高度size_t LeftHeight _TreeHeight(root-_left);// 再算右子树高度size_t RightHeight _TreeHeight(root-_right);// 计算平衡因子int bf RightHeight - LeftHeight;if (abs(bf) 1){cout 树失衡不断平衡树 endl;return false;}if (bf ! root-_bf){cout 平衡因子于实际不符合不是平衡树 endl;return false;}// 递归判断左右子树return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}// 判断平衡树bool IsBalanceTree(){return _IsBalanceTree(_root);}
