企业官网建设流程全解析

AVL树

1. 概念

与红黑树的目标一样，都是控制二叉搜索树的平衡

他是由前苏联两个科学家弄出来的，分别叫​G.M.Adelson-Velsky​和​E.M.Landis，这也是AVL名称的由来

也叫自平衡二叉查找树

AVL树实现这里我们引入一个平衡因子（balancefactor）的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

平衡因子=右子树高度 - 左子树高度

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O（logN），相比二叉搜索树有了本质的提升。

‍

基本功能

插入逻辑基本跟搜索二叉树保持一致

每插入一个元素，就要从该节点向上查找节点平衡因子是否满足-1/0/1，根据情况选择旋转方式来平衡平衡因子

‍

根据平衡因子的计算规则，我们可以知道

插入左边父亲平衡因子要减减，插入右边平衡因子要加加

‍

插入

template <class K, class V> struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pair<K, V> kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }； template<class K,class V> class My_avl { typedef AVLTreeNode<K, V> Node; bool insert(const pair(K, 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->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left } else return false; } cur = new Node(kv); if (parent->_kv.first < cur) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //更新平衡因子 while (parent) { if (cur == parent->_left) { --parent->_bf; } else { ++parent->_bf; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { //继续更新 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //旋转处理 break; } else { assert(false); } } return true; } private: Node* _root = nullptr; };

旋转

旋转的规则

1. 保持搜索树的原则

2. 让搜索树从不平衡变平衡，其次降低旋转树的高度

   旋转分四种：右单旋、左单旋、、左右双旋、右左双旋

‍

右单旋

‍

#pragma once #include<assert.h> #include<iostream> #include<set> #include<map> using namespace std; namespace My_AVL { template <class K, class V> struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pair<K, V> kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; template<class K,class V> class My_avl { typedef AVLTreeNode<K, V> Node; void RotateR(Node* parent) //右旋 { Node* subL = parent->_left; Node* subLR = parent->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent->_left; Node* Parentparent = parent->_parent; subL->_right = parent; parent->_parent = subL; // parent有可能是整棵树的根，也可能是局部的⼦树 // 如果是整棵树的根，要修改_root // 如果是局部的指针要跟上⼀层链接 if (Parentparent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (Parentparent->_left == parent) { Parentparent->_left = subL; } else if (Parentparent->_right == parent) { Parentparent->_right = subl; } subL->_parent = Parentparent; } return; } private: Node* _root = nullptr; }; }

左单旋

#pragma once #include<assert.h> #include<iostream> #include<set> #include<map> using namespace std; namespace My_AVL { template <class K, class V> struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pair<K, V> kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; template<class K,class V> class My_avl { typedef AVLTreeNode<K, V> Node; void RotateL(const Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_left = subRL; if (subRL) subRL->_parent = parent->_left; Node* Parentparet = parent->_parent; subR->_right = parent; parent->_parent = subR; if (Parentparet == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (Parentparet->_left == parent) { Parentparet->_left = subR; } else if (Parentparet->_right == parent) { Parentparet->_right = subR; } subR->_parent = Parentparet; } return; } private: Node* _root = nullptr; }; }

左右双旋

不需要再重头开始写，在相应部分复用左旋和右旋代码

不是纯粹的右边高或者左边高

‍

//为了更清晰的显示，这里直接给关键代码，头文件和相关成员变量可以参考上面代码 void RotateLR(const Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateLR(parent); if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subL->_bf = -1; subLR->_bf = 0; parent->_bf = ; } else if (bf == -1) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else { assert(false); } }

右左双旋

与左右双旋高度类似

注意一点，与上面的左右双旋相反的一点，需要双旋的那一坨由根节点的左子树那一块，变成了根节点的右子树那一块。那么在完成双旋后，​parent​节点变成了左边，​subR节点变成了右边

//为了更清晰的显示，这里直接给关键代码，头文件和相关成员变量可以参考上面代码 void RotateRL(const Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_right; int bf = subR->_bf; RotateR(parent->_right); Rotate(parent); if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subL->_bf = 0; subLR->_bf = 0; parent->_bf =-1 ; } else if (bf == -1) { subL->_bf = 1; subLR->_bf = 0; parent->_bf = 0; } else { assert(false); } }

AVL树的查找

AVL树的查找与二叉搜索树的查找是一样的搜索效率是O(log N)，比它大就往右走，比他小就往左走

‍

完