潍坊专业网站建设最新报价,海南省建筑信息平台,帮做3d模型的网站,黄骅市属于AVL树
AVL树的定义
avl本质是搜索树,是高度平衡二叉搜索树.特点是:任何树的左右子树的高度差不超过1.最大的高度差值最大也只能是1,也称之为平衡因子,
平衡因子就是右子树减去左子树的值,这个值的绝对值的最大值只能是1.这个平衡因子不是必须的,只是一种控制方式,方便我们更…AVL树
AVL树的定义
avl本质是搜索树,是高度平衡二叉搜索树.特点是:任何树的左右子树的高度差不超过1.最大的高度差值最大也只能是1,也称之为平衡因子,
平衡因子就是右子树减去左子树的值,这个值的绝对值的最大值只能是1.这个平衡因子不是必须的,只是一种控制方式,方便我们更便捷的控制树.
节点的定义
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorpairK, V _kv;AVLTreeNode(const pairK,V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};向AVL树插入节点
先按着搜索树的规则插入节点接着利用平衡因子来观测该树是否还是AVL树 新插入的节点可能会影响该节点的部分祖先的平衡因子的值.更新规则:在c的左边新增,那么p-bf–,在c的右边新增,那么p-bf,那么是否还会继续影响祖先呢?取决于p的高度是否变化.更新之后:父亲的 平衡因子如果是0的话,那么p所在的子树的高度不变不会影响爷爷.(如果p的平衡因子更新之后是0,就说明过更新之前是1或者是-1,说明是在矮的那一边插入了节点,p的高度不变,不会影响爷爷.),此时更新结束更新之后p的平衡因子是1或者是-1,那么p所在的子树的高度变了.会影响爷爷,说明更新之前p-bf是0,在p的有一边插入之后,p的高度变化了,就会影响爷爷.更新之后p的平衡因子成了2或者是-2,此时p所在子树就不是AVL树了,那么就需要进行旋转处理了.最后c成了根节点之后,那么就是更新条件结束了 三种结束条件: 更新到root结束,p-bf0结束,旋转让parent所在子树的高度回到了插入之前,不会对上层的bf有影响,结束.
代码实现:
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{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur 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){RotateLR(parent);}else{RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}AVL中的旋转处理
根据插入数据的不同情况可以分为四种情况的
左单旋
当碰到如下图的情况:(红色的是插入节点之后节点对应的平衡因子的值,红色的方块代表插入了一个节点)
当c的右边增加了节点导致了p的平衡因子变成了2之后,此时将subR的左子树连接到parent的右子树上,紧接着将整个parent为根,a为左子树,b为右子树的整棵树连接到subR的左边.此时再计算平衡因子,发现都成了0,整棵树就满足了avl树的规则. 这里subR在插入节点之前,b子树和c子树的高度一定是相同的(高度也可以是0),只有如此,subR的节点的平衡因子才是0,假如b子树和c子树的高度不同,那么subR的平衡因子是值可能是1或者是-1,此时在subR的右边插入节点,subR节点的平衡因子可能会变成0或者是2,若变成0,avl树的更新就结束了,根本就不需要调整,若变成了2,那么需要调整的树就是subR这颗树,而不是parent这个树. 同理,a子树的节点的高度也一定是h 如果a子树的高度是h1,那么parent的平衡因子就是0了,此时无论是在parent的左边还是右边插入元素,都无法使parent的平衡因子更新成2或者是-2如果a子树的高度使h-1,那么此时这颗树根本就不是AVL树了,说明在新节点插入之前就不是AVL树 代码实现:
void RotateL(Node* parent)
{Node* subR parent-_left;Node* subRL subR-_right;Node* ppnode parent-_parent;parent-_right subRL;if(subRL) // subRL的高度可能是0subRL-_parent parent;subR-_left parent;parent-_parent subR;// 假如插入节点之前parent就是整棵树的根if(ppnode nullptr){_root subR;subR-_parent nullptr;}else{if(ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}parent-_bf 0;subR- _bf 0;
}右单旋
当遇到如下图的情况时:(红色是更新之后的平衡因子的值):
新节点插入到较高左子树的左侧,就使用右单旋.因为此时的树看上去就是整个左侧高,右侧低的形式
右单旋的方法:将subL的b这个右子树连接到parent的左边,紧接着,以parent为根,b为左子树,c为右子树的整棵树连接到subL的右边. 代码实现:
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* grandParent parent-_parent;parent-_left subLR;// 同理,subLR的高度可能是0 if(subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;// 假如插入节点之前parent就是整棵树的根if(_root parent){_root subL;subL-_parent nullptr;}else{if(grandParent-_left parent){grandParent-_left subL;}else{grandParent-_right subL;}subL-_parent grandParent;}parent-_bf 0;subL-_bf 0;
}左右双旋
当新的节点插入在较高左树的右边时,需要进行左右双旋.
假定是如下图的情况:
此时在h这个子树插入数据时,整棵树的左边是较高的,此时我们假如采用右旋转,则会:
会发现,右旋之后,值为30的节点的平衡因子还是-2,所以我们不能采用单旋了,使用双旋. 假设h是大于0的情况: 先将b子树拆分: 将b拆分为值为40(这里40只是例子,只要满足时大于30小于60即可)的节点和e子树和f子树,那么此时由e和f两个子树了,新的节点就会有两种选择了. 当在e子树插入数据时:以30为断点进行左单旋,接着对整棵树进行右单旋 通过图可知,最后形成的树是符合要求的,并且各自的平衡因子经过计算都是满足要求的. 当在f子树插入节点时: 对仍然对局部进行左单旋,接着对整棵树进行右单旋. 并且经过计算之后的平衡因子经过计算之后也是符合要求的. 当h0时: 此时e和f就不存在了, 当在30的右边插入节点时,就先对30为根的树进行做单旋,对整棵树进行右单旋.如下图所示,最终计算出的平衡因子都是符合要求的. 当在30的左边插入节点时:可以直接对整棵树进行右单旋即可. 最终形成的树的关键节点的平衡因子的如何确定:由上图可以看出规律 当h!0时 当新节点在e子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是0,60所在节点的平衡因子是1.当新节点在f子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是-1,60所在节点的平衡因子是0. 当h0时,这个三个关键节点的平衡因子都是0 如何确定规律呢? 因为e和f这两颗子树的高度是相同的.所以在e树插入数据时,e的parent的平衡因子就会更新为-1, 当是在f树插入节点时,f的parent的平衡因子就会更新成1. 当e和f不存在时: 代码实现: 可以就可以利用subL的右节点的平衡因子的值来确定关键节点的平衡因子的值 这里可以复用前面的代码,但是前面的左旋和右旋都会将节点的平衡因子都改成0.所以需要提前保存这个值 void RotateLR(Node* parent)
{// 记录节点,为了保存节点里的_bf的值.Node* subL parent-_left;Node* subLR subL-_right;// 提前保存好平衡因子,防止被修改int bf subLR-_bf;// 直接调用RotateL(parent-_left);RotateR(parent);if(bf -1){subLR-bf 0;subL-_bf 0;parent-_bf 1;}else if(bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if(bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{// 此时就不是AVL树. assert(false); }
}右左双旋
当新节点插入在较高右树的左侧时,需要右左双旋了.采用的是和左右双旋类似的思想 当h!0时 当在e树插入时: 当在f树插入时: 当h0时
代码实现:
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL -_bf;RotateR(parent-_right);RotateL(parent);if(bf -1){subRL -_bf 0;parent-_bf 0;subR -_bf 1;}else if(bf 1){subRL-_bf 0;parent-_bf -1;subR-_bf 0;}else if(bf 0){subRL-_bf 0;parent-_bf 0;subR-_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;}int Height(){return _Height(_root);}在写一个Isbalance函数检查函数的左右高度是否符合要求
bool _IsBalance(Node* root){if (root nullptr)return true;int balance _Height(root-_right) - _Height(root-_left);if (abs(balance) 2){cout 平衡 endl;return true;}else{cout 不平衡 endl;return false;}if (balance ! root-_bf){cout 平衡因子异常 ;return false;}return _IsBalance(root-_left) _IsBalance(root-_right);}但是这个函数使用的递归太多了,复杂度太高了.每次在计算高度差的时候,已经将高度给计算出来了,但是函数的最后还是要计算左右子树的高度.
balance的优化,使用一个引用来记录height的左右高度.
bool _IsBalance(Node* root,int Height){if (root nullptr){height 0;return true; }int balance _Height(root-_right) - _Height(root-_left);int leftHeight 0,rightHeight 0;// 左右子树只要有一个不是平衡树,就返回falseif (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first不平衡 endl;return false;}if (balance ! root-_bf){cout 平衡因子异常 ;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}结束
关于AVL树的讲解就到这里啦,如有不足,请在评论区指正,下期见!
