avl树自实现（带图），探讨平衡因子与旋转

引子：

在此之前，我们学过了搜索二叉树，这种树，在如果数据有序或接近有序的情况下，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，而且普通搜索二叉树无法有重复的元素，对此，我们提出了平衡二叉树，avl树就是比较基础的，一种基于搜索二叉树的改进树，引入了平衡因子与旋转的概念！avl树是由两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种方法。

什么是avl树？

AVL树是一种自平衡的二叉搜索树，它的名字来源于它的发明者Adelson-Velsky和Landis。AVL树的特点是任何节点的两个子树的高度（或深度）最大差异为1。这种平衡特性确保了树的查找、插入和删除操作都能在对数时间内完成，即时间复杂度为O(log n)。当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1，它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

2，如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2n)，搜索时间复杂度O(log_2n)。

avl树的实现

如何实现avl树呢，我们要从图入手，并一步一步实现avl树代码的实现！

我们可以先换一侧树的全部情况，先写出“一半代码”，然后仿照着写就可以了。

一，先试着画出一半的图，思考如何写？以下是一个示范图

图一：

图二：

图三：

二，导入库

#include<iostream>
#include<assert.h>
using namespace std;

三，创建节点

//创建节点
template<class K,class V>
class avlTreeNode
{
public:avlTreeNode* _left;//左节点avlTreeNode* _right;//右节点avlTreeNode* _parent;//上级节点int _bf;//平衡因子pair<K, V>_kv;//kv的值；avlTreeNode(const pair<K,V>&kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};

四，整体框架；

template<class K,class V>
class avlTree
{typedef avlTreeNode<K,V> Node;
public://构造函数avlTree() = default;//拷贝构造函数,树形节点要一个一个拷贝avlTree(const avlTree<K, V>& h){_root = copy(h._root);}//find K值Node* Find( const K& key){Node* cur = _root;while (cur){if (cur->_left->_kv.first < key){cur = cur->_right;}else if (cur->_left->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//find V值Node* Find(const V& key){Node* cur = _root;while (cur){if (cur->_left->_kv.second < key){cur = cur->_right;}else if (cur->_left->_kv.second > key){cur = cur->_left;}else{return cur;}}return nullptr;}//中序有序，避免了_root是内部private的加密void _InOrder(){_InOrder(_root);cout << endl;}//insertbool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//要先找到，插入位置Node* parent = nullptr;Node* current = _root;while (current){if (current->_kv.first < kv.first){parent = current;current = current->_right;}else if (current->_kv.first > kv.first){parent = current;current = current->_left;}else{return false;}}//新增节点再链接上去current = new Node(kv);if (kv.first > (parent->_kv.first)){parent->_right = current;}else if (kv.first < (parent->_kv.first)){parent->_left = current;}return true;current->_parent = parent;//更新平衡因子,新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否//破坏了AVL树while (current){//左插--，右插++if (current == parent->_left){parent->_bf--;}else if (current == parent->_right){parent->_bf++;}if (parent->_bf == 0){//高度不变，达到最理想状态break;}else if (parent->_bf == -1 || parent->_bf == 1){//向上更新current = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2)//不平衡情况{if (parent->_bf == 2 && current->_bf == 1)//左旋RotateL(parent);else if (parent->_bf == -2 && current->_bf == -1)//右旋RotateR(parent);else if (parent->_bf == 2 && current->_bf ==-1)//左右旋RotateRL(parent);else  //(parent->_bf == -2 && current->_bf == 1)RotateLR(parent);}elseassert(false);}return true;}//因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不//错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。//重载=avlTree<K, V>& operator=(const avlTree<K, V>& h){swap(_root, h._root);return *this;}//析构函数,注意开辟了空间后，对于树形结构的节点要一个一个删除~avlTree(){Destory(_root);_root = nullptr;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}

五，private部分

private://计算有效的节点int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}//计算树的高度，利用递归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 _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root) return true;//严格检验int TreeHeight_L = _Height(root->_left);int TreeHeight_R = _Height(root->_right);//我们默认的是右到左int diff = TreeHeight_R - TreeHeight_L;//高度与平衡因子的数值不匹配if (diff != root->_bf || (diff > 1 || diff < -1))return false;return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}//左根右；_InOrder(root->_left);cout << root->_kv.first << " :" << root->_kv.second << " ";_InOrder(root->_right);}void RotateL( Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;Node* parent_parent = parent->_parent;if (parent_parent == nullptr){_root = subR;parent_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subR;}else if (parent_parent->_right == parent){parent_parent->_right = subR;}subR->_parent = parent_parent;}subR->_bf = parent->_bf = 0;}void RotateR( Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;Node* parent_parent = parent->_parent;if (parent_parent == nullptr){_root = subL;parent_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subL;}else if (parent_parent->_right == parent){parent_parent->_right = subL;}subL->_parent = parent_parent;}subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(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 =0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else{assert(false);}}//销毁void Destory(Node* root){if (root==nullptr){return;}Destory(root->_left);Destory(root->_right);Destory(root->_parent);delete root;}//拷贝Node* copy(const Node*& root){if (root == nullptr){return nullptr;}Node* temp = new Node(root->_kv);temp->_left=copy(root->_left);temp->_right=copy(root->_right);temp->_parent=copy(root->_parent);return temp;}Node* _root = nullptr;
};

六：说明，对于erase部分先不做处理啦！

七，AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即log_2 (N)。但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

ok，感谢大家的观看，有
问题可以发评论区（微笑！）