天津智能网站建设哪里有,东莞寮步招聘网最新招聘信息,青色系网站,亿方云企业网盘目录 一、AVL树的概念
二、AVL树的性质
三、AVL树节点的定义
四、AVL树的插入
4.1 parent的平衡因子为0
4.2 parent的平衡因子为1或-1
4.3 parent的平衡因子为2或-2
4.3.1 左单旋
4.3.2 右单旋
4.3.3 先左单旋再右单旋
4.3.4 先右单旋再左单旋
4.4 插入节点完整代码…目录 一、AVL树的概念
二、AVL树的性质
三、AVL树节点的定义
四、AVL树的插入
4.1 parent的平衡因子为0
4.2 parent的平衡因子为1或-1
4.3 parent的平衡因子为2或-2
4.3.1 左单旋
4.3.2 右单旋
4.3.3 先左单旋再右单旋
4.3.4 先右单旋再左单旋
4.4 插入节点完整代码
五、AVL树判断是否平衡
六、AVL树的验证 一、AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
二、AVL树的性质
1、空树也是一颗AVL树
2、它的左右子树都是AVL树
3、左右子树高度差平衡因子的绝对值不超过1
4、如果一颗二叉搜索树是高度平衡的它就是AVL树。如果它由N个节点其高度可保持在O(log2N)搜索时间复杂度为O(log2N)。 三、AVL树节点的定义
templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(const pairK, V kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0)//平衡因子初始为0{}pairK, V _kv;AVLTreeNode* _parent;AVLTreeNode* _left;AVLTreeNode* _right;int _bf;//平衡因子 —— balance factor
};
四、AVL树的插入
AVL树的插入分为两大步
1、新建节点插入到正确的位置使之符合二叉搜索树的性质
如果插入到右边则平衡因子加1如果插入到左边平衡因子减1
2、判断平衡因子是否合法不合法则调整节点旋转
插入完成后平衡因子有以下几种情况
4.1 parent的平衡因子为0
如果此时parent的平衡因子为0那么之前的平衡因子是1或-1这棵树的高度不会变不用向上更新插入完成。
4.2 parent的平衡因子为1或-1
如果此时parent的平衡因子为1或-1那么之前的平衡因子为0高度改变了需要向上更新。
4.3 parent的平衡因子为2或-2
如果此时parent的平衡因子为2或-2那么需要通过旋转调平衡。
4.3.1 左单旋 void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;cur-_left parent;if (curleft)curleft-_parent parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){cur-_parent nullptr;_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;//更新平衡因子}
4.3.2 右单旋 void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;cur-_right parent;if (curright)curright-_parent parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){cur-_parent nullptr;_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}
4.3.3 先左单旋再右单旋 void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(parent-_left);RotateR(parent);//更新平衡因子if (bf 0){parent-_bf curright-_bf cur-_bf 0;}else if (bf 1){parent-_bf 0;cur-_bf -1;curright 0;}else if (bf -1){parent-_bf 1;cur-_bf 0;curright 0;}else{assert(false);}}
4.3.4 先右单旋再左单旋 void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf;RotateR(parent-_right);RotateL(parent);//更新平衡因子if (bf 0){parent-_bf curleft-_bf cur-_bf 0;}else if (bf 1){parent-_bf -1;cur-_bf 0;curleft 0;}else if (bf -1){parent-_bf 0;cur-_bf 1;curleft 0;}else{assert(false);}}
4.4 插入节点完整代码 bool insert(const pairK, V kv){//如果root为空if (_root nullptr){_root new Node(kv);return true;}//插入Node* cur _root;Node* parent cur;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//刚开始忘记写了//插入完成开始判断是否平衡//最坏走到根就不再判断了根的parent为空while (parent){//更新平衡因子if (parent-_left cur){parent-_bf--;}else{parent-_bf;}//如果此时parent的平衡因子为0那么之前的平衡因子是1或-1这棵树的高度不会变不用向上更新if (parent-_bf 0){break;}//如果此时parent的平衡因子为1或-1那么之前的平衡因子为0高度改变了需要向上更新else if (parent-_bf 1 || parent-_bf -1){//向上更新cur parent;parent parent-_parent;}//如果此时parent的平衡因子为2或-2那么需要通过旋转调平衡else if (parent-_bf 2 || parent-_bf -2){//左单旋if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//右单旋if(parent-_bf -2 cur-_bf -1){RotateR(parent);}//先右单旋再左单旋if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}//先左单旋再右单旋if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;//忘记写了}else{assert(false);}}return true;}
五、AVL树判断是否平衡 bool isBalance(){return _isBalance(_root);}int Height(Node* root){if (root nullptr)return 0;int lh Height(root-_left);int rh Height(root-_right);return lh rh ? lh 1 : rh 1;}bool _isBalance(Node* root){if (root nullptr)return true;int leftHeight Height(root-_left);int rightHeight Height(root-_right);int diff abs(rightHeight - leftHeight);return diff 1 _isBalance(root-_left) _isBalance(root-_right);}
六、AVL树的验证
int main()
{//常规场景AVLTreeint, int* root1 new AVLTreeint, int();int a1[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };for (auto e : a1){root1-insert(make_pair(e, e));}root1-InOrder();cout isBalance: root1-isBalance() endl;//特殊场景AVLTreeint, int* root2 new AVLTreeint, int();int a2[] { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a2){root2-insert(make_pair(e, e));}root2-InOrder();cout isBalance: root2-isBalance() endl;//随机数const int N 100000;vectorint v;v.reserve(N);srand(time(0));for (int i 0; i N; i){int n rand();v.push_back(n);}AVLTreeint, int* root3 new AVLTreeint, int();for (auto e : v){root3-insert(make_pair(e, e));}//root-InOrder();cout isBalance: root3-isBalance() endl;return 0;
}
运行结果
