数据结构【AVL树】

AVL树

• 1.AVL树
  • 1.1AVL的概念
  • 1.2平衡因子
• 2.AVl树的实现
  • 2.1AVL树的结构
  • 2.2AVL树的插入
  • 2.3 旋转
    • 2.3.1 旋转的原则

1.AVL树

1.1AVL的概念

AVL树可以是一个空树。
它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 log^N ，那么增删查改的效率也可以控制在O(log^N ) ，相比二叉搜索树有了本质的提升。

1.2平衡因子

结点的平衡因子=右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标一样。
为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？
因为例如二和四个结点无法达到0.

2.AVl树的实现

2.1AVL树的结构

template<classK,classV>structAVLTreeNode{// 需要parent指针，后续更新平衡因⼦可以看到 pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;int _bf;// balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public://...private: Node * _root =nullptr;};

2.2AVL树的插入

boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv);if(parent->_kv.first < kv.first){ 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;}elseif(parent->_bf ==1|| parent->_bf ==-1){// 继续往上更新 cur = parent; parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){// 不平衡了，旋转处理break;}else{assert(false);}}returntrue;}

2.3 旋转

2.3.1 旋转的原则

保持搜索树的规则
让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。