天津网络建站模板,网站首页做几个关键词,北京网页制作培训班,来源门户网站源码这是关于一个普通双非本科大一学生的C的学习记录贴
在此前#xff0c;我学了一点点C语言还有简单的数据结构#xff0c;如果有小伙伴想和我一起学习的#xff0c;可以私信我交流分享学习资料
那么开启正题
今天分享的是关于AVLTree模拟实现
1.AVLTree概念
二叉搜索树可…这是关于一个普通双非本科大一学生的C的学习记录贴
在此前我学了一点点C语言还有简单的数据结构如果有小伙伴想和我一起学习的可以私信我交流分享学习资料
那么开启正题
今天分享的是关于AVLTree模拟实现
1.AVLTree概念
二叉搜索树可以缩短查找的效率但如果数据有序或接近有序二叉树将退化为单支树查找元素相当于在链表中搜索元素效率低下因此两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发现一种可以解决上面问题的树形结构为了纪念两位做出的贡献以他们的名字为这种树取了名字——AVLTree
AVLTree特性
1.它的左右子树都是AVLTree
2.左右子树高度差简称平衡因子的绝对值不大于1
如果一棵二叉搜索树是高度平衡的他就是AVLTree如果他有N个结点搜索的时间复杂度就是O(logN)
2.AVLTree结点的定义
AVLTree结点是一种三岔链不仅存储了左右子树结点的指针还要存储父亲结点的指针当然还要存储平衡因子以及pair
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};
3.AVLTree的插入
3.1插入流程
AVLTree树插入数据可以分为两步
1.按照二叉搜索树的方式插入新结点
2.调整结点的平衡因子
在平衡因子异常情况下需要旋转处理
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (nullptr _root){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//更新平衡因子while (parent){if (parent-_left cur)--parent-_bf;elseparent-_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){//...break;}}return true;}private:Node* _root nullptr;
};3.2AVLTree的旋转
3.2.1左单旋
新节点插入较高右子树的右侧——右右左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;subR-_parent ppNode;}else{ppNode-_right subR;subR-_parent ppNode;}}subR-_bf parent-_bf 0;
}
3.2.2右单旋
新节点插入较高左子树的左侧——左左右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;subL-_parent ppNode;}else{ppNode-_right subL;subL-_parent ppNode;}}subL-_bf parent-_bf 0;
}
3.2.3左右双旋
新节点插入较高左子树的右侧——左右先左单旋再右单旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}
}
3.2.4右左双旋
新节点插入较高右子树的左侧——右左先右单旋再左单旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else{parent-_bf 0;subR-_bf 0;subRL-_bf 0;}
} 旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新break跳出循环即可
4.AVLTree的验证
4.1验证其是二叉搜索树
插入数据后中旬遍历输出即可验证
void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);
}void Inorder()
{_Inorder(_root);
}
4.2验证其高度平衡
通过高度递归验证其是否平衡即可
int Height(Node* root)
{if (nullptr root)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);return (abs(leftHeight - rightHeight) 2) _IsBalance(root-_left) _IsBalance(root-_right);
}bool IsBalance()
{return _IsBalance(_root);
}
下面是验证代码
void Test_AVLTree1()
{AVLTreeint, int t;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//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(make_pair(e, e));}t.Inorder();
}void Test_AVLTree2()
{AVLTreeint, int t;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t.Insert(make_pair(e, e));}cout t.IsBalance() endl;
}
新手写博客有不对的位置希望大佬们能够指出也谢谢大家能看到这里让我们一起学习进步吧
