广东官网网站建设平台_百度seo排名主要看啥_凡科建站收费价目表_开网站需要多少钱

1.AVL树介绍

1.1概念介绍

1.2核心性质

2.项目文件规划

3.整体框架（节点和Tree）

4.AVL树的新节点插入

4.1新节点插入当前节点的右子树的右子树——左旋转

4.2新节点插入当前节点的左子树的左子树——右旋转

4.3新节点插入当前节点的左子树的右子树——左右双旋

4.4新节点插入当前节点的右子树的左子树——右左双旋

4.5组装完整版Insert（）

5.中序方便过会测试

6.编写函数看是否满足要求

6.1求高度

6.2 平衡否

7.全部代码

1.AVL树介绍

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法，人为规定：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

1.1概念介绍

1.AVL树定义：

解释AVL树是一种自平衡的二叉搜索树，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。
强调AVL树中每个节点的平衡因子（Balance Factor），即左子树高度和右子树高度之差不超过1。

2.平衡因子：

解释平衡因子的概念，即一个节点的右子树高度减去左子树高度的值。
平衡因子为{-1, 0, 1}时，树是平衡的。

3.自平衡性质：

说明AVL树具有自平衡性质，即在插入或删除节点时，会通过旋转操作来保持树的平衡。
提及AVL树的平衡因子限制，确保树的高度保持在对数级别。

1.2核心性质

1.严格平衡

强调AVL树的严格平衡性质，即每个节点的左右子树高度差不超过1。
严格平衡性质保证了AVL树的高度近似于对数级别，保证了高效的插入、删除和查找操作。

2.插入和删除操作：

介绍当插入或删除节点时，AVL树如何通过旋转操作来保持平衡。
解释插入和删除操作可能会导致树失去平衡，需要通过单旋转、双旋转等操作进行调整。。

3.时间复杂度：

说明AVL树的插入、删除和查找操作的时间复杂度都是O(log n)，其中n为树中节点的数量。
强调AVL树在动态数据集合中的高效性，适用于需要频繁更新的场景。

2.项目文件规划

头文件AVLTree.h：进行模拟的编写

源文件test.cpp：进行测试，检查代码逻辑是否满足期望

3.整体框架（节点和Tree）

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//父亲节点int _val; // balance factor 平衡因子pair<K, V> _kv;//每个节点里存一个pairAVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _val(0), _kv(kv)//都直接在初始化列表里初始化了{}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;//名字太长了，叫Node也更好理解
public:private:Node* _root = nullptr;//给上缺省值
};

4.AVL树的新节点插入

基本步骤：

查找插入位置：首先，我们需要找到新节点应该插入的位置。从根节点开始，按照二叉搜索树的性质，逐级向左或向右比较键值，直到找到一个合适的位置。
插入新节点：找到插入位置后，我们创建一个新的节点，并将其插入到树中。如果树为空，则新节点成为树的根节点。否则，将新节点插入到合适的位置，使得树仍然保持二叉搜索树的性质。
更新平衡因子：在插入新节点后，需要沿着插入路径更新所有受影响节点的平衡因子。平衡因子是指节点的左右子树的高度差。如果插入导致某个节点的平衡因子超出范围（通常是 -1、0、1），则需要进行旋转操作来恢复平衡。
平衡调整：如果插入操作破坏了 AVL 树的平衡性，我们需要进行一系列的旋转操作来重新平衡树。旋转操作包括单旋转和双旋转，具体的旋转方式取决于插入节点的位置以及平衡因子的情况。
旋转后继续向上：插入节点后，可能需要对父节点、祖父节点等进行旋转操作，直到树恢复平衡为止

    bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//找到父亲节点Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//找到了父亲节点，将要插入的节点插入适当的位置cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//更新插入节点的父亲节点cur->_parent = parent;//父亲节点的平衡值有没有发生变化while (parent){if (parent->_left == cur){parent->_val--;}else //if(parent->_right == cur){parent->_val++;}//如果平衡值==0，则说明该查入值没有影响，对于上面祖先的节点也没有影响，即可以跳出if (parent->_val == 0){break;}//如果该查入值的父亲平衡值发生了变化，则这条线的祖先的平衡值也要更新//所以不断的更新cur，parent，使祖先的平衡值，也不断的发生变化else if (parent->_val == 1 || parent->_val == -1){cur = parent;parent = parent->_parent;}//到了这一步，则需要进入左旋或有旋else if (parent->_val == 2 || parent->_val == -2){if (parent->_val == 2 && cur->_val == 1){//左旋levorotation(parent);}else if (parent->_val == -2 && cur->_val == -1){//右旋dextrorotation(parent);}else if (parent->_val == 2 && cur->_val == -1){//右双旋rightbispin(parent);}else if (parent->_val == -2 && cur->_val == 1){//左双旋leftbispin(parent);}break;}else{assert(false);}}return true;}

