吉林网站seo,手机做任务佣金的网站,怎么免费建个人网站,太平洋在线企业建站系统AVL树是啥
一提到AVL树#xff0c;脑子里不是旋了#xff0c;就是悬了。
AVL树之所以难#xff0c;并不是因为结构难以理解#xff0c;而是因为他的旋转。
AVL树定义
平衡因子#xff1a;对于一颗二叉树#xff0c;某节点的左右子树高度之差#xff0c;就是该节点的…AVL树是啥
一提到AVL树脑子里不是旋了就是悬了。
AVL树之所以难并不是因为结构难以理解而是因为他的旋转。
AVL树定义
平衡因子对于一颗二叉树某节点的左右子树高度之差就是该节点的平衡因子AVL树对于一颗二叉树任意节点的平衡因子bf 在范围[-11]之间即左右子树高度差的绝对值1则该树就是平衡二叉树
为何会有AVL树
AVL树是二叉搜索树的衍生其名字来源是根据两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis他们在1962年发明的一种用来解决二叉搜索树在极端情况下时间复杂度变为O(n)的情况。而其解决该情况的方法便是通过旋转旋转来调整二叉搜索树的平衡
AVL树的节点
AVL树的节点实现方式有很多这里采取下面的方法定义节点
templateclass Tstruct 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树节点的实现增加了_bf 平衡因子成员变量用来记录每个点的平衡因子。同时用了父节点的指针_parent 目的是方便调整平衡因子。
AVL树的插入
这里AVL树的插入操作与二叉搜索树一样唯一不同的是在插入后要调整平衡因子
对于插入的节点因为其是插入到叶节点位置所以他的平衡因子为0将节点插入后树的高度可能会发生改变此时则要调整他父亲甚至还要调整父亲的父亲的平衡因子。主要分为以下几种情况 情况1 如果在节点的右孩子插入则该节点的bf需要1节点70、50的bf连锁着发生了变化后面有说明 情况2 如果在节点的左孩子插入则该节点的bf需要-1节点70、50的bf连锁着发生了变化后面有说明 但是没完 如果节点的平衡因子因为插入而变成了1 或者-1 则说明子树的高度发生了变化此时该节点的父节点的bf也应发生变化如果父节点的bf更改之后影响了“爷爷节点”则爷爷节点也要跟着跟着变化。所以上图中的70和50两节点的bf也要发生变化。 但是还没完 bf 的值有可能会变为2、-2则此时就需要进行旋转操作旋转完成后会手动调整bf保证其符合要求 代码
//插入操作
...
//调整平衡因子
cur newnode;
parent newnode-_parent;
while (parent)
{if (parent-_right cur){parent-_bf;}else if (parent-_left cur){--parent-_bf;}if (parent-_bf 0)//AVL树稳定了break出去break;else if (parent-_bf 1 || parent-_bf -1)//无需旋转但是需要更改父亲的平衡因子{cur parent;parent parent-_parent;}else if ()//需要旋转{}
}AVL树的旋转
重中之重也是难中之难
AVL树旋转的目的
AVL树是一个平衡二叉搜索树因为某些插入操作导致它不再平衡具体表现是平衡因子变为2或-2则此时为了使之平衡就需要进行旋转操作
AVL树旋转操作
AVL树的旋转主要分为4种情况
左旋右旋左旋再右旋双旋右旋再左旋双旋 情况1左旋 对于插入后父亲的bf2右孩子的bf1的情况采用左旋。且左旋后平衡因子都是0 情况2右旋 对于插入后父亲的bf-2左孩子的bf-1的情况采用右旋。且右旋后平衡因子都是0 双旋 这种情况的发生是因为发现对该节点无论左旋还是右旋都无法使其平衡原因是插入节点的位置比较特殊 情况3左旋再右旋 对于插入这里插入b还是c只会影响旋转完后的平衡因子后父亲的bf-2左孩子的bf1的情况采用左旋再右旋。这里的平衡因子更新规则与前不同详见后文。 情况4先右旋再左旋 对于插入这里插入b还是c只会影响旋转完后的平衡因子后父亲的bf2右孩子的bf-1的情况采用右旋再左旋。这里的平衡因子更新规则与前不同详见后文。 双旋的平衡因子更新规则
更新规则相比旋转规则就简单许多
分为以下3种情况以上图为例
如果60的平衡因子旋转前是-1则更新后的60的平衡因子变为0左孩子变为0右孩子变为1如果60的平衡因子旋转前是1则更新后60的平衡因子变为0左孩子变为-1右孩子变为0如果60的平衡因子旋转前是0则更新后60的平衡因子变为0左孩子变为0右孩子变为0
代码
这里只给出一部分代码剩下的可以自己尝试写出来然后可以到仓库对照
bool insert(const pairK,V kv)
{//插入Node* newnode new Node(kv);if (newnode nullptr) return false;if (_root nullptr){_root newnode;return true;}Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (kv.first cur-_kv.first){cur cur-_right;}else cur cur-_left;}//调整节点连接if (kv.first parent-_kv.first)parent-_right newnode;else parent-_left newnode;newnode-_parent parent;//调整平衡因子cur newnode;parent newnode-_parent;while (parent){if (parent-_right cur){parent-_bf;}else if (parent-_left cur){--parent-_bf;}if (parent-_bf 0)//AVL树稳定了break出去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);}else{assert(false);}}}return true;
}
//左旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_parent subR;subR-_left parent;parent-_right subRL;if (subRL){subRL-_parent parent;}if (!pparent){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}parent-_bf 0;subR-_bf 0;
}
//先左旋再右旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){subLR-_bf 0;parent-_bf 0;subL-_bf 0;}else if (bf 1){subLR-_bf 0;parent-_bf 0;subL-_bf -1;}else if (bf -1){subLR-_bf 0;parent-_bf 1;subL-_bf 0;}else{assert(false);}
}
