域名大全免费网站,泰安网络公司电话,网站建设情况简介,泰州网站建设设计AVL树是一棵平衡二叉搜索树
二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查 找元素相当于在顺序表中搜索元素#xff0c;效率低下
一种解决上述问题的方法#xff1a;当向二叉搜索树中插入新结点后#xff0…AVL树是一棵平衡二叉搜索树
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下
一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度平衡二叉搜索树就诞生了。
在这里主要实现他的调节功能。
首先在每一个节点了都需要一个平衡因子bf通过平衡因子判断是否平衡。
templateclass T, class V
struct AVLTreeNode
{AVLTreeNodeT,V* _parent; // 指向其父节点AVLTreeNodeT,V* _left;AVLTreeNodeT,V* _right;T _key;V _value;int bf; // 平衡因子AVLTreeNode(const T key T(), const V value V()):_parent(nullptr),_left(nullptr),_right(nullptr),_key(key),_value(value),bf(0){}
};bf为右子树的高度减左子树的高度也就是说平衡搜索二叉树要保持每一个节点里的bf都小于2大于-2。
在之前已经实现了通过插入就可以保持一颗搜索树。
插入代码(未调节)
templateclass T, class V
class AVLTree
{typedef AVLTreeNodeT, V AVLTreeNode;
public:AVLTree():_node(nullptr){ }bool Insert(const T key T(), const V value V()){if (_node nullptr){_node new AVLTreeNode(key,value);return true;}AVLTreeNode* cur _node;AVLTreeNode* parent nullptr; while (cur ! nullptr){if (cur-_key key){return false; }if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}if (key parent-_key){parent-_left new AVLTreeNode(key, value);parent-_left-_parent parent;}else{parent-_right new AVLTreeNode(key, value);parent-_right-_parent parent;}接下来就是对平衡因子的判断的对树的调节因为当我们插入一个节点其祖先节点可能都会发生改变。 可以看出当插入一个节点时其祖先节点可能受影响其他节点不受影响。
只需要向上调节并排查祖先的平衡因子。当某个祖先的平衡因子bf0的时候结束。
如何调节祖先的平衡因子与为什么bf0就结束呢 蓝色方框表示将要插入的节点
这里的bf指2的bf。
图一bf1左插入后bf0。
图二bf-1右插入后bf0。
图三bf0右插入后bf1。
图四bf0左插入后bf-1。
可以发现左插入bf--右插入bf
当插入后bf0其所有祖先的高度并没有被影响。
当插入后bf1/-1就要去向上判断祖先是否被影响图三图四(2的父节点)的bf均改变变为了1图五2的父节点的bf变为2需要调节了。
写一下向上的代码 while (parent){if (parent-_key key) // 通过key判断改变的是parent的左边还是右边{parent-bf--;}else{parent-bf;}if (parent-bf 0) // 原来是1或-1说明并没有改变高度{break;}else if (parent-bf 1 || parent-bf -1) // 原来是为0 其所有的祖先都可能被影响了{ // 往上走判断其祖先cur parent;parent parent-_parent;}// 开始旋转else if((parent-bf 2 || parent-bf -2))}看看是如何旋转的
将bf2/-2的节点定义为parent上调之前的parent定义为cur(cur-_parentparent)
左旋转:将cur-left给parent-right(原来cur是parent-right)parent变为cur-left。
右旋转将cur-right给parent-left(原来cur是parent-left)parent变为cur-right。 注意这里也很复杂需要考虑他们的_parent节点的连接和parent是否是头节点。
接下来具体讲一讲他们的分类 bf1/-1继续往上走看父节点的bf变化。 旋转一经过左旋转后就可以break了
旋转二就要复杂一点看看旋转二的分析 可以看到在parent-bf2cur-bf-1需要双旋的需要将左右旋结合。
左单旋 //左单旋void RotateL(AVLTreeNode* parent){if (parent nullptr || parent-_right nullptr)return;AVLTreeNode* subr parent-_right;AVLTreeNode* subrL subr-_left; //记录保证对cur-bf的正确修改parent-_right subr-_left;if (subr-_left){subr-_left-_parent parent;}subr-_left parent;AVLTreeNode* ppnode parent-_parent;parent-_parent subr;//对subr进行处理if (ppnode nullptr) // parent是头节点{subr-_parent nullptr;_node subr;}else{subr-_parent ppnode;if (ppnode-_left parent){ppnode-_left subr;}else{ppnode-_right subr;}}// 进行bf的修改if (parent-bf 2){if (subr-bf 1){parent-bf subr-bf 0;}if (subr-bf -1){if (subrL-bf 0){parent-bf subrL-bf subr-bf 0;}if (subr-bf -1){parent-bf subrL-bf 0;subr-bf 1;}}}}右单旋 void RotateR(AVLTreeNode* parent){if (parent nullptr){return;}AVLTreeNode* subl parent-_left;AVLTreeNode* sublR subl-_right;parent-_left subl-_right;if (subl-_right) // 为空就不用去管他的_parent{subl-_right-_parent parent;}subl-_right parent;AVLTreeNode* ppnode parent-_parent;parent-_parent subl;if (ppnode nullptr){subl-_parent nullptr;}else{subl-_parent ppnode;if (ppnode-_left parent){ppnode-_left subl;}else{ppnode-_right subl;}}if (parent-bf -2){if (subl-bf -1){subl-bf parent-bf 0;}if (subl-bf 1){if (sublR-bf 0){parent-bf sublR-bf subl-bf 0;}if (sublR-bf 1){parent-bf sublR-bf 0;subl-bf -1;}}}}旋转代码 // 开始旋转else if((parent-bf 2 || parent-bf -2)){if (parent-bf 2){if (cur-bf 1){RotateL(parent);}if (cur-bf -1){RotateR(cur); // 不会给平衡因子因为cur-parent!-2RotateL(parent);}}if (parent-bf -2){if (cur-bf -1){RotateR(parent);}if (cur-bf 1){RotateL(cur); // 不会给平衡因子因为cur-parent!-2RotateR(parent);}}break; // 旋转了就保证了当前的树是平衡树其祖先不需要判断了}对代码进行测试 void _InOrder(AVLTreeNode* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key root-_value endl;_InOrder(root-_right);}void InOrder(){_InOrder(_node);}bool _IsbalanceTree(AVLTreeNode* root, int high){if (root nullptr){high 0;return true;}int left_high 0;if (_IsbalanceTree(root-_left, left_high) false){return false;}int right_high 0;if (_IsbalanceTree(root-_right, right_high) false){return false;}if (left_high - right_high 1 || left_high - right_high -1){return false;}high 1 (left_high right_high ? left_high : right_high);return true; // 满足左子树为平衡二叉树 右子树为平衡二叉树 该树为平衡二叉树}//判断平衡bool IsbalanceTree(){int k 0;return _IsbalanceTree(_node, k);}void test4()
{AVLTreestring, int avl;avl.Insert(a, 1);avl.Insert(b, 2);avl.Insert(c, 3);avl.Insert(d, 4);avl.Insert(e, 5);avl.Insert(f, 6);avl.Insert(g, 7);avl.Insert(h, 8);avl.Insert(i, 9);avl.Insert(j, 10);//判断是否是平衡二叉搜索树// 搜索树avl.InOrder();// 平衡树if (avl.IsbalanceTree()){cout 是平衡树 endl;}
}结果
a 1
b 2
c 3
d 4
e 5
f 6
g 7
h 8
i 9
j 10
是平衡树
其实在耦合这块的话并不是很好将左右旋和右左旋单独实现并修改平衡因子能够实现高内聚低耦合。
希望能够彻底帮助你理解AVL树的旋转而不是仅依靠一张结论图搬公式