更新平衡因子过程：

更新的原则如下：

如果新节点插入到父节点的左侧，则父节点的平衡因子减一。
如果新节点插入到父节点的右侧，则父节点的平衡因子加一。
更新后，需要检查父节点的平衡因子是否发生变化，如果发生变化，则继续向上检查祖先节点的平衡因子，直到根节点或者到达一个平衡因子为 ±1 的节点为止。根据更新后节点的平衡因子情况，可以采取以下处理措施：
如果节点的平衡因子为 0，表示节点所在子树的高度没有变化，不会影响祖先节点的平衡因子，更新结束。
如果节点的平衡因子为 ±1，表示节点所在子树的高度变化（本来是0，现在变成 ±1，子树高度变了），会影响祖先节点的平衡因子，需要继续向上更新祖先节点的平衡因子。
如果节点的平衡因子为 ±2，表示节点所在子树违反了平衡规则，需要进行平衡调整操作（如旋转），然后更新结束

4.1新节点插入当前节点的右子树的右子树——左旋转

左旋 (levorotation)

左旋的情况是当一个节点的右子树过高，需要进行左旋来降低右子树的高度，同时保持树的平衡。

情况：

新节点插入到当前节点的右子树的右子树中，导致当前节点的平衡因子为 +2。
在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。

操作：

左旋是指将当前节点向左旋转，使得当前节点的右子树的左子树成为当前节点的右子树，同时将当前节点成为其右子树的左子树。
    A                     B/ \                   / \T1  B       ==>       A   T3/ \               / \T2  T3            T1  T2

    //左旋void levorotation(Node* parent){//找到右孩子Node* cur = parent->_right;Node* leftcur = cur->_left;parent->_right = leftcur;if (leftcur){leftcur->_parent = parent;}cur->_left = parent;//形成一个新的搜索二叉树//保存祖先节点，如果parent不是根节点时，好用祖先链接孩子Node* pparent = parent->_parent;//更新父亲parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left == cur;}else{pparent->_right = cur;}cur->_parent = pparent;}parent->_val = cur->_val = 0;}

4.2新节点插入当前节点的左子树的左子树——右旋转

右旋 (Right Rotation)

右旋的情况是当一个节点的左子树过高，需要进行右旋来降低左子树的高度，同时保持树的平衡。

情况：

新节点插入到当前节点的左子树的左子树中，导致当前节点的平衡因子为 -2。
在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。

操作：

右旋是指将当前节点向右旋转，使得当前节点的左子树的右子树成为当前节点的左子树，同时将当前节点成为其左子树的右子树。
    A                     B/ \                   / \B   T3       ==>     T1   A/ \                       / \
T1  T2                    T2  T3

	//右旋void dextrorotation(Node* parent){Node* cur = parent->_left;Node* rightcur = cur->_right;parent->_left = rightcur;if (rightcur){rightcur->_parent = parent;}cur->_right = parent;Node* pparent = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = cur;}else{pparent->_right = cur;}cur->_parent = pparent;}cur->_val = parent->_val = 0;}

4.3新节点插入当前节点的左子树的右子树——左右双旋

当新节点插入当前节点的左子树的右子树时，会触发左右双旋操作（LR旋转）。这种情况发生在当前节点的左子树的右子树上插入了新节点，导致当前节点的平衡因子不平衡（可能为+2或-2），且当前节点的左子树的右子树的平衡因子为正值（+1）。为了恢复 AVL 树的平衡性，需要先对当前节点的左子树进行一次左旋操作，然后再对当前节点进行一次右旋操作。

左右双旋（LR旋转）

具体步骤如下：

对当前节点的左子树进行一次左旋操作。
对当前节点进行一次右旋操作。

示例：

假设当前节点为 A，新节点插入在 A 的左子树的右子树的情况下，左右双旋操作如下：
        A                        A                        C/ \                      / \                      / \B   T4    左旋后         C   T4    右旋后         B   A/ \      --------->     / \       --------->    / \ / \T1   C                   B   T3                  T1 T2 T3 T4/ \                 / \T2  T3              T1  T2

