农业 网站源码,凡科网站教程,网上商城网站建设方案,做风能的网站文章目录 AVL树旋转单旋右单旋左单旋 双旋左右双旋右左双旋 平衡因子的更新左右双旋右左双旋 判断是不是AVL树时间复杂度分析全部的代码 AVL树
旋转
单旋
单旋是纯粹的一边高 单旋平衡因子是同号
右单旋
a,b,c自身不能发生旋转 并且也不能不向上继续更新#xff08;不能停… 文章目录 AVL树旋转单旋右单旋左单旋 双旋左右双旋右左双旋 平衡因子的更新左右双旋右左双旋 判断是不是AVL树时间复杂度分析全部的代码 AVL树
旋转
单旋
单旋是纯粹的一边高 单旋平衡因子是同号
右单旋
a,b,c自身不能发生旋转 并且也不能不向上继续更新不能停止更新 插入之前是h2插入后进行旋转后是h2没有对pParent它的子树的高度产生影响不用继续向上更新
// 链接孩子和父亲
// 右单旋,旋转点是parent
void Rotate(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;// b可能为空树if (suLR ! nullptr)subLR-_parent parent;// 记录parent的parentpParent parent-_parent;subL-_right parent;parent-_parent subL;// 1. 10是这棵树的总根if (parent _root){subL _root;subL-_parent nullptr;}else{// 2. 10是这棵树的局部根// 就有父亲的父亲节点// pParent左可能是parent,右也可能是parentif (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}// 更新平衡因子subL-_bf 0;parent-_bf 0;}左单旋
左单旋和右单旋类似
// 左单旋,旋转点是parent
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;// b不是空树if (subRL)subRL-_parent parent;// 记录父亲节点的父亲节点Node* pParent parent-_parent;subR-_left parent;parent-_parent subR;// 1. 10是这棵树的总根if (_root parent){_root subR;subR-_parent nullptr;}else{// 2. 10是这棵树的局部根if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}subR-_bf 0;parent-_bf 0;
}双旋
双旋平衡因子会异号 双旋是进行两次单旋
对于5来说右边高对于10来说左边高需要进行双旋 下面是进行的单旋解决不了问题 对于5来说右边高对于10来说左边高需要进行双旋 进行单旋解决不了问题会变成下面的样子
左右双旋
h 0
h 1
右左双旋
右左双旋和左右双旋类似这里就不画了
平衡因子的更新
左右双旋
双旋和单旋的平衡因子更新方式不同双旋按照单旋的方式更新后5,108都是0不符合逻辑
左右双旋中h0和h1具体场景分析下面我们将a/b/c子树抽象为高度h的AVL 子树进行分析另外我们需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树因为 我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置 不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。
场景1h 1时新增结点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子 引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。场景2h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引 发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1。场景3h 0时a/b/c都是空树b自己就是一个新增结点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。 8的平衡因子会影响其它的平衡因子
插入到8的左边8的平衡因子为-1插入到8的右边8的平衡因子为18本身就是要插入的节点8的平衡因子为0
// 左右双旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;// 提前存平衡因子int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (subLR-_bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (subLR-_bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (subLR-_bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}
}右左双旋
跟左右双旋类似下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同这里我们要分三个场景讨论。
场景1h 1时新增结点插入在e子树e子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1。场景2h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。场景3h 0时a/b/c都是空树b自己就是一个新增结点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0。 3种情况
插入到e那边插入到f那边b本身就是插入的点
// 右左双旋
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树
用高度差的绝对值是否 1来检查
// 算树的高度,左右子树高的那个加1
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;
}// 判断是不是AVL树
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (root nullptr)return true;// pRoot的子树的平衡因子,左右子树的高度差int _leftheight _Height(root-_left);int _rightheight _Height(root-_right);int diff _rightheight - _leftheight;// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}else if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}// pRoot节点的左树和右树都是AVL树,那么就是AVL树return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}时间复杂度分析
插入logN,寻找插入的位置会找到叶子的位置 旋转常数次 调整假设最坏情况调整到根logN平衡因子为-1/1,要继续调整 时间复杂度logN
全部的代码
#pragma once
#includeiostream
#includeassert.husing namespace std;templateclass K, class V
struct AVLTreeNode
{// 需要parent指针pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;// 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)// 刚插入的节点平衡因子都是0{}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public: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 (parent-_left cur)parent-_bf--;else // if (parent-_right cur)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){// 右旋,左高右低RotateR(parent);}else if(parent-_bf 2cur-_bf 1){// 左旋,右高左低RotateL(parent);}else if(parent-_bf -2cur-_bf 1){// 左右双旋,右高左高RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){// 右左双旋,左高右高RotateRL(parent);}else{assert(false);}break;}else{// 逻辑错误,之前就不是AVL树assert(false);}}return true;}// 右单旋,旋转点是parentvoid RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;// b可能为空树if (subLR ! nullptr)subLR-_parent parent;// 记录parent的parentNode* pParent parent-_parent;subL-_right parent;parent-_parent subL;// 1. 10是这棵树的总根if (parent _root){_root subL;subL-_parent nullptr;}else{// 2. 10是这棵树的局部根// pParent左可能是parent,右也可能是parentif (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}// 更新平衡因子subL-_bf 0;parent-_bf 0;}// 左单旋,旋转点是parentvoid RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;// b不是空树if (subRL)subRL-_parent parent;// 记录父亲节点的父亲节点Node* pParent parent-_parent;subR-_left parent;parent-_parent subR;// 1. 10是这棵树的总根if (_root parent){_root subR;subR-_parent nullptr;}else{// 2. 10是这棵树的局部根if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}subR-_bf 0;parent-_bf 0;}// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;// 提前存平衡因子int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (subLR-_bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (subLR-_bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (subLR-_bf 0){subLR-_bf 0;subL-_bf 0;parent-_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);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);}}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}// 大小int Size(){return _Size(_root);}// 判断是不是AVL树bool IsBalanceTree(){return _IsBalanceTree(_root);}// 算树的高度int Height(){_Height(_root);}// 中序void InOrder(){_InOrder(_root);cout endl;}
private:// 算树的高度,左右子树高的那个加1int _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 _Size(Node* root){if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 1;}// 判断是不是AVL树bool _IsBalanceTree(Node* root){// 空树也是AVL树if (root nullptr)return true;// pRoot的子树的平衡因子,左右子树的高度差int _leftheight _Height(root-_left);int _rightheight _Height(root-_right);int diff _rightheight - _leftheight;// 高度差超过2或者pRoot的平衡因子不等于计算出的平衡因子就不是AVL树if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}else if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}// pRoot节点的左树和右树都是AVL树,那么就是AVL树return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}private:Node* _root nullptr;
};#includeAVLTree.hvoid TestAVLTree1()
{AVLTreeint, int t;// 常规的测试⽤例int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e, e });}t.InOrder();cout t.IsBalanceTree() endl;
}int main()
{TestAVLTree1();return 0;
}
