百度智能门户建站怎么样,网站文字源码,wordpress 分类浏览量,传奇类网页游戏文章目录 一、AVL树的介绍二、AVL树的实现1、基本框架2、查找3、插入4、删除5、测试6、总代码 三、AVL树的性能 一、AVL树的介绍
1、概念 AVL树#xff08;Adelson-Velsky and Landis Tree#xff09;是一种自平衡的二叉搜索树。它得名于其发明者G. M. Adelson-Velsky和E. M… 文章目录 一、AVL树的介绍二、AVL树的实现1、基本框架2、查找3、插入4、删除5、测试6、总代码 三、AVL树的性能 一、AVL树的介绍
1、概念 AVL树Adelson-Velsky and Landis Tree是一种自平衡的二叉搜索树。它得名于其发明者G. M. Adelson-Velsky和E. M. Landis。在AVL树中任何节点的两个子树的高度最大差别为1这保证了树的平衡性从而避免了在极端情况下如数据有序或接近有序时二叉搜索树退化为链表导致操作效率低下的问题。 2、特点 1平衡性AVL树通过维护每个节点的平衡因子左子树高度与右子树高度之差来保持树的平衡。平衡因子的值只能是-1、0或1。如果某个节点的平衡因子绝对值大于1那么该树就失去了平衡需要通过旋转操作来重新平衡。 2旋转操作当AVL树失去平衡时会触发旋转操作来恢复平衡。旋转操作主要有四种右旋单旋、左旋单旋、右-左双旋和左-右双旋。这些旋转操作通过改变树中节点的链接关系来降低树的高度从而保持树的平衡。 3 高效的查找、插入和删除操作由于AVL树保持了平衡其查找、插入和删除操作的时间复杂度都能保持在O(log n)的范围内其中n是树中节点的数量。这使得AVL树在处理大量数据时能够保持高效的性能。 4空间开销与普通的二叉搜索树相比AVL树需要额外的空间来存储每个节点的平衡因子。这增加了树的空间开销但在大多数情况下这种开销是可以接受的。 3、应用场景 AVL树广泛应用于需要频繁插入、删除和查找操作的场景如数据库索引、文件系统的目录结构、实时数据更新等。在这些场景中AVL树能够保持高效的性能确保数据处理的快速响应。 4、缺点 尽管AVL树具有许多优点但它也有一些缺点。例如在每次插入或删除节点后都需要进行平衡检查和可能的旋转操作这增加了操作的复杂度。此外与红黑树等其他自平衡二叉搜索树相比AVL树在插入和删除操作时可能需要更多的旋转操作来保持平衡。因此在某些特定场景下红黑树可能比AVL树更受欢迎。然而在需要高度平衡的场合AVL树仍然是一个非常好的选择。 二、AVL树的实现
1、基本框架
树节点 //树节点
templateclass K, class V
struct AVLTreeNode
{//构造函数AVLTreeNode(const pairK, V val pairK, V()): _left(nullptr), _right(nullptr), _parent(nullptr), _val(val), _bf(0){}AVLTreeNodeK,V* _left; //左孩子指针AVLTreeNodeK, V* _right; //右孩子指针AVLTreeNodeK, V* _parent; //父亲指针pairK, V _val; //数据int _bf; //节点的平衡因子 - 右子树高度 - 左子树高度
};AVL树类
templateclass K, class V
class AVLTree
{//树节点typedef AVLTreeNodeK, V Node;private://根节点Node* _root nullptr;
};2、查找 AVL树的查找操作与普通的二叉搜索树BST的查找操作非常相似。由于AVL树本身就是一种二叉搜索树所以它可以利用二叉搜索树的性质来高效地查找元素。在AVL树中查找元素的过程基本上不涉及树的平衡操作如旋转只是简单地利用节点的值和树的结构来定位目标元素。 步骤从根节点cur开始通过判断key与当前节点key的大小来决定是去左子树还是右子树找该值循环迭代cur上述过程直到找到相同的key后返回该节点否则就返回空。
//查找
Node* Find(const K key)
{//从根节点开始Node* cur _root;while (cur){//大了就去左子树中搜索if (cur-_val.first key){cur cur-_left;}//小了就去右子树中搜索else if (cur-_val.first key){cur cur-_right;}else{//找到返回当前节点return cur;}}return nullptr;
}3、插入 AVL树的插入操作在二叉搜索树BST的插入基础上增加了维护树平衡的步骤。AVL树是一种自平衡的二叉搜索树其中任何节点的两个子树的高度最大差别为1。 在插入后需要更新平衡因子插入左子树节点时父节点的平衡因子-1插入右子树节点时父节点的平衡因子1当更新后的父节点的平衡因子为0就不需要向上更新了说明插入之前是-1或者1插入节点后不会影响到上面的节点的平衡因子当平衡因子右子树高度 - 左子树高度为1或者-1时需要向上更新平衡因子说明插入之前为0插入后会影响到上面节点的平衡因子当为2或者-2时说明该树失去平衡了需要旋转来调整高度旋转之后的高度就平衡了不需要向上更新。 1插入一个元素使左子树高度大于右子树且失去平衡单纯一边高L和parent平衡因子同号 ------- 右旋转 平衡因子根据图分析旋转后parent和L都为0
// 右单旋
void RotateR(Node* parent)
{//左节点Node* L parent-_left;//左子树右边第一个节点Node* Lr L-_right;//parent的父亲Node* pparent parent-_parent;//连接过程L-_right parent;parent-_parent L;//该节点可能为空if (Lr){Lr-_parent parent;}parent-_left Lr;//更新L的父节点L-_parent pparent;//是根的情况if (pparent nullptr){_root L;}else{if (parent pparent-_left) pparent-_left L;else pparent-_right L;}//更新后平衡因子都为0parent-_bf L-_bf 0;
}2插入一个元素使右子树高度大于左子树且失去平衡单纯一边高R和parent平衡因子同号 ------- 左旋转
平衡因子根据图分析旋转后parent和R都为0
//左旋转
void RotateL(Node* parent)
{//右边第一个节点Node* R parent-_right;//右子树第一个左节点Node* Rl R-_left;//父节点Node* pparent parent-_parent;//连接过程parent-_right Rl;if (Rl){Rl-_parent parent;}R-_left parent;//更新parent的父节点parent-_parent R;//更新R的父节点R-_parent pparent;//是根的情况if (nullptr pparent){_root R;}else{if (pparent-_left parent) pparent-_left R;else pparent-_right R;}//更新平衡因子parent-_bf R-_bf 0;
}3插入一个元素使左子树高度大于右子树且失去平衡不单纯一边高L和parent平衡因子异号 ------- 左右旋转
平衡因子根据图分析上面只有Lr 1 的情况Lr 0,或者Lr -1的情况也按上图的方式推导更新前Lr的平衡因子为1时更新后L的平衡因子为-1、parent和Lr为0更新前Lr的平衡因子为-1时更新后parent平衡因子为1、L和Lr平衡因子为0更新前Lr的平衡因子为0时L、Lr、parent平衡因子都为0。
// 左右双旋
void RotateLR(Node* parent)
{Node* L parent-_left;Node* Lr L-_right;//先保存Lr的平衡因子因为旋转之后Lr的平衡因子会变int bf Lr-_bf;//左右双旋RotateL(L);RotateR(parent);//更新平衡因子if (bf -1){parent-_bf 1;L-_bf 0;Lr-_bf 0;}else if (bf 1){parent-_bf 0;L-_bf -1;Lr-_bf 0;}else if (bf 0){parent-_bf 0;L-_bf 0;Lr-_bf 0;}elseassert(false);
}4插入一个元素使右子树高度大于左子树且失去平衡不单纯一边高R和parent平衡因子异号 ------- 右左旋转 平衡因子根据图分析上面只有Rl 1 的情况Rl 0,或者Rl -1的情况也按上图的方式推导更新前Rl的平衡因子为-1时更新后R的平衡因子为-1、parent和Rl为0更新前Rl的平衡因子为1时更新后parent平衡因子为-1、R和Rl平衡因子为0更新前Rl的平衡因子为0时R、Rl、parent平衡因子都为0。
// 右左双旋
void RotateRL(Node* parent)
{Node* R parent-_right;Node* Rl R-_left;//先保存平衡因子int bf Rl-_bf;//右左双旋RotateR(R);RotateL(parent);//更新平衡因子if (bf 1){parent-_bf -1;R-_bf 0;Rl-_bf 0;}else if (bf -1){parent-_bf 0;R-_bf 1;Rl-_bf 0;}else if (bf 0){parent-_bf 0;R-_bf 0;Rl-_bf 0;}elseassert(false);
}5根据插入节点(参考搜索二叉树)更新平衡因子完成插入
//插入
bool Insert(const pairK, V val)
{ //找到放val的位置Node* cur _root;//作为前驱指针与val节点连接Node* precursor nullptr;while (cur){//向左if (cur-_val.first val.first){precursor cur;cur cur-_left;}//向右else if (cur-_val.first val.first){precursor cur;cur cur-_right;}//存在相同的值else{return false;}}//插入新节点cur new Node(val);//不存在根节点作为根节点if (precursor nullptr) _root cur;//连接在前驱指针左侧else if (precursor-_val.first val.first){cur-_parent precursor;precursor-_left cur;}//连接在前驱指针右侧else{cur-_parent precursor;precursor-_right cur;}//更新平衡因子while (precursor){if (precursor-_left cur)precursor-_bf--;elseprecursor-_bf;//为0说明平衡了不需要再更新了if (precursor-_bf 0)break;//出现异常需要更新平衡因子,更新完就可以else if (precursor-_bf 2 || precursor-_bf -2){if (precursor-_bf 2 cur-_bf 1){RotateL(precursor);}else if (precursor-_bf -2 cur-_bf -1){RotateR(precursor);}else if (precursor-_bf 2 cur-_bf -1){RotateRL(precursor);}else if (precursor-_bf -2 cur-_bf 1){RotateLR(precursor);}else{assert(false);}//更新完平衡了不需要向上更新break;}//进行迭代向上更新cur precursor;precursor precursor-_parent;}return true;
}4、删除 AVL树删除操作是一个复杂但关键的过程因为它需要在删除节点后重新调整树的结构以保持其平衡性。AVL树是一种自平衡的二叉搜索树其中任何节点的两个子树的高度最大差别为1。 在删除后需要更新平衡因子删除左子树节点时父节点的平衡因子1删除右子树节点时父节点的平衡因子-1当更新后的父节点的平衡因子为-1 或者 1就不需要向上更新了说明删除之前0删除节点后不会影响到上面的节点的平衡因子当平衡因子0时需要向上更新平衡因子说明删除之前为1或者-1删除后会影响到上面节点的平衡因子当为2或者-2时说明该树失去平衡了需要旋转来调整高度旋转之后当前父节点还是0的话还要继续向上更新直到更新为-1或者1时就结束更新。
因为复用插入的旋转操作所以在删除元素后有一些平衡因子在旋转过程中没有正确更新此时我们就要在旋转完后再次更新。 (1)删除后右边高了当R 0或者 R 1 时进行 — 左单旋 平衡因子当R的平衡因子为0时parent的平衡因子需要修改为1R的平衡因子修改为-1当R的平衡因子为1时也是按上图方式推导parent、R平衡因子都为0。
2删除后左边高了当L 0或者 L -1 时进行 — 右单旋 平衡因子当L的平衡因子为0时parent的平衡因子需要修改为-1L的平衡因子修改为-1当L的平衡因子为-1时也是按上图方式推导parent、L平衡因子都为0。
3删除后右边高了并且出现异号 — 右左双旋 平衡因子与插入时使用的右左双旋一样。
4删除后左边高了并且出现异号 — 左右双旋 平衡因子与插入时使用的左右双旋一样。
5使用删除操作参考搜索二叉树的删除旋转完成删除
//删除
bool Erase(const K key)
{//从根节点开始搜索Node* cur _root;//作为cur的前驱指针Node* precursor nullptr;//搜索查找while (cur){if (cur-_val.first key){precursor cur;cur cur-_left;}else if (cur-_val.first key){precursor cur;cur cur-_right;}elsebreak;}//找不到if (cur nullptr) return false;//假设cur左右节点都存在找右边最小值替换if (cur-_left ! nullptr cur-_right ! nullptr){Node* tmp1 cur-_right;Node* tmp2 nullptr;while (tmp1-_left){tmp2 tmp1;tmp1 tmp1-_left;}cur-_val tmp1-_val;//tmp1左边没有节点自己就是最小的节点if (tmp2 nullptr){precursor cur;cur tmp1; }else{cur tmp1;precursor tmp2;}}//假设左边为空和左右节点都为空int sign 0;//左边为-1右边为1Node* deletecur cur;if (cur-_left nullptr){左边为空父节点为空cur为根节点让cur-_riggt做为根直接结束就行了cur-_riggt本身为平衡树if (precursor nullptr){_root cur-_right;delete deletecur;return true;}else{if (precursor-_left cur){precursor-_left cur-_right;if (cur-_right nullptr) sign -1;}else{precursor-_right cur-_right;if (cur-_right nullptr) sign 1;}}cur cur-_right;}//假设右边为空else{//右边为空父节点为空cur为根节点让cur-_left做为根直接结束就行了cur-_left本身为平衡树if (precursor nullptr){_root cur-_left;delete deletecur;return true;}else{if (precursor-_left cur)precursor-_left cur-_left;elseprecursor-_right cur-_left;}cur cur-_left;}//更新平衡因子while (precursor){//cur出现空的情况if (cur nullptr){if (sign -1)precursor-_bf;elseprecursor-_bf--;}else if (precursor-_left cur)precursor-_bf;elseprecursor-_bf--;if (precursor-_bf -1 || precursor-_bf 1)break;else if (precursor-_bf -2 || precursor-_bf 2){//右边高了左单旋if (precursor-_bf 2 (precursor-_right-_bf 0 || precursor-_right-_bf 1)){//R会做为新的precursor先保存Node* R precursor-_right;int bf precursor-_right-_bf;RotateL(precursor);//在旋转后的平衡因子不符合预期需要更新if (bf 0){precursor-_bf 1;R-_bf -1;}//更新precursor R;}//左边高了右单旋else if (precursor-_bf -2 (precursor-_left-_bf 0 || precursor-_left-_bf -1)){//L会做为新的precursor先保存Node* L precursor-_left;int bf L-_bf;RotateR(precursor);//在旋转后的平衡因子不符合预期需要更新if (bf 0){precursor-_bf -1;L-_bf 1;}//更新precursor L;}else if (precursor-_bf 2 precursor-_right-_bf -1){//L会做为新的precursor先保存Node* R precursor-_right;Node* L R-_left;RotateRL(precursor);//更新precursor L;}else if (precursor-_bf -2 precursor-_left-_bf 1){//R会做为新的precursor先保存Node* L precursor-_left;Node* R L-_right;RotateLR(precursor);//更新precursor R;}elseassert(false);//旋转完precursor更新了再次判断是否平衡了if (precursor-_bf -1 || precursor-_bf 1) break;}//进行迭代cur precursor;precursor precursor-_parent;}delete deletecur;return true;
}5、测试
通过两颗子树的高度差是否大于1和判断高度差是否与这颗根节点平衡因子相等来判断是否为AVL树。
//判断是否为平衡树
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}
//验证是否是平衡树
bool _IsBalanceTree(Node* root)
{if (root nullptr) return true;int l _Height(root-_left);int r _Height(root-_right);int buff r - l;if (root-_bf ! buff || buff 1 || buff -1)return false;return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}
//求树的高度
int _Height(Node* root)
{if (root nullptr) return 0;int l _Height(root-_left);int r _Height(root-_right);return max(l, r) 1;
}void test()
{AVLTreeint, int a;vectorint arr;for (int i 0; i 10000; i){int m rand() i;arr.push_back(m);}//插入10000个随机数for (auto e :arr){a.Insert({ e,e });if (a.IsBalanceTree())cout 是AVL树 endl;elseassert(false);}//再全部删除for (auto e : arr){a.Erase(e);if (a.IsBalanceTree())cout 是AVL树 endl;elseassert(false);}
}在插入和删除过程中没有报错说明该树是AVL树。
6、总代码
#pragma once
#includeiostream
#includestring
#includecassert
#includequeue
#includevectorusing namespace std;//树节点
templateclass K, class V
struct AVLTreeNode
{//构造函数AVLTreeNode(const pairK, V val pairK, V()): _left(nullptr), _right(nullptr), _parent(nullptr), _val(val), _bf(0){}AVLTreeNodeK,V* _left; //左孩子指针AVLTreeNodeK, V* _right; //右孩子指针AVLTreeNodeK, V* _parent; //父亲指针pairK, V _val; //数据int _bf; //节点的平衡因子 - 右子树高度 - 左子树高度
};templateclass K, class V
class AVLTree
{//树节点typedef AVLTreeNodeK, V Node;
public:~AVLTree(){DeleteTree(_root);}//插入bool Insert(const pairK, V val){ //找到放val的位置Node* cur _root;//作为前驱指针与val节点连接Node* precursor nullptr;while (cur){//向左if (cur-_val.first val.first){precursor cur;cur cur-_left;}//向右else if (cur-_val.first val.first){precursor cur;cur cur-_right;}//存在相同的值else{return false;}}//插入新节点cur new Node(val);//不存在根节点作为根节点if (precursor nullptr) _root cur;//连接在前驱指针左侧else if (precursor-_val.first val.first){cur-_parent precursor;precursor-_left cur;}//连接在前驱指针右侧else{cur-_parent precursor;precursor-_right cur;}//更新平衡因子while (precursor){if (precursor-_left cur)precursor-_bf--;elseprecursor-_bf;//为0说明平衡了不需要再更新了if (precursor-_bf 0)break;//出现异常需要更新平衡因子,更新完就可以else if (precursor-_bf 2 || precursor-_bf -2){if (precursor-_bf 2 cur-_bf 1){RotateL(precursor);}else if (precursor-_bf -2 cur-_bf -1){RotateR(precursor);}else if (precursor-_bf 2 cur-_bf -1){RotateRL(precursor);}else if (precursor-_bf -2 cur-_bf 1){RotateLR(precursor);}else{assert(false);}//更新完平衡了不需要向上更新break;}//进行迭代向上更新cur precursor;precursor precursor-_parent;}return true;}//查找Node* Find(const K key){//从根节点开始Node* cur _root;while (cur){//大了就去左子树中搜索if (cur-_val.first key){cur cur-_left;}//小了就去右子树中搜索else if (cur-_val.first key){cur cur-_right;}else{//找到返回当前节点return cur;}}return nullptr;}//删除bool Erase(const K key){//从根节点开始搜索Node* cur _root;//作为cur的前驱指针Node* precursor nullptr;//搜索查找while (cur){if (cur-_val.first key){precursor cur;cur cur-_left;}else if (cur-_val.first key){precursor cur;cur cur-_right;}elsebreak;}//找不到if (cur nullptr) return false;//假设cur左右节点都存在找右边最小值替换if (cur-_left ! nullptr cur-_right ! nullptr){Node* tmp1 cur-_right;Node* tmp2 nullptr;while (tmp1-_left){tmp2 tmp1;tmp1 tmp1-_left;}cur-_val tmp1-_val;//tmp1左边没有节点自己就是最小的节点if (tmp2 nullptr){precursor cur;cur tmp1; }else{cur tmp1;precursor tmp2;}}//假设左边为空和左右节点都为空int sign 0;//左边为-1右边为1Node* deletecur cur;if (cur-_left nullptr){左边为空父节点为空cur为根节点让cur-_riggt做为根直接结束就行了cur-_riggt本身为平衡树if (precursor nullptr){_root cur-_right;delete deletecur;return true;}else{if (precursor-_left cur){precursor-_left cur-_right;if (cur-_right nullptr) sign -1;}else{precursor-_right cur-_right;if (cur-_right nullptr) sign 1;}}cur cur-_right;}//假设右边为空else{//右边为空父节点为空cur为根节点让cur-_left做为根直接结束就行了cur-_left本身为平衡树if (precursor nullptr){_root cur-_left;delete deletecur;return true;}else{if (precursor-_left cur)precursor-_left cur-_left;elseprecursor-_right cur-_left;}cur cur-_left;}//更新平衡因子while (precursor){//cur出现空的情况if (cur nullptr){if (sign -1)precursor-_bf;elseprecursor-_bf--;}else if (precursor-_left cur)precursor-_bf;elseprecursor-_bf--;if (precursor-_bf -1 || precursor-_bf 1)break;else if (precursor-_bf -2 || precursor-_bf 2){//右边高了左单旋if (precursor-_bf 2 (precursor-_right-_bf 0 || precursor-_right-_bf 1)){//R会做为新的precursor先保存Node* R precursor-_right;int bf precursor-_right-_bf;RotateL(precursor);//在旋转后的平衡因子不符合预期需要更新if (bf 0){precursor-_bf 1;R-_bf -1;}//更新precursor R;}//左边高了右单旋else if (precursor-_bf -2 (precursor-_left-_bf 0 || precursor-_left-_bf -1)){//L会做为新的precursor先保存Node* L precursor-_left;int bf L-_bf;RotateR(precursor);//在旋转后的平衡因子不符合预期需要更新if (bf 0){precursor-_bf -1;L-_bf 1;}//更新precursor L;}else if (precursor-_bf 2 precursor-_right-_bf -1){//L会做为新的precursor先保存Node* R precursor-_right;Node* L R-_left;RotateRL(precursor);//更新precursor L;}else if (precursor-_bf -2 precursor-_left-_bf 1){//R会做为新的precursor先保存Node* L precursor-_left;Node* R L-_right;RotateLR(precursor);//更新precursor R;}elseassert(false);//旋转完precursor更新了再次判断是否平衡了if (precursor-_bf -1 || precursor-_bf 1) break;}//进行迭代cur precursor;precursor precursor-_parent;}delete deletecur;return true;}//判断是否为平衡树bool IsBalanceTree(){return _IsBalanceTree(_root);}private:// 右单旋void RotateR(Node* parent){//左节点Node* L parent-_left;//左子树右边第一个节点Node* Lr L-_right;//parent的父亲Node* pparent parent-_parent;//连接过程L-_right parent;parent-_parent L;//该节点可能为空if (Lr){Lr-_parent parent;}parent-_left Lr;//更新L的父节点L-_parent pparent;//是根的情况if (pparent nullptr){_root L;}else{if (parent pparent-_left) pparent-_left L;else pparent-_right L;}//更新后平衡因子都为0parent-_bf L-_bf 0;}//左旋转void RotateL(Node* parent){//右边第一个节点Node* R parent-_right;//右子树第一个左节点Node* Rl R-_left;//父节点Node* pparent parent-_parent;//连接过程parent-_right Rl;if (Rl){Rl-_parent parent;}R-_left parent;//更新parent的父节点parent-_parent R;//更新R的父节点R-_parent pparent;//是根的情况if (nullptr pparent){_root R;}else{if (pparent-_left parent) pparent-_left R;else pparent-_right R;}//更新平衡因子parent-_bf R-_bf 0;}// 右左双旋void RotateRL(Node* parent){Node* R parent-_right;Node* Rl R-_left;//先保存平衡因子int bf Rl-_bf;//右左双旋RotateR(R);RotateL(parent);//更新平衡因子if (bf 1){parent-_bf -1;R-_bf 0;Rl-_bf 0;}else if (bf -1){parent-_bf 0;R-_bf 1;Rl-_bf 0;}else if (bf 0){parent-_bf 0;R-_bf 0;Rl-_bf 0;}elseassert(false);}// 左右双旋void RotateLR(Node* parent){Node* L parent-_left;Node* Lr L-_right;//先保存Lr的平衡因子因为旋转之后Lr的平衡因子会变int bf Lr-_bf;//左右双旋RotateL(L);RotateR(parent);//更新平衡因子if (bf -1){parent-_bf 1;L-_bf 0;Lr-_bf 0;}else if (bf 1){parent-_bf 0;L-_bf -1;Lr-_bf 0;}else if (bf 0){parent-_bf 0;L-_bf 0;Lr-_bf 0;}elseassert(false);}//求树的高度int _Height(Node* root){if (root nullptr) return 0;int l _Height(root-_left);int r _Height(root-_right);return max(l, r) 1;}//验证是否是平衡树bool _IsBalanceTree(Node* root){if (root nullptr) return true;int l _Height(root-_left);int r _Height(root-_right);int buff r - l;if (root-_bf ! buff || buff 1 || buff -1)return false;return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}void DeleteTree(Node* root){if (root nullptr)return;DeleteTree(root-_left);DeleteTree(root-_right);delete root;}//根节点Node* _root nullptr;
};三、AVL树的性能
1、搜索性能分析 时间复杂度O(log n) 1 AVL树作为二叉搜索树的一种其搜索操作与普通的二叉搜索树相同。从根节点开始根据要搜索的值与节点值的大小关系决定是向左子树搜索还是向右子树搜索直到找到目标节点或搜索到叶子节点为止。 2由于AVL树的高度被限制在O(log n)以内其中n是树中节点的数量因此搜索操作的时间复杂度也是O(log n)。 2、插入性能分析 时间复杂度O(log n) 1插入操作首先执行普通的二叉搜索树插入操作找到新节点应该插入的位置。 插入新节点后从该节点开始向上遍历更新所有受影响节点的平衡因子。 2如果某个节点的平衡因子变为2或-2即左右子树高度差超过1则需要进行旋转操作来恢复平衡。旋转操作包括单旋转左单旋、右单旋和双旋转左右双旋、右左双旋。 3由于旋转操作只在从插入节点到根节点的路径上进行且路径长度不超过树的高度因此插入操作的时间复杂度也是O(log n)。 3、删除性能分析 时间复杂度O(log n) 1删除操作首先找到要删除的节点。 2如果要删除的节点有两个子节点则通常使用其右子树中的最小节点或左子树中的最大节点来替换它并删除那个最小或最大节点。 3删除节点后从该节点开始向上遍历更新所有受影响节点的平衡因子。 4如果某个节点的平衡因子变为2或-2则需要进行旋转操作来恢复平衡。旋转操作的类型与插入操作类似包括单旋转和双旋转。 5同样地由于旋转操作只在从删除节点到根节点的路径上进行且路径长度不超过树的高度因此删除操作的时间复杂度也是O(log n)。 4、总结 AVL树通过保持树的平衡性使得搜索、插入和删除操作的时间复杂度都能保持在O(log n)的水平。这种高效的性能使得AVL树在需要频繁进行动态修改操作的数据结构中非常有用如数据库索引、文件系统等。然而需要注意的是AVL树在每次插入或删除操作后都需要进行平衡调整这可能会增加一些额外的开销。但在大多数情况下这种开销是可以接受的因为AVL树提供了比未平衡的二叉搜索树更好的性能保证。