//左双旋
void leftbispin(Node* parent
{Node* cur = parent->_left;Node* rightcur = cur->_right;levorotation(parent->_left);dextrorotation(parent);//更新平衡因子int val = rightcur->_val;if (val == 0){parent->_val = 0;cur->_val = 0;rightcur->_val = 0;}else if (val == 1){parent->_val = -1;cur->_val = 0;rightcur->_val = 0;}else if (val == -1){cur->_val = 1;parent->_val = 0;rightcur->_val = 0;}else{assert(false);}
}

4.4新节点插入当前节点的右子树的左子树——右左双旋

右左旋（RL旋转）

右左旋操作发生在节点的右子树过深，导致平衡因子为 -2 且其右子节点的平衡因子为 +1 的情况下。具体步骤如下：

对 A 的右子树进行一次左旋操作。
再对 A 进行一次右旋操作。

示例：
    A                     A                    C/ \                   / \                  / \T1  B       ==>      T1   C      ==>       A   B/ \                   / \              / \ / \C   T4                T2  B            T1 T2 T3 T4/ \                       / \T2  T3                    T3  T4

	//右双旋
void rightbispin(Node* parent)
{Node* cur = parent->_right;Node* rightcur = cur->_left;dextrorotation(parent->_right);levorotation(parent);int val = rightcur->_val;if (val == 0){parent->_val = 0;cur->_val = 0;rightcur->_val = 0;}else if (val == 1){parent->_val = 1;cur->_val = 0;rightcur->_val = 0;}else if (val == -1){cur->_val = -1;parent->_val = 0;rightcur->_val = 0;}else{assert(false);}
}

4.5组装完整版Insert（）

bool insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}//找到父亲节点Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//找到了父亲节点，将要插入的节点插入适当的位置cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//更新插入节点的父亲节点cur->_parent = parent;//父亲节点的平衡值有没有发生变化while (parent){if (parent->_left == cur){parent->_val--;}else //if(parent->_right == cur){parent->_val++;}//如果平衡值==0，则说明该查入值没有影响，对于上面祖先的节点也没有影响，即可以跳出if (parent->_val == 0){break;}//如果该查入值的父亲平衡值发生了变化，则这条线的祖先的平衡值也要更新//所以不断的更新cur，parent，使祖先的平衡值，也不断的发生变化else if (parent->_val == 1 || parent->_val == -1){cur = parent;parent = parent->_parent;}//到了这一步，则需要进入左旋或有旋else if (parent->_val == 2 || parent->_val == -2){if (parent->_val == 2 && cur->_val == 1){levorotation(parent);}else if (parent->_val == -2 && cur->_val == -1){//右旋dextrorotation(parent);}else if (parent->_val == 2 && cur->_val == -1){rightbispin(parent);}else if (parent->_val == -2 && cur->_val == 1){leftbispin(parent);}break;}else{assert(false);}}return true;}

5.中序方便过会测试

void InOrder()
{_InOrder(_root);
}
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << "[" << root->_val << "]" << endl;_InOrder(root->_right);
}

6.编写函数看是否满足要求

只要有一个节点的左子树与右子树的高度差距大于等于2，那么就不满足了

从这里也能看出要写一个求高度函数更方便

6.1求高度

int Height()
{_Height(_root);
}
int _Height(Node* root)
{if (root == nullptr){return 0;}int right = _Height(root->_right);int left = _Height(root->_left);return right > left ? right + 1 : left + 1;
}

这段代码实现了 AVL 树的高度计算和平衡性检查功能。

_Height 函数:

这个函数用于计算给定树的高度。递归地计算左右子树的高度，然后返回较大的子树高度加上 1。这个函数被用于计算整棵树的高度。

Height 函数:

这个函数是对外提供的接口，用于获取 AVL 树的高度。它调用 _Height 函数并传入根节点，返回整棵 AVL 树的高度。

6.2 平衡否

bool IsBalance()
{int height = 0;return _IsBlance(_root, height);
}
bool _IsBlance(Node* root, int& h)
{if (root == nullptr){h = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBlance(root->_left, leftHeight)|| !_IsBlance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}h= leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;
}

_IsBalance 函数:

这个函数用于检查 AVL 树的平衡性。它递归地检查树的每个节点，计算左右子树的高度并比较它们的差值，如果差值大于等于 2，则表示不平衡。此外，还检查每个节点的平衡因子是否正确，即右子树高度减去左子树高度等于节点的平衡因子。如果平衡因子异常，则表示树不平衡。

