山东汽车行业网站开发,wordpress 索引插件,wordpress 中國,wordpress主题 dux2.0AVL树的概念
二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下。因此#xff0c;两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决…AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
节点的平衡因子右子树的高度-左子树的高度
例如 下图的二叉搜索树的每个节点的平衡因子的 绝对值都小于2并且每个节点的子树也都是AVL树
AVL树的定义
AVL树是一种特殊的二叉搜索树它具有高度的平衡所以为了在插入过程中的各个节点的平衡因子的更新我们在定义AVL树的节点结构的同时要带上一个节点的双亲结点parent
templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _left; // 该节点的左孩子AVLTreeNodeT* _right; // 该节点的右孩子AVLTreeNodeT* _parent; // 该节点的双亲T _data;int _bf; // 该节点的平衡因子
};AVL树的插入
AVL树的插入是一个难点它分为好几种情况其实AVL树的插入也就是在二叉搜索树中插入新节点但是由于他引入了平衡因子需要更新所以这里的插入节点就比较麻烦她一共分为两步
1 插入节点 2 更新节点的平衡因子
为什么要更新节点的平衡因子呢
简单地举个例子 如图所示我将一个新节点插入0的左孩子节点的位置那么以3为节点的这颗子树的高度差不就会超过1了吗他的左子树的高度插入新节点后为3而右子树为1这就不符合AVL树的性质了所以我们需要经过一些操作来更新平衡因子
这里大家需要注意一个规则 新节点如果是插入后他的parent的左侧那么他的平衡因子默认是1 反之插入他的右侧就是默认-1
那么在插入节点后各个插入节点的parent一共就有三种情况了
平衡因子为0 如果parent的平衡因子为0说明插入之前parent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功
平衡因子为正负1 如果parent的平衡因子为正负1说明插入前pParent的平衡因子一定为0插入后被更新成正负1此时以parent为根的树的高度增加需要继续向上更新防止部分节点的左右子树高度差超过1 平衡因子为正负2 如果parent的平衡因子为正负2则pParent的平衡因子违反平衡树的性质需要对其进行旋转处理旋转处理之后插入成功
至于旋转的情况我们待会分析我们先将插入节点的代码的主要框架构造出来 这样一个简单的框架就构造出来了
templateclass T
struct AVLTreeNode
{AVLTreeNodeT* _left; // 该节点的左孩子AVLTreeNodeT* _right; // 该节点的右孩子AVLTreeNodeT* _parent; // 该节点的双亲T _data;int _bf; // 该节点的平衡因子AVLTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}
};
templateclass T
class AVLTree
{typedef AVLTreeNodeT Node;
public:bool insert(const T data){if (_root nullptr){_root new Node(data);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_data data){parent cur;cur cur-_right;}else if (cur-_data data){parent cur;cur cur-_left;}else{return false;}cur new Node(data);if (parent-_data data){parent-_left cur;}else{parent-_right cur;}while (parent){//左边if (cur parent-_left){parent-_bf--;}//右边--else{parent-_bf;}//parent的平衡因子等于0插入成功if (parent-_bf 0){break;}//parent的平衡因子等于1或者-1继续向上更新else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//需要进行旋转}else{assert(false);}}}}private:Node* _root;
};下面我们就具体分析几种旋转的情况
AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
1. 新节点插入较高左子树的左侧—左左右单旋 下图中的h可以时0 1 2三种分别代表了这三个子树的高度无论他是等于0 1 还是2时他们都可以满足AVL树的要求 可以看到这种情况就是parent的平衡因子等于-2cur的平衡因子等于-1 左旋函数如下
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;//防止sublr为空if(subLR)subLR-_parent parent;//记录祖父位置Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;//如果父亲是根节点if (parent _root){_root subL;subL-_parent nullptr;}//parent不是根节点那么祖父就会成为subl的parentelse{if (pparent-_left parent){pparent-_left subL;subL-_parent pparent;}else{pparent-_right subL;subL-_parent pparent;}}//旋转后parent和subl的 平衡因子都会更新为0parent-_bf subL-_bf 0;
}2. 新节点插入较高右子树的右侧—右右左单旋 实现及情况考虑可参考右单旋。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* pparent parent-_parent;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;subR-_parent pparent;}else{pparent-_right subR;subR-_parent pparent;}}parent-_bf subR-_bf 0;
}3. 新节点插入较高左子树的右侧—左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。 直接复用即可 由于博主能力有限所以放入代码大家仔细理解
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;RotateL(parent-_left);RotateR(parent);int bf subLR-_bf;//sublr就是新增节点if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}//sublr左子树新增节点else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}//sublr右子树新增节点else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{assert(false);}
}4. 新节点插入较高右子树的左侧—右左先右单旋再左单旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//subrl这个点为新增点if (bf 0){parent-_bf subR-_bf subRL-_bf 0;}//subrl的左子树新增else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}//subrl的右子树新增else if (bf 1){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else{assert(false);}
}根据各种情况我们做了总结
假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑
parent的平衡因子为2说明parent的右子树高设parent的右子树的根为subR当subR的平衡因子为1时执行左单旋当subR的平衡因子为-1时执行右左双旋parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为subL当subL的平衡因子为-1是执行右单旋当subL的平衡因子为1时执行左右双旋旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。
所以我们可以补全上面的插入节点的代码了
bool insert(const T data)
{if (_root nullptr){_root new Node(data);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_data data){parent cur;cur cur-_right;}else if (cur-_data data){parent cur;cur cur-_left;}else{return false;}}cur new Node(data);if (parent-_data data){parent-_left cur;}else{parent-_right cur;}while (parent){//左边if (cur parent-_left){parent-_bf--;}//右边--else{parent-_bf;}//parent的平衡因子等于0插入成功if (parent-_bf 0){break;}//parent的平衡因子等于1或者-1继续向上更新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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}}return true;
}AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
我们可以用一个函数来判断即可 首先要有一个计算树的高度的函数 然后判断他们的子树的高度差的绝对值是否在2以内并且他们的子树也要是AVL树
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 leftheight Height(root-_left);int rightheight Height(root-_right);if (rightheight - leftheight ! root-_bf){cout root-_data 平衡因子异常 endl;return false;}return abs(rightheight - leftheight) 2 _isbalance(root-_left) _isbalance(root-_right);
}我们还可以用中序遍历打印
void inorder()
{_inorder(_root);cout endl;
}void _inorder(Node* root)
{if (root nullptr){return;}_inorder(root-_left);cout root-_data ;_inorder(root-_right);
}完整代码如下
#includeiostream
#includeassert.h
using namespace std;
templateclass T
struct AVLTreeNode
{AVLTreeNodeT* _left; // 该节点的左孩子AVLTreeNodeT* _right; // 该节点的右孩子AVLTreeNodeT* _parent; // 该节点的双亲T _data;int _bf; // 该节点的平衡因子AVLTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}
};
templateclass T
class AVLTree
{typedef AVLTreeNodeT Node;
public:bool insert(const T data){if (_root nullptr){_root new Node(data);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_data data){parent cur;cur cur-_right;}else if (cur-_data data){parent cur;cur cur-_left;}else{return false;}}cur new Node(data);if (parent-_data data){parent-_left cur;}else{parent-_right cur;}while (parent){//左边if (cur parent-_left){parent-_bf--;}//右边--else{parent-_bf;}//parent的平衡因子等于0插入成功if (parent-_bf 0){break;}//parent的平衡因子等于1或者-1继续向上更新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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;//防止sublr为空if(subLR)subLR-_parent parent;//记录祖父位置Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;//如果父亲是根节点if (parent _root){_root subL;subL-_parent nullptr;}//parent不是根节点那么祖父就会成为subl的parentelse{if (pparent-_left parent){pparent-_left subL;subL-_parent pparent;}else{pparent-_right subL;subL-_parent pparent;}}//旋转后parent和subl的 平衡因子都会更新为0parent-_bf subL-_bf 0;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* pparent parent-_parent;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;subR-_parent pparent;}else{pparent-_right subR;subR-_parent pparent;}}parent-_bf subR-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;RotateL(parent-_left);RotateR(parent);int bf subLR-_bf;//sublr就是新增节点if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}//sublr左子树新增节点else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}//sublr右子树新增节点else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_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);//subrl这个点为新增点if (bf 0){parent-_bf subR-_bf subRL-_bf 0;}//subrl的左子树新增else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}//subrl的右子树新增else if (bf 1){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}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 leftheight Height(root-_left);int rightheight Height(root-_right);if (rightheight - leftheight ! root-_bf){cout root-_data 平衡因子异常 endl;return false;}return abs(rightheight - leftheight) 2 _isbalance(root-_left) _isbalance(root-_right);}void inorder(){_inorder(_root);cout endl;}void _inorder(Node* root){if (root nullptr){return;}_inorder(root-_left);cout root-_data ;_inorder(root-_right);}private:Node* _rootnullptr;
};
好了今天的分享到这里就结束了感谢大家的支持
