宣城市市政建设集团公司网站,seo外包上海,网站建设需要会什么,百度seo和谷歌seo有什么区别目录
前言#xff1a;
1 AVL树的创建
2 部分成员函数
2.1 查找
2.2 中序遍历
2.3 插入
2.4 左旋转
2.5右旋转 前言#xff1a;
上文#xff0c;上上文提到了map set#xff0c;二叉搜索树#xff0c;其实都是为了近两文做铺垫的#xff0c;虽然map的底层是红黑树…目录
前言
1 AVL树的创建
2 部分成员函数
2.1 查找
2.2 中序遍历
2.3 插入
2.4 左旋转
2.5右旋转 前言
上文上上文提到了map set二叉搜索树其实都是为了近两文做铺垫的虽然map的底层是红黑树但是也为AVL树的学习打下了基础那么什么是AVL树呢由谁发明的呢 两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis发明的名字就是发明家的首字母咯发明是用来干什么的呢发明出来是为了解决当树的结构趋近于单链表时候效率接近O(N)的问题只要能有效降低高度那么就能提高速度所以AVL树诞生了。
创建AVL树有很多种方式我们本次介绍的是使用的平衡因子的概念也就是每个节点都有个平衡因子绝对值不能超过1也就是取值范围是0 1 -1如果超过2也就代表树失衡了需要进行旋转调整。
这里旋转右子树高度减左子树高度的值作为平衡因子的大小当然AVL树的满足条件就是左右子树都是AVL树并且每个节点的平衡因子都小于2。 1 AVL树的创建
AVL树的创建和二叉平衡搜索树是一样的无非是每个节点的区别而已前言上文提及节点涉及到的内容有平衡因子左右指针key或者是key-value这里我们使用key-value模型实现。
但是当我们旋转的时候涉及到的节点势必有某个节点的父节点所以还有一个成员变量指向父节点的指针所以AVL树实际上是三叉链的结构
templateclass T, class V
struct AVLTreeNode
{AVLTreeNodeT* _left;AVLTreeNodeT* _right;AVLTreeNodeT* _parent;pairT, V _kv;int _bf;//平衡因子AVLTreeNode(const pairT,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};这就是节点的创建。
那么AVL树的大体如下
templateclass T
class AVLTree
{
public:typedef AVLTreeNodeT, V Node;private:Node* _root nullptr;
}; 2 部分成员函数
这里要实现的成员函数有左旋右旋以及查找插入(实现一半)以及中序遍历。
但是部分函数其实变化不打改的都是细枝末节的东西这里直接给代码即可
2.1 查找
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;
}
2.2 中序遍历 void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}
2.3 插入
插入和二叉搜索树都是一样的但是呢插入完成之后平衡因子怎么改变呢 我们现在不妨来分析一下平衡因子在插入后会有哪些改变
当我们在8的左边插入数据后8的平衡因子变为了0此时父节点的平衡因子就不用更新了因为作为7的右子树来说8这个子树的高度没有变。
当我们在6的任意部分插入数据6的平衡因子变为了1或者是-1此时需要往上更新数据7的平衡因子被更新为了0那么不用往上了所以此时我们就可以发现一个规律基于原有的AVL树的基础上插入数据之后平衡因子变为0的都不用继续遍历了因为平衡了但是要注意是 基于原来的树就是AVL树。
当我们在9的右边插入数据此时9的平衡因子变为了1往上更新8的平衡因子变为了2那么就需要旋转了此时是完全的右子树高所以需要左旋转。
当我们在9的右边插入数据此时9的平衡因子变为了1往上更新8的平衡因子变为了2那么就需要旋转了此时是完全的右子树高所以需要左旋转。
当我们在0的左边边插入数据此时0的平衡因子变为了-1往上更新1的平衡因子变为了-2那么就需要旋转了此时是完全的左子树高所以需要右旋转。
所以插入这里要干的事是更新平衡因子一直往上更新直到出现0或者是更新到根节点位置更新到根节点也就说明了父节点为空就可以结束了为0也可以直接结束
bool Insert(const pairT,V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* root _root;Node* parent nullptr;//判断部分while (root){if (kv.first root-_kv.first){parent root;root root-_right;}else if (val root-_kv.first){parent root;root root-_left;}else{return false;}}Node* newnode new Node(kv);//连接部分 开始判断大小关系if (parent-_key kv.first){parent-_left newnode;}else{parent-_right newnode;}//更新平衡因子newnode-_parent parent;while (parent){if (parent-_left newnode){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){newnode parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//右单旋if (parent-_bf -2 || newnode-_bf -1){RotateR(parent);}//左单旋else if (parent-_bf 2 || newnode-_bf 1){RotateL(parent);}else if (parent-_bf 2 || parent-_bf -1){}else{}}else{//理论而言不可能出现这种情况assert(false);}}return true;
}
为了保险期间出现了超过2的情况就要报错了。
现在的问题就是面对完全的右子树高或者是完全的左子树高我们应该怎么操作
2.4 左旋转 此时这棵AVL树就不平衡了那么我们可以从一个有趣的角度来看7是当家的8的二当家6是三当家当家的不管事二当家一不小心做大做强了那么当家的就得易主了是吧所以7要下位了此时8的左子树就应该指向7那么7的右子树就应该指向8的左子树空也没有关系。那么旋转完成了吗没有现在不够形象换个结构我们这样看 旋转的核心就是这两条线的指向二号指向7一号指向7.5这个过程大家脑部一下就十分形象了。
但是不要忘了AVL树实际上是三叉链结构所以还有父节点需要更新二号的节点如果不为空父节点应该指向的是77如果不是根节点那么我们还要用7的父节点作为连接的下一步判断相对位置让7的父节点连8如果是根节点那么根节点易位就可以了。此时连接的差不多了但是涉及到的8的父节点还要连接可能是空也可能是7的父节点这里代码给上结合文字的说明代码写的也是有区域性的结合相对来说好理解许多
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;subR-_left parent;parent-_right subRL;parent-_parent subR;//可能为空比如接近单链表if (subRL){subRL-_parent parent;}//旋转的时候判断是不是根节点if (parent _root){_root subR;subR-_parent nullptr;}else{//根据位置进行连接Node* pparent parent-_parent;if (parent _root-_left){_root-_left subR;}else{_root-_left subRL;}//三叉链记得更新完subR-_parent _pparent;}//更新平衡因子parent-_bf subR-_bf 0;
}
2.5右旋转
右旋转的是同理的就直接给代码了
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;subL-_right parent;parent-_left subLR;parent-_parent subL;if (subLR)subLR-_parent parent;if (parent _root){_root subL;subL-_parent nullptr;}else{Node* pparent parent-_parent;if (parent _root-_left){_root-_left subL;}else{_root-_right subL;}subL-_parent pparent;}//更新平衡因子parent-_bf subL-_bf 0;
}
以上两种情况是完全的左右子树高所以只需要一个左旋或者是右旋下篇是复合旋转
至于为什么平衡因子旋转之后一定为0请见下文~ 感谢阅读
