废旧电脑做网站服务器谷歌广告联盟
引子:
在此之前,我们学过了搜索二叉树,这种树,在如果数据有序或接近有序的情况下,二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,而且普通搜索二叉树无法有重复的元素,对此,我们提出了平衡二叉树,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,感谢大家的观看,有
问题可以发评论区(微笑!)