360弹出网站,移动端适配,做外贸生意哪个网站好,深圳计算机速成班培训AVL树 什么是AVL树?AVL树节点的定义AVL树的插入平衡因子调整旋转调整左旋转右旋转左右双旋右左双旋 AVL树完整代码实现 什么是AVL树?
AVL是1962年,两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis 为了解决如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找… AVL树 什么是AVL树?AVL树节点的定义AVL树的插入平衡因子调整旋转调整左旋转右旋转左右双旋右左双旋 AVL树完整代码实现 什么是AVL树?
AVL是1962年,两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis 为了解决如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下的问题 ,因此发明了一种特殊的二叉搜索树,并以他们的名字命名为AVL树. 相比于普通的二叉树来说,AVL树的节点定义多了一个平衡因子: 平衡因子 右子树的高度 - 左子树的高度 因为AVL树需要通过平衡因子来确保它的特性,而AVL树的特性有以下几点:
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
因为有上面两点的限制,当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过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树中,若插入一些节点需要对AVL树的节点进行旋转调整等,在进行旋转调整的时候需要记录当前节点父节点的位置,因此在AVL树的节点定义如下:
templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data T()): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _left; AVLTreeNodeT* _right;AVLTreeNodeT* _parent;T _data;int _bf; // 节点的平衡因子
};平衡因子_bf应初始化为0
AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。 但是AVL树插入值的时候会有平衡因子的改变,那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
平衡因子调整 新增节点在父节点的左边 bf– 新增节点在父节点的右边 bf 在更新后: 插入节点之前,父亲的bf 为 1 或者 -1 ,插入节点在低的子树那边,那么更新后父亲的 bf 0 ,左右子树高度不变,插入结束 插入前父节点的bf 0,更新后父亲的 bf 1 || bf -1 ,父亲所在子树高度变了,需要继续往上更新 父亲节点bf更新后为 2 或者 -2,则说明需要进行调整
新增节点可能会影响祖先,因此插入节点后,需要查看子树的高度是否变化:
若子树高度不变,就不会影响祖先若子树高度改变,就会影响祖先
如下图,虽然增加了一个节点,但是并不影响节点 7 这颗子树的高度,因此祖先节点5就不会改变 但是出现下面这种情况,就需要进行调整了 因为新插入的节点影响了父节点 9 的高度,进而影响了 8 节点的平衡因子变成了2 这种时候就需要进行调整了
旋转调整
AVL树正式因为有旋转调整这一必杀利器因此才能保证它一直是AVL树而旋转调整又分为左旋转右旋转左右旋转右左旋转 四种旋转分别对应种不同的情况接下来看看这些旋转的条件及思想 而旋转的必要条件就是父亲节点的bf -2 || bf 2:parent-_bf -2 || parent-_bf 2
左旋转
左旋转的条件: parent-_bf 2 cur-_bf 1 如图: 简易版:
综合版
代码实现:
// 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* pparent parent-_parent;parent-_parent subR;if (subRL){subRL-_parent parent;}if (parent _root){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}parent-_bf subR-_bf 0;}右旋转
右旋转的条件:parent-_bf -2 cur-_bf -1 思想: 简易版: 综合版
左右双旋
左右双旋的条件:parent-_bf -2 cur-_bf 1 思想: 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。 代码实现
// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);//此节点本身就是插入节点if (bf 0){parent-_bf subL-_bf subLR-_bf 0;}else if (bf 1) //右子树的高度较高{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1) //左子树的高度较高{parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}右左双旋
右左双旋的条件:parent-_bf 2 cur-_bf -1 思想: 右左双旋代码实现:
// 右左双旋void RotateRL(Node* parent){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 subRL-_bf 0;}else if (bf -1){//subRL 的左子树新增节点parent-_bf 0;subR-_bf 0;subRL-_bf 1;}else if (bf 1){//subRL 的右子树新增节点 parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}AVL树完整代码实现
此代码种包含了AVL树平衡的判断和中序遍历
#pragma once
#includeiostream
#includeassert.husing namespace std;templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data T()): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _left;AVLTreeNodeT* _right;AVLTreeNodeT* _parent;T _data;int _bf; // 节点的平衡因子
};// AVL: 二叉搜索树 平衡因子的限制
templateclass T
class AVLTree
{typedef AVLTreeNodeT Node;
public:// 在AVL树中插入值为data的节点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-_left;}else if (cur-_data data){parent cur;cur cur-_right;}else{return false;}}cur new Node(data);if (parent-_data data){parent-_left cur;}else{parent-_right 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){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;}bool Isbalance(){return _Isbalance(_root);}void InOrder(){_InOrder(_root);cout endl;}private:// 右单旋void RotateR(Node* parent){Node* pparent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;parent-_parent subL;subL-_right parent;if (subLR){subLR-_parent parent;}if (_root parent){_root subL;subL-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}parent-_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;parent-_parent subR;if (subRL){subRL-_parent parent;}if (parent _root){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}parent-_bf subR-_bf 0;}// 右左双旋void RotateRL(Node* parent){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 subRL-_bf 0;}else if (bf -1){//subRL 的左子树新增节点parent-_bf 0;subR-_bf 0;subRL-_bf 1;}else if (bf 1){//subRL 的右子树新增节点 parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);//此节点本身就是插入节点if (bf 0){parent-_bf subL-_bf subLR-_bf 0;}else if (bf 1) //右子树的高度较高{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1) //左子树的高度较高{parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}//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(Node* root){if (root nullptr){return true;}int leftHeight _height(root-left);int rightHeight _height(root-right);if (root-_bf ! rightHeight - leftHeight){cout root-_data 节点bf异常 endl;}return abs(leftHeight - rightHeight) 2 _Isbalance(root-_left) _Isbalance(root-_right);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}private:Node* _root nullptr;
};
