南安市住房和城乡建设局网站,关于青岛的网页设计,教务管理系统密码忘了怎么办,辛集做网站AVL树一、AVL树的概念二、AVL的接口2.1 插入2.2 旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋三、验证四、源码一、AVL树的概念
当我们用普通的搜索树插入数据的时候#xff0c;如果插入的数据是有序的#xff0c;那么就退化成了一个链表#xff0c;搜索效率…
AVL树一、AVL树的概念二、AVL的接口2.1 插入2.2 旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋三、验证四、源码一、AVL树的概念
当我们用普通的搜索树插入数据的时候如果插入的数据是有序的那么就退化成了一个链表搜索效率低下。
为了应对这种情况就出现了AVL树高度平衡二叉搜索树 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1 AVL树的性质
它的左右子树都是AVL树。左右子树高度之差(简称平衡因子)的绝对值不超过1
平衡因子 右子树高度-左子树高度 平衡因子是用来检测树的状态如果平衡因子都在-1 0 1中则没问题反之则需要调整。
二、AVL的接口
AVL的节点定义
template class K, class V
struct AVLNode
{AVLNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}pairK, V _kv;AVLNodeK, V* _left;AVLNodeK, V* _right;AVLNodeK, V* _parent;int _bf;// 平衡因子
};2.1 插入
AVL的基本插入流程跟搜索树相似但是AVL树多了一个平衡因子。 一旦插入新节点就要往上更新平衡因子。
如果是在左边点插入则平衡因子--如果是在右边点插入则平衡因子 更新一个结点之后我们需要去进行判断子树的高度是否发生了变化 1️⃣ 当父节点的平衡因子变成0说明原来是-1或1那么也就是把矮的地方填平了父节点所在树的高度不变不需要继续更新。 2️⃣ 当父节点的平衡因子变成1或-1说明原来是0父节点所在树的高度发生变化需要继续更新。 3️⃣ 当当父节点的平衡因子变成2或-2违反规则需要进行旋转处理。 所以我们可以利用parent节点插入之前的叶子节点从它开始往上更新。
bool insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else return false;}cur new Node(kv);if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_left) parent-_bf--;else parent-_bf;if (parent-_bf 0) break;else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// 旋转if (parent-_bf 2 cur-_bf 1){// 左单旋RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){// 右单旋RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){// 左右双旋RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){// 右左双旋RotateRL(parent);}break;}else{cout 结构出错 endl;assert(false);}}return true;
}2.2 旋转
为了保证每个结点的左右子树高度之差的绝对值不超过1所以当平衡因子变为-2或2时需要旋转来保持平衡。 旋转规则 1️⃣ 让这颗子树左右高度差不超过1 2️⃣ 旋转过程中继续保持它是搜索树 3️⃣ 更新调整孩子节点的平衡因子 4️⃣ 让这颗子树的高度根插入前保持一致
2.2.1 左单旋
二叉树的结构有无数种情况所以我们需要总结出抽象图来分析 解释 a/b/c是高度为h的AVL树。
新节点插入较高右子树的右侧—右右左单旋 左单旋的步骤 1️⃣ 20的左边调整到10的右边 2️⃣ 10变成20的左边20做根 3️⃣ 把平衡因子变为0 void RotateL(Node* parent)
{Node* top parent-_parent;Node* right parent-_right;// 20的左边调整到10的右边parent-_right right-_left;if (right-_left) right-_left-_parent parent;// 10变成20的左边20做根right-_left parent;parent-_parent right;if (top)// 子树{if (parent top-_left) top-_left right;else top-_right right;right-_parent top;}else// 完整的树{_root right;_root-_parent nullptr;}// 更新平衡因子parent-_bf right-_bf 0;
}2.2.2 右单旋
新节点插入较高左子树的左侧—左左右单旋
void RotateR(Node* parent)
{Node* top parent-_parent;Node* left parent-_left;Node* leftR left-_right;parent-_left leftR;if (leftR) leftR-_parent parent;left-_right parent;parent-_parent left;if (top){if (parent top-_left) top-_left left;else top-_right left;left-_parent top;}else{_root left;_root-_parent nullptr;}parent-_bf left-_bf 0;
}2.2.3 左右双旋
新节点插入较高左子树的右侧—左右先左单旋再右单旋
我们看到上面的单旋我们会想如果是这么插入呢
其实这个图可以转化为 先以10为轴进行左单旋这样就把“折线”变成了直线在以20为轴进行右单旋。 这里就要注意平衡因子的更新 15的平衡因子为0 但是其他两个会有三个不同的情况
1️⃣ 当right的平衡因子为-1时插入在b双旋结束后parent、left、right的平衡因子分别更新为1、0、0 2️⃣ 当right的平衡因子为1时插入在c双旋结束后parent、left、right的平衡因子分别更新为0、-1、0 3️⃣ 当right的平衡因子为0时双旋后parent、left、right的平衡因子分别更新为0、0、0
所以在旋转前要先进行判断在哪插入通过平衡因子旋转后手动更新即可。
void RotateLR(Node* parent)
{Node* left parent-_left;Node* right left-_right;int bf right-_bf;// 提前记录RotateL(parent-_left);RotateR(parent);if (bf -1)// 左子树新增{left-_bf 0;right-_bf 0;parent-_bf 1;}else if (bf 1)// 右子树新增{left-_bf -1;right-_bf 0;parent-_bf 0;}else if (bf 0)// 自己就是新增{left-_bf right-_bf parent-_bf 0;}else assert(false);
}2.2.4 右左双旋 void RotateRL(Node* parent){Node* right parent-_right;Node* left right-_left;int bf left-_bf;RotateR(right);RotateL(parent);if (bf -1){parent-_bf 0;left-_bf 0;right-_bf 1;}else if (bf 1){right-_bf 0;left-_bf 0;parent-_bf -1;}else if (bf 0){left-_bf right-_bf parent-_bf 0;}else assert(false);}三、验证
为了验证是否为二叉搜索树我们可以先写一个中序遍历
void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);
}void Inorder()
{_Inorder(_root);
}为了验证是否为AVL树我们要让每个节点的左右子树高度的绝对值差小于等于1。
int Height(Node* root)
{if (!root){return 0;}int lh Height(root-_left) 1;int rh Height(root-_right) 1;return max(lh, rh);
}bool IsBalance(Node* root)
{if (!root){return true;}int lh Height(root-_left);int rh Height(root-_right);if (rh - lh ! root-_bf){cout root-_kv.first :;cout root-_bf :;cout 平衡因子出错 endl;return false;}if (abs(rh - lh) 1){return false;}return IsBalance(root-_left) IsBalance(root-_right);
}bool IsBalance()
{return IsBalance(_root);
}我们可以用大量的随机值来测定
void test()
{const int N 100000;AVLTreeint, int tt;srand(time(0));for (int i 0; i N; i){int x rand();tt.insert(make_pair(x, x));}//tt.Inorder();cout tt.IsBalance() endl;
}四、源码
#pragma once
#include iostream
#include string
#include cassert
#include cstdlib using namespace std;template class K, class V
struct AVLNode
{AVLNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}pairK, V _kv;AVLNodeK, V* _left;AVLNodeK, V* _right;AVLNodeK, V* _parent;int _bf;// 平衡因子
};template class K, class V
class AVLTree
{typedef AVLNodeK, V Node;
public:bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else return false;}cur new Node(kv);if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_left) parent-_bf--;else parent-_bf;if (parent-_bf 0) break;else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// 旋转if (parent-_bf 2 cur-_bf 1){// 左单旋RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){// 右单旋RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){// 左右双旋RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){// 右左双旋RotateRL(parent);}break;}else{cout 结构出错 endl;assert(false);}}return true;}void RotateL(Node* parent){Node* top parent-_parent;Node* right parent-_right;// 20的左边调整到10的右边parent-_right right-_left;if (right-_left) right-_left-_parent parent;// 10变成20的左边20做根right-_left parent;parent-_parent right;if (top)// 子树{if (parent top-_left) top-_left right;else top-_right right;right-_parent top;}else// 完整的树{_root right;_root-_parent nullptr;}// 更新平衡因子parent-_bf right-_bf 0;}void RotateR(Node* parent){Node* top parent-_parent;Node* left parent-_left;Node* leftR left-_right;parent-_left leftR;if (leftR) leftR-_parent parent;left-_right parent;parent-_parent left;if (top){if (parent top-_left) top-_left left;else top-_right left;left-_parent top;}else{_root left;_root-_parent nullptr;}parent-_bf left-_bf 0;}void RotateLR(Node* parent){Node* left parent-_left;Node* right left-_right;int bf right-_bf;// 提前记录RotateL(left);RotateR(parent);if (bf -1)// 左子树新增{left-_bf 0;right-_bf 0;parent-_bf 1;}else if (bf 1)// 右子树新增{left-_bf -1;right-_bf 0;parent-_bf 0;}else if (bf 0)// 自己就是新增{left-_bf right-_bf parent-_bf 0;}else assert(false);}void RotateRL(Node* parent){Node* right parent-_right;Node* left right-_left;int bf left-_bf;RotateR(right);RotateL(parent);if (bf -1){parent-_bf 0;left-_bf 0;right-_bf 1;}else if (bf 1){right-_bf 0;left-_bf 0;parent-_bf -1;}else if (bf 0){left-_bf right-_bf parent-_bf 0;}else assert(false);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first root-_kv.second endl;_Inorder(root-_right);}void Inorder(){_Inorder(_root);}int Height(Node* root){if (!root){return 0;}int lh Height(root-_left) 1;int rh Height(root-_right) 1;return max(lh, rh);}bool IsBalance(Node* root){if (!root){return true;}int lh Height(root-_left);int rh Height(root-_right);if (rh - lh ! root-_bf){cout root-_kv.first :;cout root-_bf :;cout 平衡因子出错 endl;return false;}if (abs(rh - lh) 1){return false;}return IsBalance(root-_left) IsBalance(root-_right);}bool IsBalance(){return IsBalance(_root);}
private:Node* _root nullptr;
};void test()
{const int N 100000;AVLTreeint, int tt;srand(time(0));for (int i 0; i N; i){int x rand();tt.insert(make_pair(x, x));}//tt.Inorder();cout tt.IsBalance() endl;
}