IsBalance 函数:

这个函数是对外提供的接口，用于检查整棵 AVL 树的平衡性。它调用 _IsBalance 函数并传入根节点，返回整棵 AVL 树是否平衡的结果。

这些函数的实现是 AVL 树的重要部分，用于确保 AVL 树保持平衡性和正确性。

7.全部代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class K,class V>
//树的节点
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K,V>* _left;AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;//父亲节点int _val;//平衡值AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_val(0){}
};template<class K,class V>
class AVLTree
{
public:typedef AVLTreeNode<K, V> Node;bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//找到父亲节点Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//找到了父亲节点，将要插入的节点插入适当的位置cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//更新插入节点的父亲节点cur->_parent = parent;//父亲节点的平衡值有没有发生变化while (parent){if (parent->_left == cur){parent->_val--;}else //if(parent->_right == cur){parent->_val++;}//如果平衡值==0，则说明该查入值没有影响，对于上面祖先的节点也没有影响，即可以跳出if (parent->_val == 0){break;}//如果该查入值的父亲平衡值发生了变化，则这条线的祖先的平衡值也要更新//所以不断的更新cur，parent，使祖先的平衡值，也不断的发生变化else if (parent->_val == 1 || parent->_val == -1){cur = parent;parent = parent->_parent;}//到了这一步，则需要进入左旋或有旋else if (parent->_val == 2 || parent->_val == -2){if (parent->_val == 2 && cur->_val == 1){levorotation(parent);}else if (parent->_val == -2 && cur->_val == -1){//右旋dextrorotation(parent);}else if (parent->_val == 2 && cur->_val == -1){rightbispin(parent);}else if (parent->_val == -2 && cur->_val == 1){leftbispin(parent);}break;}else{assert(false);}}return true;}//左旋void levorotation(Node* parent){//找到右孩子Node* cur = parent->_right;Node* leftcur = cur->_left;parent->_right = leftcur;if (leftcur){leftcur->_parent = parent;}cur->_left = parent;//形成一个新的搜索二叉树//保存祖先节点，如果parent不是根节点时，好用祖先链接孩子Node* pparent = parent->_parent;//更新父亲parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left == cur;}else{pparent->_right = cur;}cur->_parent = pparent;}parent->_val = cur->_val = 0;}//右旋void dextrorotation(Node* parent){Node* cur = parent->_left;Node* rightcur = cur->_right;parent->_left = rightcur;if (rightcur){rightcur->_parent = parent;}cur->_right = parent;Node* pparent = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = cur;}else{pparent->_right = cur;}cur->_parent = pparent;}cur->_val = parent->_val = 0;}//左双旋void leftbispin(Node* parent){Node* cur = parent->_left;Node* rightcur = cur->_right;levorotation(parent->_left);dextrorotation(parent);int val = rightcur->_val;if (val == 0){parent->_val = 0;cur->_val = 0;rightcur->_val = 0;}else if (val == 1){parent->_val = -1;cur->_val = 0;rightcur->_val = 0;}else if (val == -1){cur->_val = 1;parent->_val = 0;rightcur->_val = 0;}else{assert(false);}}//右双旋void rightbispin(Node* parent){Node* cur = parent->_right;Node* rightcur = cur->_left;dextrorotation(parent->_right);levorotation(parent);int val = rightcur->_val;if (val == 0){parent->_val = 0;cur->_val = 0;rightcur->_val = 0;}else if (val == 1){parent->_val = 1;cur->_val = 0;rightcur->_val = 0;}else if (val == -1){cur->_val = -1;parent->_val = 0;rightcur->_val = 0;}else{assert(false);}}private:Node* _root = nullptr;
};

广东官网网站建设平台_百度seo排名主要看啥_凡科建站收费价目表_开网站需要多少钱

1.AVL树介绍

1.1概念介绍

1.2核心性质

2.项目文件规划

3.整体框架（节点和Tree）

4.AVL树的新节点插入

4.1新节点插入当前节点的右子树的右子树——左旋转

4.2新节点插入当前节点的左子树的左子树——右旋转

4.3新节点插入当前节点的左子树的右子树——左右双旋

4.4新节点插入当前节点的右子树的左子树——右左双旋

4.5组装完整版Insert（）

5.中序方便过会测试

6.编写函数看是否满足要求

6.1求高度

6.2 平衡否

7.全部代码

最新新闻

热搜词