婚纱摄影网站设计案例,网站做的自适应体验差,百度河南代理商,wordpress内置分页方法目录 1.AVL树的概念2.AVL树模拟实现2.1AVL树节点的定义2.2AVL的插入2.3AVL树的旋转2.3.1左单旋2.3.2右单旋2.3.3右左双旋2.3.3.1旋转情况分析2.3.3.2平衡因子更新分析 2.3.4右左双旋2.3.4.1旋转情况分析2.3.4.2平衡因子更新分析 2.3.5AVL树的验证 3.AVL模拟实现源码4.总结 1.AV… 目录 1.AVL树的概念2.AVL树模拟实现2.1AVL树节点的定义2.2AVL的插入2.3AVL树的旋转2.3.1左单旋2.3.2右单旋2.3.3右左双旋2.3.3.1旋转情况分析2.3.3.2平衡因子更新分析 2.3.4右左双旋2.3.4.1旋转情况分析2.3.4.2平衡因子更新分析 2.3.5AVL树的验证 3.AVL模拟实现源码4.总结 1.AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1需要对树中的结点进行调整即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树左右子树高度之差简称平衡因子的绝对值不超过1-1/0/1 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n) 搜索时间复杂度O( l o g 2 n log_2 n log2n)
2.AVL树模拟实现
2.1AVL树节点的定义
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left; //该节点的左孩子AVLTreeNodeK, V* _right; //该节点的右孩子AVLTreeNodeK, V* _parent; //该节点的双亲int _bf;//该节点的平衡因子AVLTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};2.2AVL的插入
假设下面这棵树是我们最开始AVL树接下来我们需要对其进行节点的插入并针对不同的情况有不同的处理情况 1.新增节点在parent节点的左边parent的平衡因子减一减减 2.新增节点在parent节点的右边parent的平衡因子加一加加 3.更新parent平衡因子0说明parent所在的子树的高度不变不会再影响祖先不用继续沿着到root的路径继续往上更新插入结束 4.更新后parent平衡因子1 or -1说明parent所在的子树的高度变化会再影响祖先需要继续沿着到root的路径继续往上更新 5.更新后parent平衡因子2 or -2说明parent所在的子树的高度变化且不平衡对parent所在子树进行旋转让子树平衡插入结束涉及旋转下面将分情况进行讲解 6.更新到根节点没有出现parent平衡因子2 or -2的情况更新结束 2.3AVL树的旋转
旋转的时候涉及的问题 旋转之后的树需要满足两个条件1.保持这棵树是二叉搜索树2.变成平衡树AVL树且降低这个子树的高度 2.3.1左单旋
当更新parent30节点的平衡因子为2cur60节点的平衡因子为1造成parent30所在子树右边高需要进行左单旋 以下是h等于0和h等于1的具象图 根据上面两种右边子树比较高的情况需要将cur的左子树链接成为parent的右子树让parent链接成为cur的左子树。情况一插入之前AVL树高度为1插入节点后树高度为2旋转之后树高度为1且达到平衡不用继续沿着到root的路径继续往上更新插入结束情况二插入之前AVL树高度为2插入节点后树高度为3旋转之后树高度为2且达到平衡不用继续沿着到root的路径继续往上更新插入结束。 代码如下
void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;//curleft成为parent的右边parent-_right curleft;//curleft可能为空if (curleft){//改变curleft父指针的指向curleft-_parent parent;}//parent成为cur的左边cur-_left parent;//记录parent的父节点指针Node* ppnode parent-_parent;//改变parent父指针的指向parent-_parent cur;//判断parent节点是否为根节点if (parent _root){//cur成为根节点_root cur;cur-_parent nullptr;}else{//cur链接parent的父节点if (ppnode-_left parent){ppnode-_left cur;}else if (ppnode-_right parent){ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}2.3.2右单旋
当更新后parent30节点的平衡因子为-2cur60节点的平衡因子为-1造成parent30所在子树左边高需要进行右单旋 以下是h等于0和h等于1的具象图 情况一h等于0 插入之前AVL树高度为1插入节点后树高度为2旋转之后树高度为1且达到平衡不用继续沿着到root的路径继续往上更新插入结束情况二h等于1 插入之前AVL树高度为2插入节点后树高度为3旋转之后树高度为2且达到平衡不用继续沿着到root的路径继续往上更新插入结束。 分析 根据上面两种左边子树比较高的情况需要将cur的右子树链接成为parent的左子树让parent链接成为cur的左子树。局部根节点parent已经出现向左边倾斜的情况当插入节点时导致parent所在子树左边高且不平衡经过旋转后cur成为新的局部根节点cur所在子树的高度与未插入节点前的高度一致不会对上层节点造成影响达到平衡状态即cur的平衡因子为0
代码如下
void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;//curright链接成为parent的左子树parent-_left curright;if (curright){//curright不为空情况进行改变其父指针指向curright-_parent parent;}//parent链接成为cur的右子树cur-_right parent;//记录parent父指针Node* ppnode parent-_parent;//让parent父指针指向curparent-_parent cur;//cur与原parent指向父节点链接if (parent _root){//parent为根节点的情况_root cur;cur-_parent nullptr;}else{//parent为局部子树根节点//判断parent原先为局部左子树还是局部右子树if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新parent\cur的平衡因子为0parent-_bf cur-_bf 0;}2.3.3右左双旋
2.3.3.1旋转情况分析
当插入节点更新平衡因子后parent30节点的平衡因子为2cur60节点的平衡因子为-1造成parent30所在子树右边高但右子树cur节点所在子树却左边高这时候已经parent所在的子树并不是纯粹的右边高了所以只进行左单旋不能解决问题需要进行右左双旋。 以下是h等于0和h等于1的具象图 仅仅进行左单旋操作 从上面的图可以看出若parent所在子树不是完全右边高的情况对其进行左单旋操作不能使AVL树达到平衡 进行右左双旋操作 parent30所在子树右边高但右子树cur节点所在子树却左边高像一个折线需要先对以cur节点为根节点的子树进行右旋操作然后对parent节点为根节点的子树进行左旋操作经过双旋操作后curleft代替parent节点成为新的局部根节点解决了不平衡问题使左右子树高度一致达到平衡状态。 2.3.3.2平衡因子更新分析 问题 双旋调整后parent\cur\curleft三个节点的位置发生了变化这三个节点的平衡因子是否都无脑改为0呢答案不是的那么该这三个节点的平衡因子应该怎么修改呢友友们不要着急且和我一起慢慢分析吧 h0curleft-_bf 0的情况 分析 ①当curleft的平衡因子为0时curleft没有节点给cur\parent节点且cur\parent节点原本也无左右子树所以cur\parent节点的平衡因子都更新为0 h1curleft-_bf -1的情况 分析 ②当curleft的平衡因子为-1curleft没有右节点可以链接成为cur节点的左子树以cur节点为根节点右旋之后造成cur节点所在子树右边偏高所以cur节点的平衡因子更新为1curleft有左节点可以链接成为parent的右子树以parent节点为根节点左旋之后使parent节点左右子树高度一致达到平衡状态所以parent的平衡因子也更新为0 h1curleft-_bf -1的情况 分析 ③当curleft的平衡因子为1curleft有右节点可以链接成为cur节点的左子树以cur节点为根节点右旋之后使cur节点左右子树高度一致达到平衡状态所以cur节点的平衡因子更新为0curleft有左节点链接成为parent的右子树以parent节点为根节点左旋之后造成parent节点所在子树左边偏高所以parent节点的平衡因子更新为-1 代码如下
void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf;//旋转过程中curleft的bf发生变化需要提前记录//先以cur(parent-_right)为根节点右旋//再以parent为根节点左旋RotateR(cur);RotateL(parent);//针对不同curleft-_bf的情况进行处理if (bf 0){curleft-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf 1){curleft-_bf 0;cur-_bf 0;parent-_bf -1;}else if (bf -1){curleft-_bf 0;cur-_bf 1;parent-_bf 0;}else{assert(false);}}右左双旋平衡因子更新总结分析 分析上面三种平衡因子更新的情况可以看出右左双旋先右旋再左旋结果的本质是curleft的右边给了cur的左边curleft的左边给了parent的左边cur节点和parent分别成为curleft的右左子树。
2.3.4右左双旋
2.3.4.1旋转情况分析
当插入节点更新平衡因子后parent90节点的平衡因子为-2cur30节点的平衡因子为1造成parent90所在子树左边高但其左子树cur节点所在子树却左边高这时候已经parent所在的子树并不是纯粹的左边高了所以只进行右单旋不能解决问题需要进行右左双旋。 以下是h等于0和h等于1的具象图 仅仅进行右单旋操作 从上面的图可以看出若parent所在子树不是完全左边高的情况对其进行右单旋操作不能使AVL树达到平衡 进行左右双旋操作 parent90所在子树左边高但右子树cur节点所在子树却右边高像一个折线需要先对以cur节点为根节点的子树进行左旋操作然后对parent节点为根节点的子树进行右旋操作经过双旋操作后curleft代替parent节点成为新的局部根节点解决了不平衡问题使左右子树高度一致达到平衡状态。 2.3.4.2平衡因子更新分析
h0curright-_bf 0的情况 分析 ①当curright的平衡因子为0时curright没有节点给cur\parent节点且cur\parent节点原本也无左右子树所以cur\parent节点的平衡因子都更新为0 h-1curright-_bf -1的情况 分析 ②当curright的平衡因子为-1curright有左节点链接cur节点的右子树以cur节点为根节点左旋之后使cur节点左右子树高度一致达到平衡状态所以cur的平衡因子也更新为0curright没有右节点链接成为parent的左子树以parent节点为根节点右旋之后造成parent节点所在子树右边偏高所以parent节点的平衡因子更新为1 h1curright-_bf 1的情况 分析 ③当curright的平衡因子为1curright没有左节点可以链接cur节点的右子树以cur节点为根节点左旋之后造成parent节点所在子树左边偏高所以cur的平衡因子也更新为-1curright有右节点可以链接成为parent的左子树以parent节点为根节点右旋之后使parent节点左右子树高度一致达到平衡状态所以parent节点的平衡因子更新为0 代码如下
void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;//先以cur(parent-_left)为根节点左旋//再以parent为根节点右旋RotateL(parent-_left);RotateR(parent);//针对不同curright-_bf的情况进行处理if (bf 0){curright-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf -1){curright-_bf 0;cur-_bf 0;parent-_bf 1;}else if (bf 1){curright-_bf 0;cur-_bf -1;parent-_bf 0;}}左右双旋平衡因子更新总结分析 分析上面三种平衡因子更新的情况可以看出左右双旋先左旋再右旋结果的本质是curright的左边给了cur的右边curleft的右边给了parent的左边cur节点和parent分别成为curleft的左右子树。
注意 ① 双旋是先左右旋然后再右左旋单旋转的原理是一样的所以可以直接对前面左右旋函数调用然后对右左旋函数调用可增加代码复用性②双旋平衡因子单独分析进行更新与单旋转函数可以起到解耦合的作用。
2.3.5AVL树的验证
我们已经实现了AVL树插入操作的功能为了保证所写的代码正确我们可以插入数据进行检验。
使用测试AVL树平衡的函数进行数据的插入检验 int Height(){return Height(_root);}int Height(Node* root){if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr){return true;}int leftHeightHeight(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout Exception: root-_kv.first - root-_bf endl;assert(false);return false;}return abs(leftHeight - rightHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}测试1
void test()
{//普通场景int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int t;for (auto e : a){t.insert(make_pair(e, e));cout Insert: e - t.IsBalance() endl;}cout 所有数据插入成功 endl;
}代码运行结果为 测试2
void test2()
{//插入随机数const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand()i);}AVLTreeint, int t;for (auto e : v){t.insert(make_pair(e, e));}cout 所有数据插入成功 endl;
}代码运行结果如下 测试3
void test2()
{//插入随机数const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand()i);}AVLTreeint, int t;for (auto e : v){t.insert(make_pair(e, e));}cout Insert: t.IsBalance() endl;cout 所有数据插入成功 endl;
}代码运行结果如下
3.AVL模拟实现源码
#includeiostream
#includeassert.h
using namespace std;
templateclass K,class V
struct AVLTreeNode
{//建议声明顺序与初始化顺序一样AVLTreeNodeK, V* _left; //该节点的左孩子AVLTreeNodeK, V* _right; //该节点的右孩子AVLTreeNodeK, V* _parent; //该节点的双亲pairK, V _kv;int _bf;//该节点的平衡因子AVLTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};
templateclass K,class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool insert(const pairK, V kv){//插入第一个节点if (_root nullptr){_root new Node(kv);return true;}//找到合适的位置插入连接Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{//有相同节点的值则插入失败return false;}}cur new Node(kv);//关系链接if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//更新平衡因子while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}//parent所在子树高度不变会影响祖先不需要更新平衡因子插入结束if (parent-_bf 0){break;}//parent所在子树高度变化会影响祖先继续沿着到root的路径更新平衡因子else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}//parent所在子树高度变化且不平衡需要旋转parent所在子树else if (parent-_bf 2 || parent-_bf -2){//插入在parent右子树的右侧造成parent右边高if (parent-_bf 2 cur-_bf 1){RotateL(parent);//进行左单旋}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);//进行右单旋}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);//右左双旋}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);//左右双旋}break;}else{assert(false);}}}void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;//curleft成为parent的右边parent-_right curleft;//curleft可能为空if (curleft){//改变curleft父指针的指向curleft-_parent parent;}//parent成为cur的左边cur-_left parent;//记录parent的父节点指针Node* ppnode parent-_parent;//改变parent父指针的指向parent-_parent cur;//判断parent节点是否为根节点if (parent _root){//cur成为根节点_root cur;cur-_parent nullptr;}else{//cur链接parent的父节点if (ppnode-_left parent){ppnode-_left cur;}else if (ppnode-_right parent){ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;//curright链接成为parent的左子树parent-_left curright;if (curright){//curright不为空情况进行改变其父指针指向curright-_parent parent;}//parent链接成为cur的右子树cur-_right parent;//记录parent父指针Node* ppnode parent-_parent;//让parent父指针指向curparent-_parent cur;//cur与原parent指向父节点链接if (parent _root){//parent为根节点的情况_root cur;cur-_parent nullptr;}else{//parent为局部子树根节点//判断parent原先为局部左子树还是局部右子树if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新parent\cur的平衡因子为0parent-_bf cur-_bf 0;}void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf;//旋转过程中curleft的bf发生变化需要提前记录//先以cur(parent-_right)为根节点右旋//再以parent为根节点左旋RotateR(cur);RotateL(parent);if (bf 0){curleft-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf 1){curleft-_bf 0;cur-_bf 0;parent-_bf -1;}else if (bf -1){curleft-_bf 0;cur-_bf 1;parent-_bf 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;//先以cur(parent-_left)为根节点左旋//再以parent为根节点右旋RotateL(parent-_left);RotateR(parent);if (bf 0){curright-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf -1){curright-_bf 0;cur-_bf 0;parent-_bf 1;}else if (bf 1){curright-_bf 0;cur-_bf -1;parent-_bf 0;}}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr){return true;}int leftHeightHeight(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout Exception: root-_kv.first - root-_bf endl;assert(false);return false;}return abs(leftHeight - rightHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}
private:Node* _root nullptr;
};
4.总结
①AVL树的删除(了解) 因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不过与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 ② AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但一个结构经常修改就不太适合。
