顶部固定网站模板,金阊企业建设网站公司,分类目录检索,公司网页建立本章完整代码gitee地址#xff1a;平衡二叉搜索树 文章目录 #x1f333;0. 前言#x1f332;1. AVL树概念#x1f334;2. 实现AVL树#x1f33f;2.1 结构定义#x1f33f;2.2 插入#x1f490;左单旋#x1f490;右单旋#x1f490;左右双旋#x1f490;右左双旋 平衡二叉搜索树 文章目录 0. 前言1. AVL树概念2. 实现AVL树2.1 结构定义2.2 插入左单旋右单旋左右双旋右左双旋 2.3 查找2.4 删除2.5 树的高度2.6 是否为平衡树2.7 遍历中序 0. 前言
C的map和set这两个容器的底层就搜索树关于搜索树之前此篇文章讲过数据结构——二叉搜索树但它可能会出现极端情况退化为链表 所以再次基础上就要将这颗树变为平衡的二叉搜索树——ALV树、红黑树本章讲解的是AVL树
1. AVL树概念
AVL树俄罗斯的两位数学家G.M.Adlson-Velskii和E.M.Landis在1962年发表的论文《An algorithm for the organization of information》公开了这种结构向二叉树插入一个新节点后保证每个左右子树的高度之差绝对值不超过1即可降低树的高度减少平均搜索的长度。
将左子树减去右子树的深度的值成为平衡因子BFBalance Factor由于绝对值不超过1则平衡因子的范围是**[-1,1]**如果超过就说明目前这棵树不是平衡的需要进行调整 由于树的左右子树是平衡的所以要对这棵树操作的时候最多进行高度次操作O(lonN) 满二叉树2h-1 N AVL树2h - X NX的范围为[12h-1-1]属于O(lonN)这个量级 2. 实现AVL树
2.1 结构定义
//定义成kv结构
templateclass K,class V
struct AVLTreeNode
{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){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;public://功能
private
}
2.2 插入
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-_left cur;}else{parent-_right 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 parent;parent parent-_parent;cur cur-_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);}break;}else{//防止写的代码有bugassert(false);}}return true;
}我们设平衡因子为右子树-左子树 新增左节点parent平衡因子减一 新增右节点parent平衡因子加一 更新后的parent平衡因子 0 说明parent所在子树高度不变无需继续更新祖先节点 更新后的parent平衡因子 1 或- 1说明parent所在子树高度发生变化影响祖先需要继续更新祖先节点 更新后的parent平衡因子 2 或 -2说明parent所在子树高度发生变化且不平衡需要对parent对所在子树进行旋转让其平衡 这里的平衡因子起到一个检测作用查看这棵树是否“生病”如果发现“生病”立即“治疗”所以不可能出现大于2的绝对值的平衡因子 左单旋
单纯右边高采用左单旋进行调整具体情况如图 核心操作
parent-right cur-left;cur-left parent;
左单旋实现
//左单旋
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;
}动态示例 右单旋
单纯的左边高采用右单旋进行调整具体情况如图 核心操作
parent-left cur-right;cur-right parent;
右单旋实现
//右单旋
void RotateR(Node* parent)
{Node* cur parent-_left;Node* curRight cur-_right;parent-_left cur-_right;//防止curRight为空if (curRight){curRight-_parent parent;}cur-_right parent;//保存父亲的父亲节点Node* ppnode parent-_parent;parent-_parent cur;if (parent _root) {_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-parent ppnode;}//更新平衡因子parent-_bf cur-_bf 0;
}动图示例 左右双旋
新插入节点在较高左子树的右侧采用右左双旋具体情况如图 平衡因子更新需要看cur-right的平衡因子情况 curRight 0它就是插入节点全部更新为0curRight 1c插入cur-_bf -1parent-_bf 0curRight -1b插入cur-_bf 0·parent-_bf 1 核心操作
以parent-left为旋转点左旋以parent为旋转点右旋根据curRight-_bf调整平衡因子
右左双旋
新插入节点在较高右子树的左侧采用右左双旋具体情况如图 这里平衡因子的更新不能和单旋一样直接更新为0要分情况我们这里主要是看cur-left的平衡因子 curLeft-_bf 0则它就是插入节点平衡因子全部更新为0curLeft-_bf 1c插入cur-_bf 0parent-_bf -1curLeft-_bf -1,b插入cur-_bf 1parent-_bf 0 核心操作
以为parent-right为旋转点右旋以parent为旋转点左旋根据curLeft-_bf更新平衡因子
右左双旋代码实现 //右左双旋void RotateRL(Node* parent){Node* cur parent-_right;Node* curLeft cur-_left;int bf curLeft-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){//curLeft为新增节点cur-_bf 0;curLeft-_bf 0;parent-_bf 0;}else if (bf 1){//curLeft右子树插入cur-_bf 0;curLeft-_bf 0;parent-_bf -1;}else if (bf -1){//curLeft左子树插入cur-_bf 1;curLeft-_bf 0;parent-_bf 0;}else{assert(false);}}动图示例 2.3 查找
//查找
Node* Find(const K key)
{return _Find(_root, key);
}因为_root是私有成员外部无法使用所以我们设置一个子函数
Node* _Find(Node* root, const K key)
{if (root nullptr || root-_kv.first key)return root;if (root-_kv.first key)return _Find(root-_left, key);elsereturn _Find(root-_right, key);
}2.4 删除
删除操作就不多说了注释写的特别清楚 基本思路就是 删除元素更新平衡因子 与插入类似但细节还是很多 //删除
bool Erase(const K key)
{return _Erase(key);
}子函数
bool _Erase(const K key)
{Node* parent nullptr;Node* cur _root;//查找元素while (cur){if (cur-_kv.first key){parent cur;cur cur-_left;}else if (cur-_kv.first key){parent cur;cur cur-_right;}elsebreak;}//该元素不存在if (cur nullptr)return false;//删除元素//1.左右子树都为空if (cur-_left nullptr cur-_right nullptr){//根节点直接删除退出if (cur _root){delete _root;_root nullptr;return true;}if (cur parent-_left){//删除的是左孩子parent-_bf;parent-_left nullptr;}else{//删除的是右孩子parent-_bf--;parent-_right nullptr;}delete cur;cur parent;}else if (cur-_left nullptr) //左子树为空{if (cur _root){_root cur-_right;cur-_right-_parent nullptr;delete cur;cur nullptr;return true;}//因为是平衡二叉树如果左子树为空那么右子树至多只有一个节点//这里前面已经判断了双空的情况那么肯定右子树只有一个节点,直接删除即可Node* curRight cur-_right;//替换元素cur-_kv.first curRight-_kv.first;cur-_kv.second curRight-_kv.second;//删除节点cur-_right nullptr;delete curRight;curRight nullptr;//删右孩子父节点平衡因子-1cur-_bf--;}else if (cur-_right nullptr) //右子树为空{if (cur _root){_root cur-_left;cur-_left-_parent nullptr;delete cur;cur nullptr;return true;}//与左子树为空同理Node* curLeft cur-_left;//替换元素cur-_kv.first curLeft-_kv.first;cur-_kv.second curLeft-_kv.second;//删除节点cur-_left nullptr;delete curLeft;curLeft nullptr;//删除左孩子父节点平衡因子1cur-_bf;}else{//左右子树都不为空//以左子树最大元素为例parent cur; //前驱Node* prev cur-_left; //找左子树最大元素while (prev-_right){parent prev;prev prev-_right;}//替换元素cur-_kv.first prev-_kv.first;cur-_kv.second prev-_kv.second;//右边肯定没有元素了因为找的就是最大的元素左子树里面的最右边if (parent-_left prev){parent-_left prev-_left; parent-_bf;}else{parent-_right prev-_left;parent-_bf--;}delete prev;prev nullptr;//指向删除节点父亲cur parent;}parent cur-_parent;//重新找调整位置if (cur-_bf -2 || cur-_bf 2){if (cur-_bf -2){Node* curLeft cur-_left;parent cur;cur curLeft;}else{Node* curRight cur-_right;parent cur;cur curRight;}}//if (cur-_bf 0 parent ! nullptr abs(parent-_bf) 2)//{// if (cur parent-_left)// cur parent-_right;// else// cur parent-_left;//}while (parent){//更新父亲的平衡因子parent-_bf UpdateBf(parent);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 if (parent-_bf 2){//cur-_bf 0时RotateL(parent);//再更新一次parent-_bf UpdateBf(parent);}else if (parent-_bf -2){RotateR(parent);parent-_bf UpdateBf(parent);}else{assert(false);}}cur parent;parent cur-_parent;}return true;
}
int UpdateBf(Node* root)
{if (!root)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return rightH - leftH;
}2.5 树的高度
int _Height(Node* root)
{if (root nullptr)return 0;//记录深度int leftH _Height(root-_left);int rightH _Height(root-_right);//记录更深的那一个return std::max(leftH, rightH) 1;
}2.6 是否为平衡树
bool _IsAVLTree(Node* root)
{//空树符合AVL树if (root nullptr)return true;//左子树的高度int leftH _Height(root-_left);//右子树高度int rightH _Height(root-_right);//看平衡因子是否符合int bf rightH - leftH;if (bf ! root-_bf)return false;//平衡因子绝对值不大于//在一次递归左右子树return abs(bf) 2 _IsAVLTree(root-_left) _IsAVLTree(root-_right);
}2.7 遍历中序
void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);
}那本次分享就到这里咯AVL树主要是重点了解其中是如何变平衡的各种旋转在实际中我们只有使用C里面的map和set底层是红黑树。
我们下期再见咯如果还有下期的话。 Tips 如果代码有bug希望大家能指出来看了网上好多的都有bug 不知道这个有没有bug我测了一些数据目前没发现bug
