yahoo网站提交入口,西安做服务器的公司,cpv广告联盟,wordpress图片lazyload二叉搜索树#xff1a;【C进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
目录
一、AVL树的概念
二、AVL树的原理与实现
AVL树的节点
AVL树的插入
AVL树的旋转
AVL树的打印
AVL树的检查
三、实现AVL树的完整代码
四、总结 前言#xff1a…二叉搜索树【C进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
目录
一、AVL树的概念
二、AVL树的原理与实现
AVL树的节点
AVL树的插入
AVL树的旋转
AVL树的打印
AVL树的检查
三、实现AVL树的完整代码
四、总结 前言 在前面我们学习二叉搜索树的时候虽然大部分情况下二叉搜索树的效率都是很高的但是如果是一组相对有序的数字我们用二叉搜索树来排序就会显得比较麻烦了因此AVL树就出现了下面就让我们一起来学习以下AVL树的相关知识 一、AVL树的概念 AVL树实际上就是特殊的二叉搜索树是对二叉搜索树的改进我们在用树形结构来查找或操作数据的时候一般都是要从树根一层一层往下找所以树高越低效率越高但是二叉搜索树在有些场景下比较麻烦比如一个相对有序的数组{213456} 这样一个数组如果通过二叉搜索树处理就会显得层数太多效率很低 所以人们也就有了这样一种思考我们可不可以通过某种操作让左右子树的高度差不超过1这样就能极大的提高效率这就是AVL树的概念 AVL树中任何节点的左右子树的高度差平衡因子绝对值不超过1。这意味着树始终保持平衡避免了二叉搜索树在节点插入或删除后可能出现的退化现象。 二、AVL树的原理与实现
了解了AVL树的基本内容之后接下来我们就来一步一步学习以下AVL树的原理到底是什么以及如何实现一个AVL树
AVL树的节点
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; //左子树AVLTreeNodeK, V* _right; //右子树AVLTreeNodeK, V* _parent; //父亲pairK, V _kv; //存放节点值的int _bf; //平衡因子通过这个可以直到左右子树存在情况//构造函数AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0) //平衡因子起始值是0当左子树插入一个节点时-1右子树插入一个节点时1{}
};AVL树的节点操作与二叉搜索树还是比较相似的都有左子树右子树和父亲节点的叉式结构比较不同的是加入了一个平衡因子 AVL树的插入
实现AVL树的重点就是解决AVL树的插入问题而解决插入问题最关键的就是要做到如何让左右子树高度的绝对值适合不大于1我们是通过合理的旋转来实现的而且需要旋转的情况也是分为四种的 RR型左旋 LL型右旋 RL型先右旋再左旋 LR型先左旋再右旋 下面我们来看这样几个例子
1、RR型左旋 2、LL型右旋 3、LR型先左旋再右旋 4、RL型先右旋再左旋
操作与3正好相反不过多赘述
下面就让我们看一下插入的代码 bool Insert(const pairK,V kv) //插入节点{if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left 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 2cur-_bf1){//左单旋RotateL(parent);break;}else if (parent-_bf -2 cur-_bf -1){//右单旋RotateR(parent);break;}else if (parent-_bf 2 cur-_bf -1){//RL型RotateRL(parent);break;}else if (parent-_bf -2 cur-_bf 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}AVL树的旋转 void RotateL(Node* parent) //左单旋RR型{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;parent-_right subRL;subR-_left parent;if(subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_parent subR;parent-_bf 0;subR-_bf 0;}void RotateR(Node* parent) //右单旋LL型{Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;parent-_left subLR;subL-_right parent;if (subLR){subLR-_parent parent;}if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}parent-_parent subL;subL-_bf parent-_bf 0;}void RotateRL(Node* parent) //先右单旋再左单旋RL型{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){//subRL自己就是新增点parent-_bf subR-_bf 0;}else if (bf -1){//subRL的左子树上新增parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 1){//subRL的右子树上新增parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}void RotateLR(Node* parent) //先左单旋再右单旋LR型{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){//subLR自己就是新增点parent-_bf subL-_bf 0;}else if (bf -1){//subLR的左子树上新增parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){//subLR的右子树上新增parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else{assert(false);}}AVL树的打印
AVL树的打印与二叉搜索树一致都是中序打印我们就直接来看代码了 //中序打印void Inorder(){_Inorder(_root);cout endl;}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}AVL树的检查 检查是否为AVL树一方面我们可以通过打印的结果先来判断一下它是不是二叉搜索树然后我们可以通过比较左右子树的高度差来判断它是否为AVL树根据前面可知AVL树左右子树高度差最大为1 //检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root nullptr)return 0;int LeftHigh _High(root-_left);int RightHigh _High(root-_right);return LeftHigh RightHigh ? LeftHigh 1 : RightHigh 1;}bool _IsBalance(Node* root){if (root nullptr)return true;int LeftHigh _High(root-_left);int RightHigh _High(root-_right);if (RightHigh - LeftHigh ! root-_bf){cout _root-_kv.first 当前节点平衡因子有问题 endl;return false;}return abs(LeftHigh- RightHigh) 2 _IsBalance(root-_left) _IsBalance(root-_right);}三、实现AVL树的完整代码
AVLTree.h
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; //左子树AVLTreeNodeK, V* _right; //右子树AVLTreeNodeK, V* _parent; //父亲pairK, V _kv; //存放节点值的int _bf; //平衡因子通过这个可以直到左右子树存在情况//构造函数AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0) //平衡因子起始值是0当左子树插入一个节点时-1右子树插入一个节点时1{}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, 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 (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left 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 2cur-_bf1){//左单旋RotateL(parent);break;}else if (parent-_bf -2 cur-_bf -1){//右单旋RotateR(parent);break;}else if (parent-_bf 2 cur-_bf -1){//RL型RotateRL(parent);break;}else if (parent-_bf -2 cur-_bf 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}void RotateL(Node* parent) //左单旋RR型{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;parent-_right subRL;subR-_left parent;if(subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_parent subR;parent-_bf 0;subR-_bf 0;}void RotateR(Node* parent) //右单旋LL型{Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;parent-_left subLR;subL-_right parent;if (subLR){subLR-_parent parent;}if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}parent-_parent subL;subL-_bf parent-_bf 0;}void RotateRL(Node* parent) //先右单旋再左单旋RL型{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){//subRL自己就是新增点parent-_bf subR-_bf 0;}else if (bf -1){//subRL的左子树上新增parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 1){//subRL的右子树上新增parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}void RotateLR(Node* parent) //先左单旋再右单旋LR型{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){//subLR自己就是新增点parent-_bf subL-_bf 0;}else if (bf -1){//subLR的左子树上新增parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){//subLR的右子树上新增parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else{assert(false);}}//中序打印void Inorder(){_Inorder(_root);cout endl;}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}//检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root nullptr)return 0;int LeftHigh _High(root-_left);int RightHigh _High(root-_right);return LeftHigh RightHigh ? LeftHigh 1 : RightHigh 1;}bool _IsBalance(Node* root){if (root nullptr)return true;int LeftHigh _High(root-_left);int RightHigh _High(root-_right);if (RightHigh - LeftHigh ! root-_bf){cout _root-_kv.first 当前节点平衡因子有问题 endl;return false;}return abs(LeftHigh- RightHigh) 2 _IsBalance(root-_left) _IsBalance(root-_right);}
private:Node* _root nullptr;
};
test.c
//AVL树
#includeAVLTree.h
int main()
{int a[] { 16,3,7,11,9,26,18,14,15 }; AVLTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.Inorder();cout 输出1代表是AVL树输出0代表不是 t.IsBalance() endl;return 0;
}
运行结果 四、总结 AVL树的理解和实现总体来说还是比较难的思路一定要搞清楚代码实现上尽力而为 感谢各位大佬观看创作不易还请各位大佬点一个小小的赞
