阿里云建站售前咨询,建设游戏运营网站开展工作,电脑打不开网页但是能上网,学校怎么做网站目录 AVL树的概念
AVL树的节点结构
AVL树的插入
更新平衡节点
代码实现
AVL树的旋转
左单旋
右单旋
左右双旋
右左双旋
AVL树的删除
AVL树的查找
AVL树的高度
AVL树的判定
AVL树的遍历 AVL树的概念
二叉排序#xff08;搜索#xff09;树#xff0c;虽然可以…目录 AVL树的概念
AVL树的节点结构
AVL树的插入
更新平衡节点
代码实现
AVL树的旋转
左单旋
右单旋
左右双旋
右左双旋
AVL树的删除
AVL树的查找
AVL树的高度
AVL树的判定
AVL树的遍历 AVL树的概念
二叉排序搜索树虽然可以缩短查找的效率但是在数据接近有序的时候二叉排序树会退化成为单支树斜树相当于在顺序表中查找元素效率低下。
因此两位俄罗斯的数学家发明了一种解决上述问题的办法向二叉搜索树插入新的节点后通过调整保证左右子树的高度差绝对值不大于1从而降低树的高度减少平均搜索长度。
平衡二叉树Balanced Binary Tree是一种特殊的二叉排序树又称AVL树。
AVL树的性质
1.AVL树是二叉排序树
2.左右子树高度之差即平衡因子的绝对值不超过1即平衡因子可能为-101,
AVL树的节点结构
用KV模型定义二叉树把节点定义成三叉链结构因为构造的新节点左右子树都为空树所以平衡因子设为0 平衡因子右子树的高度-左子树的高度 templateclass K,class V
struct AVLTreeNode
{//存储的键值对pairK, V _kv;//平衡因子balance factorint _bf;//存储的三叉链AVLTreeNodeK, V* _parent;//方便找到父节点AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;//构造函数AVLTreeNode(const pairK, V kv):_kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _bf(0){}
};
AVL树的插入
更新平衡节点
AVL树插入结点时有以下三个步骤
1.按照二叉搜索树的插入方法找到待插入位置。 2.找到待插入位置后将待插入结点插入到树中。 3.更新平衡因子如果出现不平衡则需要进行旋转。 与二叉搜索树相比多了更新平衡因子这个步骤。因为插入节点后树的高度可能会变化 更新父节点的平衡因子一定要更新
1.左边插入parent的平衡因子--
2.右边插入parent的平衡因子
根据父节点的平衡因子判断是否要更新祖先节点的平衡因子
1.如果父节点bf0说明父节点原来一定是-1或1插入的节点弥补了原来的空缺树的高度没有改变不用向上更新
2.如果为-1说明平衡因子从0变成了-11高度改变所以要向上更新
3.如果为-2说明该父节点就是最小不平衡子树的根节点不用再向上查找 代码实现
class AVLTree
{typedef AVLTreeNodeK, V Node;
private:Node* _root;public:AVLTree():_root(nullptr){}bool Insert(const pairK,V kv){if (_root nullptr){_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 (cur-_kv.first parent-_kv.first) {parent-_left cur;cur-_parent parent;parent-_bf--;}else{parent-_right cur;cur-_parent parent;parent-_bf;}while (parent)//最远要更新到根节点{if (parent-_bf 0) {break;}else if (abs(parent-_bf) 1){cur cur-_parent;parent parent-_parent;//向上查找}else if(abs(parent-_bf)2){//判断是哪一种旋转情况if (parent-_bf2cur-bf1){rotateL(parent);}else if (parent-_bf -2 cur-bf -1){rotateR(parent);}else if (parent-_bf -2 cur-bf 1){rotateLR(parent);}else if (parent-_bf 2 cur-bf -1){rotateRL(parent);}break;}else{//如果程序走到这里说明在此之前就有不平衡的子树assert(false);}}return true;}
};
AVL树的旋转
左单旋
什么时候需要用到左旋操作呢
当 parent 的平衡因子为 2cur 的平衡因子为 1 时需要进行左单旋。
并且经过左单旋后树的高度没有发生变化所以左单旋后无需继续往上更新平衡因子。 步骤
先让 subR 的左子树subRL作为 parent 的右子树。然后让 parent 作为 subR 的左子树。接下来让 subR 作为整个子树的根。最后更新平衡因子。 代码实现
void rotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;//1.建立subRL与parent之间的关系//左子树滑动parent-_right subRL;if (subRL) {subRL-_parent parent;}//2.建立subR和parent之间的关系//更新右子树的左子树subR-_left parent;parent-_parent subR;//3.建立pparent和subR之间的关系//与上一个节点建立连接if (parent _root){_root subR;subR-_parent nullptr;}else{subR-_parent pparent;if (parent pparent-_left) {pparent-_left subR;}else{pparent-_right subR;}}//更新平衡因子parent-_bf 0;subR-_bf 0;}
右单旋 先让 subL 的右子树subLR作为 parent 的左子树。然后让 parent 作为 subL 的右子树。接下来让 subL 作为整个子树的根。最后更新平衡因子。
void rotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;//滑动parent-_left subLR;if (subLR) {subLR-_parent parent;}//更新左子树的右子树subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else {subL-_parent pparent;if (parent pparent-_left) {pparent-_left subL;}else{pparent-_right subL;}}parent-_bf 0;subL-_bf 0;}
左右双旋
(1)以30为节点进行左单旋 2以90为节点进行右单旋 左右双旋后平衡因子的更新随着 subLR 原始平衡因子的不同分为以下三种情况
1当 subLR 原始平衡因子是 -1 时左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0 2当 subLR 原始平衡因子是 1 时左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0 3当 subLR 原始平衡因子是 0 时说明 subLR 为新增结点左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0 可以看到经过左右双旋后树的高度没有发生变化所以左右双旋后无需继续往上更新平衡因子。
代码实现
void rotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;rotateL(subL);//parent并不为最小不平衡子树的根所以要在旋转以后重新赋值rotateR(parent);//各点的bf值由调整前subLR的bf值决定if (_bf 0) {parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}
右左双旋
1以 90 为旋转点进行右单旋 2以 30 为旋转点进行左单旋 右左双旋后平衡因子的更新随着 subLR 原始平衡因子的不同分为以下三种情况、
1当 subRL 原始平衡因子是 1 时左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0 2当 subRL 原始平衡因子是 -1 时左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0 3当 subRL 原始平衡因子是 0 时说明 subRL为新增结点左右双旋后 parent、subR、subRL 的平衡因子分别更新为0、0、0 可以看到经过右左双旋后树的高度没有发生变化所以右左双旋后无需继续往上更新平衡因子。
代码实现
void rotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;rotateR(subR);rotateL(parent);if (_bf 0) {parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else 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{assert(false);}}
AVL树的删除
要进行结点的删除首先需要在树中找到对应key值的结点寻找待删除结点的方法和二叉搜索树相同
1.先找到待删除的结点。 2.若找到的待删除结点的左右子树均不为空则需要使用替换法进行删除。 替换法删除指的是让待删除结点左子树当中key值最大的结点或待删除结点右子树当中值最小的结点代替待删除结点被删除代码中以后者为例然后再将待删除结点的key值以及value值都改为代替其被删除的结点的值即可。 也就是说我们最终找到的实际被删除的结点的左右子树当中至少有一个为空树。
在找到实际需要被删除的结点后我们先不进行实际的删除而是先进行平衡因子的更新不然后续更新平衡因子时特别麻烦已经尝试过而更新平衡因子时的规则与插入结点时的规则是相反的更新规则如下
1.删除的结点在parent的右边parent的平衡因子− − 。 2.删除的结点在parent的左边parent的平衡因子 。 并且每更新完一个结点的平衡因子后都需要进行以下判断 1.如果parent的平衡因子等于-1或者1表明无需继续往上更新平衡因子了。 2.如果parent的平衡因子等于0表明还需要继续往上更新平衡因子。 3.如果parent的平衡因子等于-2或者2表明此时以parent结点为根结点的子树已经不平衡了需要进行旋转处理。 在旋转处理时分为以下6种情况 1.当parent的平衡因子为-2parent的左孩子的平衡因子为-1时进行右单旋。 2.当parent的平衡因子为-2parent的左孩子的平衡因子为1时进行左右双旋。 3.当parent的平衡因子为-2parent的左孩子的平衡因子为0时也进行右单旋但此时平衡因子调整与之前有所不同具体看代码。 4.当parent的平衡因子为2parent的右孩子的平衡因子为-1时进行右左双旋。 5.当parent的平衡因子为2parent的右孩子的平衡因子为1时进行左单旋。6.当parent的平衡因子为2parent的右孩子的平衡因子为0时也进行左单旋但此时平衡因子调整与之前有所不同具体看代码。
代码实现
bool Erase(const K key){//用于遍历二叉树Node* cur parent;Node* parent nullptr;//用于标记实际删除的节点和父节点Node* deletePos nullptr;Node* deleteparentPos nullptr;//确定删除节点while (cur) {if (key cur-_kv.first) {parent cur;cur cur-_left;}else if (key cur-_kv.first) {parent cur;cur cur-_right;}else//遇到了待删除的节点{if (cur-_left nullptr)//如果待删除节点的左子树为空{if (cur _root)//如果待删除节点是根节点{_root cur-_right;if (_root) {_root-_parent nullptr;}delete cur;return true;}else{deleteparentPos parent;deletePos cur;break;//有祖先节点说明要更新平衡因子}}else if (cur-_right nullptr)//如果待删除节点的右子树为空{if (cur _root)//如果待删除节点是根节点{_root cur-_left;if (_root) {_root-_parent nullptr;}delete cur;return true;}else{deleteparentPos parent;deletePos cur;break;//有祖先节点说明要更新平衡因子}}else//如果待删除节点的左右子树都不为空替换法删除{//替换法删除//寻找待删除节点右子树中key值最小的节点作为实际删除节点转化为左子树为空的局面Node* minparent cur;Node* minright cur-_right;while (minright-_left){minparent minright;minright minright-_left;}//将待删除节点的属性更新为右子树中key值最小节点的属性cur-_kv.first minright-_kv.first;cur-_kv.second minright-_kv.second;//标记右子树中key值最小的节点为删除节点deleteparentPos minparent;deletePos minright;break;}}}//如果deletePos没有更新,说明没有找到根节点if (deletePos nullptr){return false;}//记录待删除节点及其父节点(实际删除时要用)cur-_kv.first minright-_kv.first;Node* del deletePos;Node* delparent deleteparentPos;//更新平衡因子while (deletePos ! _root)//可能要一直更新到根节点{//判断删除的是父亲的哪一边然后更新平衡因子if (deletePos deleteparentPos-_left) {deleteparentPos-_bf;}else{deleteparentPos-_bf--;}//判断是否需要往上继续更新if (abs(deleteparentPos-_bf) 1) {break;}else if (deleteparentPos-_bf 0) //其他两种情况树的高度都会变化所以要继续往上跟新平衡因子{deletePos deleteparentPos;deleteparentPos deleteparentPos-_parent;}else if (abs(deleteparentPos-_bf) 2)//需要进行旋转处理{//判断旋转情况if (deleteparentPos-_bf -2){if (deleteparentPos-_left-_bf -1) {Node* tmp deleteparentPos-_left;//记录右转后新的根节点rotateR(deleteparentPos);deleteparentPos tmp;//旋转后根节点更新}else if(deleteparentPos-_left-_bf 1) {Node* tmp deleteparentPos-_left-_right;//记录右转后新的根节点rotateLR(deleteparentPos);deleteparentPos tmp;//旋转后根节点更新}else//deleteparentPos-_left-_bf 0{Node* tmp deleteparentPos-_left;rotateR(deleteparentPos);deleteparentPos tmp;deleteparentPos-_bf 1;deleteparentPos-_right-_bf -1;break;}}else//deleteparentPos-_bf 2{if (deleteparentPos-_right-_bf 1){Node* tmp deleteparentPos-_right-_left;rotateRL(deleteparentPos);deleteparentPos tmp;}else if (deleteparentPos-_right-_bf -1){Node* tmp deleteparentPos-_right;rotateL(deleteparentPos);deleteparentPos tmp;}else{Node* tmp deleteparentPos-_right;rotateL(deleteparentPos);deleteparentPos tmp;deleteparentPos-_bf -1;deleteparentPos-_left-_bf 1;break;}}}else {assert(false);}//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子deletePos deleteparentPos;deleteparentPos deleteparentPos-_parent;}if (del-_left nullptr) {if (del delparent-_left) {delparent-_left del-_right;if (del-_right) {del-_right-_parent delparent;}}else {delparent-_right del-_right;if (del-_right) {del-_right-_parent delparent;}}}else{if (del delparent-_left) {delparent-_left del-_left;if (del-_left) {del-_left-_parent delparent;}}else {delparent-_right del-_left;if (del-_left) {del-_left-_parent delparent;}}}delete del;return true;}
AVL树的查找
Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key) // key值大于该结点的值{cur cur-_left; // 在该结点的右子树当中查找}else if (cur-_kv.first key) // key值小于该结点的值{cur cur-_right; // 在该结点的左子树当中查找}else // 当前节点的值等于key值{return cur; //返回该结点}}return nullptr; //查找失败}
AVL树的高度
采用了分治的思想
private:
void _Height(Node* root){if (!root) {return 0;}int left _Height(root-_left);int right _Height(root-_right);return left right ? left 1 : right 1;}
public
void Height(){_Height(_root);}
AVL树的判定 bool _IsBalancedTree(Node* root) {if (!root) {return true;}int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;if (abs(diff) 2) {cout wrong endl;return false;}else if (diff ! root-_bf) {return false;}return _IsBalancedTree(root-_left) _IsBalancedTree(root-_right);}AVL树的遍历
void _Inorder(Node* root){if (!root) {return;}_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}
