一、AVL的概念AVL树最先发明的是自平衡二叉查找树AVL是一棵空树或者具备下面性质的二叉搜索树它的左右子树都是AVL树左右子树的高度差绝对值不超过1,AVL树是一棵高度平衡二叉搜索树通过控制高度控制平衡AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis两个前苏联的科学家AVL树实现要引入一个平衡因子的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树高度减去左子树高度也就是说任何平衡因子等于0/1/-1AVL树不是必须需要平衡因子但是有了平衡因子可以帮助我们检查和控制树的平衡为什么AVL树要求左右子树高度差不超过1而不是0呢因为当树上的节点个数是2或者4个等等时没办法达到左右子树高度一致AVL树整体节点数和分布也完全二叉树类似高度可达至控制在logN所以增删查改效率也可以控制在OlogN相比二叉搜索树有了质的提升二、AVL树的实现2.1 AVL树的结构struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK,V* _parent; AVLTreeNodeK,V* _left; AVLTreeNodeK,V* _right; int _bf; AVLTreeNode(const pairK,V kv, AVLTreeNodeK,V* parentnullptr, AVLTreeNodeK,V* leftnullptr, AVLTreeNodeK,V* rightnullptr,int bf0) :_kv(kv) ,_parent(parent) ,_left(left) ,_right(right) ,_bf(bf) { } }; templateclass K,class V class AVLTree { typedef AVLTreeNodeK, V Node; public: AVLTree(Node* rootnullptr) :_root(root) { } private: Node* _root; };2.2 AVL的插入2.2.1 AVL树的插入过程及平衡因子更新将要插入的值按二叉搜索树的规则插入新增节点后可能会影响它的祖先的子树的高度可能会涉及到祖先节点的平衡因子更新从当前新插入的节点向上找祖先节点判断是否要更新平衡因子1当前父节点更新平衡因子后为0停止向上继续更新。因为这表明原来他的平衡因子是1/-1插入新节点后它的子树高度未改变因此它祖先的子树高度也未改变 2当前父节点更新平衡因子后为1/-1继续向上更新。因为这表明原来他的平衡因子是0插入新节点后它的子树高度改变会影响父节点的平衡因子 3当前父节点更新平衡因子后为2/-2要进行旋转。这时这个节点已经不满足AVL树的规则需进行旋转处理旋转的目标有两个1、把parent子树旋转平衡 2、降低parent子树高度恢复到插入节点以前的高度。所以插入后无需再向上更新插入结束 4不断更新更新到根根的平衡因子是1/-1就停止了更新平衡因子过程未出现问题插入结束2.2.2 AVL树的旋转树的旋转分为右单旋、左单旋、右左双旋、左右双旋总结规律要进行右单旋时cur节点的_bf-1,parent节点的_bf-2要进行左单旋时cur节点的_bf1,parent节点的_bf2要进行右左双旋时cur节点的_bf-1,parent节点的_bf2要进行左右双旋时cur节点的_bf1,parent节点的_bf-22.2.3 AVL树平衡检测AVL树平衡检测不能借助节点的平衡因子判断而应该要计算当前节点的左右子树高度差以防前面在计算平衡因子时已经出现错误。2.2.4 全部实现代码#pragma once #includeiostream #includecassert #includecmath #includevector using namespace std; templateclass K,class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK,V* _parent; AVLTreeNodeK,V* _left; AVLTreeNodeK,V* _right; int _bf; AVLTreeNode(const pairK,V kv, AVLTreeNodeK,V* parentnullptr, AVLTreeNodeK,V* leftnullptr, AVLTreeNodeK,V* rightnullptr,int bf0) :_kv(kv) ,_parent(parent) ,_left(left) ,_right(right) ,_bf(bf) { } }; templateclass K,class V class AVLTree { typedef AVLTreeNodeK, V Node; public: AVLTree(Node* rootnullptr) :_root(root) { } bool Insert(const pairK, V kv) { Node* newnode new Node(kv); if (_root nullptr) { _root newnode; return true; } Node* pcur _root; Node* parent pcur; while (pcur ! nullptr) { parent pcur; if (pcur-_kv.first kv.first) pcur pcur-_left; else if (pcur-_kv.first kv.first) pcur pcur-_right; else { delete newnode; return false; } } //开始插入 pcur newnode; if (kv.first parent-_kv.first) { parent-_right newnode; newnode-_parent parent; } else { parent-_left newnode; newnode-_parent parent; } while (parent) { if (pcur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) break; else if (parent-_bf 1 || parent-_bf -1) { pcur parent; parent pcur-_parent; } else if (parent-_bf 2 || parent-_bf -2) break; else assert(false); } pcur newnode-_parent; parent pcur-_parent; while (pcur-_bf ! 0 parent!nullptr) { if (pcur-_bf -1 parent-_bf -2)//右单旋 { RotateR(pcur); break; } else if (pcur-_bf 1 parent-_bf 2)//左单旋 { RotateL(pcur); break; } else if (pcur-_bf 1 parent-_bf -2)//左右双旋 { RotateLR(pcur); break; } else if (pcur-_bf -1 parent-_bf 2)//右左双旋 { RotateRL(pcur); break; } pcur parent; parent pcur-_parent; } return true; } Node* Find(const K key) { Node* pcur _root; while (pcur) { if (pcur-_kv.first key) pcur pcur-_left; else if (pcur-_kv.first key) pcur pcur-_left; else return pcur; } return nullptr; } Node* root() { return _root; } void Print(Node* root) { if (root nullptr) return; Print(root-_left); cout root-_kv.first : root-_kv.second ; Print(root-_right); } bool isbalance(Node* root) { if (root nullptr)return true; int lefth _height(root-_left); int righth _height(root-_right); if (abs(lefth - righth) 2) { cout root-_kv.first : root-_kv.second 高度差有问题 endl; return false; } if (righth - lefth ! root-_bf) { cout root-_kv.first : root-_kv.second 平衡因子异常 righth-lefth root-_bf endl; } return isbalance(root-_right) isbalance(root-_left); } private: int _height(Node* root) { if (root nullptr) return 0; int h max(_height(root-_left), _height(root-_right)); return h 1; } void RotateR(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_left cur-_right; if(cur-_right) cur-_right-_parent parent; cur-_parent grandpa; if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else//parent原本是树根 { _root cur; } parent-_parent cur; cur-_right parent; //更新平衡因子 parent-_bf cur-_bf 0; } void RotateL(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_right cur-_left; if(cur-_left) cur-_left-_parent parent; cur-_parent grandpa; if (grandpa) { if (grandpa-_left parent) grandpa-_left cur; else grandpa-_right cur; } else//parent原本是树根 { _root cur; } cur-_left parent; parent-_parent cur; //更新平衡因子 cur-_bf parent-_bf 0; } void RotateLR(Node* cur) { Node* parent cur-_parent; Node* subL cur; Node* subLR cur-_right; int bf subLR-_bf; RotateL(subLR); RotateR(parent-_left); if (bf 1)//在subLR右边插入 { subLR-_bf parent-_bf 0; subL-_bf -1; } else if (bf -1)//在左边插入 { subLR-_bf subLR-_bf 0; parent-_bf 1; } else//subLR自己就是新增节点 { subLR-_bf parent-_bf subL-_bf 0; } } void RotateRL(Node* cur) { Node* parent cur-_parent; Node* SubR cur; Node* SubRL cur-_left; int bf SubRL-_bf; RotateR(SubRL); RotateL(parent-_right); if (bf 0) { parent-_bf SubR-_bf SubRL-_bf 0; } else if (bf 1) { parent-_bf -1; SubRL-_bf SubR-_bf 0; } else { SubR-_bf 1; SubRL-_bf parent-_bf 0; } } Node* _root; }; C++进阶——AVL树实现
一、AVL的概念AVL树最先发明的是自平衡二叉查找树AVL是一棵空树或者具备下面性质的二叉搜索树它的左右子树都是AVL树左右子树的高度差绝对值不超过1,AVL树是一棵高度平衡二叉搜索树通过控制高度控制平衡AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis两个前苏联的科学家AVL树实现要引入一个平衡因子的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树高度减去左子树高度也就是说任何平衡因子等于0/1/-1AVL树不是必须需要平衡因子但是有了平衡因子可以帮助我们检查和控制树的平衡为什么AVL树要求左右子树高度差不超过1而不是0呢因为当树上的节点个数是2或者4个等等时没办法达到左右子树高度一致AVL树整体节点数和分布也完全二叉树类似高度可达至控制在logN所以增删查改效率也可以控制在OlogN相比二叉搜索树有了质的提升二、AVL树的实现2.1 AVL树的结构struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK,V* _parent; AVLTreeNodeK,V* _left; AVLTreeNodeK,V* _right; int _bf; AVLTreeNode(const pairK,V kv, AVLTreeNodeK,V* parentnullptr, AVLTreeNodeK,V* leftnullptr, AVLTreeNodeK,V* rightnullptr,int bf0) :_kv(kv) ,_parent(parent) ,_left(left) ,_right(right) ,_bf(bf) { } }; templateclass K,class V class AVLTree { typedef AVLTreeNodeK, V Node; public: AVLTree(Node* rootnullptr) :_root(root) { } private: Node* _root; };2.2 AVL的插入2.2.1 AVL树的插入过程及平衡因子更新将要插入的值按二叉搜索树的规则插入新增节点后可能会影响它的祖先的子树的高度可能会涉及到祖先节点的平衡因子更新从当前新插入的节点向上找祖先节点判断是否要更新平衡因子1当前父节点更新平衡因子后为0停止向上继续更新。因为这表明原来他的平衡因子是1/-1插入新节点后它的子树高度未改变因此它祖先的子树高度也未改变 2当前父节点更新平衡因子后为1/-1继续向上更新。因为这表明原来他的平衡因子是0插入新节点后它的子树高度改变会影响父节点的平衡因子 3当前父节点更新平衡因子后为2/-2要进行旋转。这时这个节点已经不满足AVL树的规则需进行旋转处理旋转的目标有两个1、把parent子树旋转平衡 2、降低parent子树高度恢复到插入节点以前的高度。所以插入后无需再向上更新插入结束 4不断更新更新到根根的平衡因子是1/-1就停止了更新平衡因子过程未出现问题插入结束2.2.2 AVL树的旋转树的旋转分为右单旋、左单旋、右左双旋、左右双旋总结规律要进行右单旋时cur节点的_bf-1,parent节点的_bf-2要进行左单旋时cur节点的_bf1,parent节点的_bf2要进行右左双旋时cur节点的_bf-1,parent节点的_bf2要进行左右双旋时cur节点的_bf1,parent节点的_bf-22.2.3 AVL树平衡检测AVL树平衡检测不能借助节点的平衡因子判断而应该要计算当前节点的左右子树高度差以防前面在计算平衡因子时已经出现错误。2.2.4 全部实现代码#pragma once #includeiostream #includecassert #includecmath #includevector using namespace std; templateclass K,class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK,V* _parent; AVLTreeNodeK,V* _left; AVLTreeNodeK,V* _right; int _bf; AVLTreeNode(const pairK,V kv, AVLTreeNodeK,V* parentnullptr, AVLTreeNodeK,V* leftnullptr, AVLTreeNodeK,V* rightnullptr,int bf0) :_kv(kv) ,_parent(parent) ,_left(left) ,_right(right) ,_bf(bf) { } }; templateclass K,class V class AVLTree { typedef AVLTreeNodeK, V Node; public: AVLTree(Node* rootnullptr) :_root(root) { } bool Insert(const pairK, V kv) { Node* newnode new Node(kv); if (_root nullptr) { _root newnode; return true; } Node* pcur _root; Node* parent pcur; while (pcur ! nullptr) { parent pcur; if (pcur-_kv.first kv.first) pcur pcur-_left; else if (pcur-_kv.first kv.first) pcur pcur-_right; else { delete newnode; return false; } } //开始插入 pcur newnode; if (kv.first parent-_kv.first) { parent-_right newnode; newnode-_parent parent; } else { parent-_left newnode; newnode-_parent parent; } while (parent) { if (pcur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) break; else if (parent-_bf 1 || parent-_bf -1) { pcur parent; parent pcur-_parent; } else if (parent-_bf 2 || parent-_bf -2) break; else assert(false); } pcur newnode-_parent; parent pcur-_parent; while (pcur-_bf ! 0 parent!nullptr) { if (pcur-_bf -1 parent-_bf -2)//右单旋 { RotateR(pcur); break; } else if (pcur-_bf 1 parent-_bf 2)//左单旋 { RotateL(pcur); break; } else if (pcur-_bf 1 parent-_bf -2)//左右双旋 { RotateLR(pcur); break; } else if (pcur-_bf -1 parent-_bf 2)//右左双旋 { RotateRL(pcur); break; } pcur parent; parent pcur-_parent; } return true; } Node* Find(const K key) { Node* pcur _root; while (pcur) { if (pcur-_kv.first key) pcur pcur-_left; else if (pcur-_kv.first key) pcur pcur-_left; else return pcur; } return nullptr; } Node* root() { return _root; } void Print(Node* root) { if (root nullptr) return; Print(root-_left); cout root-_kv.first : root-_kv.second ; Print(root-_right); } bool isbalance(Node* root) { if (root nullptr)return true; int lefth _height(root-_left); int righth _height(root-_right); if (abs(lefth - righth) 2) { cout root-_kv.first : root-_kv.second 高度差有问题 endl; return false; } if (righth - lefth ! root-_bf) { cout root-_kv.first : root-_kv.second 平衡因子异常 righth-lefth root-_bf endl; } return isbalance(root-_right) isbalance(root-_left); } private: int _height(Node* root) { if (root nullptr) return 0; int h max(_height(root-_left), _height(root-_right)); return h 1; } void RotateR(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_left cur-_right; if(cur-_right) cur-_right-_parent parent; cur-_parent grandpa; if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else//parent原本是树根 { _root cur; } parent-_parent cur; cur-_right parent; //更新平衡因子 parent-_bf cur-_bf 0; } void RotateL(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_right cur-_left; if(cur-_left) cur-_left-_parent parent; cur-_parent grandpa; if (grandpa) { if (grandpa-_left parent) grandpa-_left cur; else grandpa-_right cur; } else//parent原本是树根 { _root cur; } cur-_left parent; parent-_parent cur; //更新平衡因子 cur-_bf parent-_bf 0; } void RotateLR(Node* cur) { Node* parent cur-_parent; Node* subL cur; Node* subLR cur-_right; int bf subLR-_bf; RotateL(subLR); RotateR(parent-_left); if (bf 1)//在subLR右边插入 { subLR-_bf parent-_bf 0; subL-_bf -1; } else if (bf -1)//在左边插入 { subLR-_bf subLR-_bf 0; parent-_bf 1; } else//subLR自己就是新增节点 { subLR-_bf parent-_bf subL-_bf 0; } } void RotateRL(Node* cur) { Node* parent cur-_parent; Node* SubR cur; Node* SubRL cur-_left; int bf SubRL-_bf; RotateR(SubRL); RotateL(parent-_right); if (bf 0) { parent-_bf SubR-_bf SubRL-_bf 0; } else if (bf 1) { parent-_bf -1; SubRL-_bf SubR-_bf 0; } else { SubR-_bf 1; SubRL-_bf parent-_bf 0; } } Node* _root; };