当前位置： 首页 > news >正文

搜索网站logo怎么做做封面的网站在哪里

news 2025/10/22 20:19:19
搜索网站logo怎么做,做封面的网站在哪里,广州网络营销外包团队,简单网页制作成品免费0.前言 前面我们已经学习过二叉搜索树了，但如果我们是用二叉搜索树来封装map和set等关联式容器是有缺陷的，很可能会退化为单分支的情况，那样效率就极低了，那么有没有方法来弥补二叉搜索树的缺陷呢？ 那么AVL树就出现了&…

0.前言

前面我们已经学习过二叉搜索树了，但如果我们是用二叉搜索树来封装map和set等关联式容器是有缺陷的，很可能会退化为单分支的情况，那样效率就极低了，那么有没有方法来弥补二叉搜索树的缺陷呢？

那么AVL树就出现了，通过AVL树的右单旋、左单旋、左右单旋，右左单旋等操作来防止二叉搜索树退化为单分支的情况出现。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树也是以这两位大佬名字的首字母来命名的。

1.AVL树的概念

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树是AVL树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
     

我们这里使用的平衡因子是右子树高度 - 左子树高度。 

 

2.AVL树节点的定义

代码如下：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};

3.AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
     

插入思路：

 1.按照搜索树规则插入

2.更新插入节点的祖先节点的平衡因子

        a.插入父亲的右边，父亲的平衡因子--

        b.插入父亲的左边，父亲的平衡因子++

        c.父亲平衡因子 == 0， 父亲所在子树高度不变，不再继续往上更新。插入结束

        d.父亲平衡因子 == 1 or -1， 父亲所在子树高度变了，继续往上更新。

        e.父亲平衡因子 == 2 or -2， 父亲所在子树已经不平衡了，需要旋转处理。

更新中不可能出现其他值，插入之前树是AVL树，平衡因子要么是1 -1 0， ++ --

最多就是c/d/e三种情况。

 代码如下：

	bool Insert(const pair<K, 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;}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 == -2 && cur->_bf == -1){//右单旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋//RotateRL(parent);}break;}else{//理论上不会出现这种情况，但仍要判断，大佬都不能保证自己的代码没有bugassert(false);}}return true;}

4.AVL树的旋转

4.1 右单旋

插入新节点要插入较高左子树的左侧（左左）-》右单旋

图形解析：

 实现代码如下：

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

4.2 左单旋

插入新节点要插入较高右子树的右侧（右右）-》左单旋

图形解析：

 代码如下：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}

4.3 左右双旋

插入新节点要插入较高左子树的右侧（左右）-》左右双旋

图形解析：

对于插入的位置根据h的高度和插入的位置时的平衡因子出现的最终的结果可分为三种情况：

1.h == 0

        60自己就是新增节点。bf == 0

此时的平衡因子为，30 60 90节点都为0。

2.h > 0

        a.新增节点插入的是60的左子树中 bf == -1

此时的平衡因子为，30节点为0,90为0,60为1

        b.新增节点插入的是60的右子树中bf == 1

此时的平衡因子为，30节点为-1,90为0,60为0

代码如下：

 

	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 = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理论上不会出现的情况assert(false);}}

4.4 右左双旋

插入新节点要插入较高右子树的左侧（右左）-》右左双旋

与左右双旋类似

代码如下：

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(false);}}


总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
 

5.AVL树的验证

5.1 验证其是否为二叉搜索树

给一个序列进行一次中序遍历，看是否有序，有序即为二叉搜索树。

void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}

5.2 验证其是否为平衡树

	bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->right);}

6.AVL树的删除（了解）

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

7.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

 8.AVL树的整体模拟代码实现

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, 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;}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 == -2 && cur->_bf == -1){//右单旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋RotateRL(parent);}break;}else{//理论上不会出现这种情况，但仍要判断，大佬都不能保证自己的代码没有bugassert(false);}}return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}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 = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理论上不会出现的情况assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
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;}return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}
void TestAVLTree2()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();cout << t1.IsBalance() << endl;
}

http://www.yayakq.cn/news/575908/

相关文章：

  • 网站的建设心得茶叶设计网站建设
  • 网站推广服务好公司排名怎么分析一个网站seo
  • 江都建设集团有限公司官方网站网站qq显示未启用
  • 做网站用win还是li阿里云做网站可以吗
  • 个人做网站能赚到钱吗本机做网站如何访问
  • 郑州网站建设与制作怀来住房和城乡建设局网站
  • 网站跳转怎么做网站备份怎么做
  • wap网站制作需要多少钱wordpress 注册邮件设置密码
  • 网站收录查询apidw软件下载
  • 2免费做网站环球易购招聘网站建设
  • 公司制作一个网站三峡建设管理有限公司网站
  • 唐山模板网站建设动漫视频网站开发
  • 佛山学校网站建设鲁山网站建设
  • 网站建设网站软件有哪些微信免费建站
  • 茂名网站建设教腾讯企点和企业qq区别
  • 阿里云购买网站登录wordpress主题 开发
  • 哪些调查网站可以做问卷赚钱百度预测大数据官网
  • 商城网站一般建设的宽度网站稳定性
  • wordpress 首页折叠内页优化
  • 河北邯郸天气预报襄阳网站推广优化技巧
  • 揭阳新闻最新消息seo是干啥的
  • 毕业设计做视频网站溧阳网站建设哪家好
  • 此网站可能有餐厅网站建设
  • 网站建设 实施计划设计网站大全铲鼠湖南岚鸿相信
  • asp网站建设运用的技术免费海外云服务器
  • 免费建网站哪个模板多网站设计的性能需求
  • 做网站后期自己可以维护吗一般注册公司多少钱
  • 网站开发需要的编程软件品牌运营总监
  • 好的做网站公司网站建设报价单ppt
  • 服务商平台登录宁波受欢迎全网seo优化