网站开发合同及报价单,网站内容协议,阿泰勒北京网站建设,长沙做网站建设价格前言 大家好吖#xff0c;欢迎来到 YY 滴C系列 #xff0c;热烈欢迎#xff01; 本章主要内容面向接触过C的老铁 主要内容含#xff1a; 欢迎订阅 YY滴C专栏#xff01;更多干货持续更新#xff01;以下是传送门#xff01; 目录 一.AVL树的概念二.AVL树节点的定义(代码… 前言 大家好吖欢迎来到 YY 滴C系列 热烈欢迎 本章主要内容面向接触过C的老铁 主要内容含 欢迎订阅 YY滴C专栏更多干货持续更新以下是传送门 目录 一.AVL树的概念二.AVL树节点的定义(代码演示)三.Avl树的基本操作插入四.AVL树的核心操作旋转【1】新节点插入较高右子树的右侧---右右左单旋【2】新节点插入较高左子树的左侧—左左右单旋【3】新节点插入较高左子树的右侧---左右先左单旋再右单旋【4】新节点插入较高右子树的左侧---右左先右单旋再左单旋 五.AVL树的验证1. 验证其为二叉搜索树2. 验证其为平衡树 六.AVL树的性能引入红黑树七.AVL树的完整代码 一.AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证 每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 平衡因子是-1左比右高1平衡因子是1右比左高1平衡因子是0左右一样高 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 1. 它的左右子树都是AVL树 2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 二.AVL树节点的定义(代码演示) 除了基本的左右孩子节点与数据外还需要引入平衡因子 由于平衡因子取决于左右子树相对高度所以节点本身 要能够返回父亲节点 —— 要设置指向父亲节点的指针 注意AVL树节点是三叉链 templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _pLeft; // 该节点的左孩子AVLTreeNodeT* _pRight; // 该节点的右孩子AVLTreeNodeT* _pParent; // 该节点的父亲节点T _data;int _bf; // 该节点的平衡因子
};三.Avl树的基本操作插入 AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子 AVL树的插入过程与二叉搜索树同理二叉搜索树博客传送门https://blog.csdn.net/YYDsis/article/details/134374001?spm1001.2014.3001.5501 平衡因子的变化步骤 新增在左parent平衡因子减减新增在右parent平衡因子加加平衡因子0高度不变直接break平衡因子1/-1高度改变- 会影响祖先 - 需要继续沿着到根节点root的路径向上更新 平衡因子2/-2高度改变 树不再平衡 -会影响祖先-需要对parent所在子树进行 旋转 操作让其平衡 旋转部分放在part4中详解 向上更新直到根节点根节点parent0 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;}//1. 按照二叉搜索树的方式插入新节点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;//2. 调整节点的平衡因子while (parent)//向上更新直到根节点根节点parent0{if (cur parent-_left)// 1.新增在左parent平衡因子减减{parent-_bf--;}else // if (cur parent-_right){parent-_bf;//2.新增在右parent平衡因子加加}if (parent-_bf 0)//3.平衡因子0高度不变直接break{// 更新结束break;}//4.平衡因子1/-1高度改变- 会影响祖先 - 需要继续沿着到根节点root的路径向上更新else if (parent-_bf 1 || parent-_bf -1){// 继续往上更新cur parent;parent parent-_parent;}//平衡因子2/-2高度改变 树不再平衡 -会影响祖先-//需要对parent所在子树进行 旋转 操作让其平衡else if (parent-_bf 2 || parent-_bf -2){// 子树不平衡了需要旋转 旋转部分为何这么设计放在part4中详解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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}}return true;}四.AVL树的核心操作旋转 根据part3中avl树的基本操作插入以下情况会出现旋转平衡因子2/-2高度改变 树不再平衡 -会影响祖先-需要对parent所在子树进行 旋转 操作让其平衡 旋转部分放在part4中详解所以一共有四种情况分别如下图所示旋转要注意以下两点 1. 保持这颗树还是搜索树 2. 变成平衡树降低其高度 【1】新节点插入较高右子树的右侧—右右左单旋 分析如下图所示新节点插入较高右子树的右侧时候整体会发生“向左的单旋” 核心操作 cur-_right parent; parent-_parent cur; 代码展示 void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}【2】新节点插入较高左子树的左侧—左左右单旋
【3】新节点插入较高左子树的右侧—左右先左单旋再右单旋
【4】新节点插入较高右子树的左侧—右左先右单旋再左单旋
五.AVL树的验证
1. 验证其为二叉搜索树 如果其通过 中序遍历 可得到一个有序的序列就说明为二叉搜索树 2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确 六.AVL树的性能引入红黑树 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。 因此需要 引入红黑树传送门如下所示 红黑树博客传送门 七.AVL树的完整代码
#pragma once#includeiostream
#includeassert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};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;}else{parent-_left cur;}cur-_parent parent;// ... 控制平衡// 更新平衡因子while (parent){if (cur parent-_left){parent-_bf--;}else // if (cur parent-_right){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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){cur-_bf 0;curleft-_bf 0;parent-_bf 0;}else if (bf 1){cur-_bf 0;curleft-_bf 0;parent-_bf -1;}else if (bf -1){cur-_bf 1;curleft-_bf 0;parent-_bf 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){parent-_bf 0;cur-_bf 0;curright-_bf 0;}else if (bf -1){parent-_bf 1;cur-_bf 0;curright-_bf 0;}else if (bf 1){parent-_bf 0;cur-_bf -1;curright-_bf 0;}}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;int leftHight Height(root-_left);int rightHight Height(root-_right);if (rightHight - leftHight ! root-_bf){cout 平衡因子异常: root-_kv.first- root-_bf endl;return false;}return abs(rightHight - leftHight) 2 IsBalance(root-_left) IsBalance(root-_right);}private:Node* _root nullptr;public:int _rotateCount 0;
};
