linux网站服务器配置,优化搜狐的培训,wordpress 返回首页,播州区住房和城乡建设局网站目录 一. AVL的概念
二 AVL树的插入
2.1先按二叉搜索树的规则插入
2.2 AVL的重点#xff1a;平衡因子更新
3.1 更新后parent的平衡因子等于0。 3.2 更新后parent的平衡因子等于1 或 -1#xff0c;需要继续往上更新。 3.3 更新后parent的平衡因子等于2 或 -2#xff0c;需…目录 一. AVL的概念
二 AVL树的插入
2.1先按二叉搜索树的规则插入
2.2 AVL的重点平衡因子更新
3.1 更新后parent的平衡因子等于0。 3.2 更新后parent的平衡因子等于1 或 -1需要继续往上更新。 3.3 更新后parent的平衡因子等于2 或 -2需要使用旋转处理。
三.旋转 和 平衡因子等于2 或 -2 的处理
1.右单旋(把左孩子变成爸爸)
2.左单旋(把右孩子变成爸爸)
3.左右双旋把LR_Child 变为爸爸
4.左右双旋把RL_Child 变为爸爸
总代码 一. AVL的概念
1.AVL树是最先发明的自平衡二叉查找树AVL是一颗空树或者具备下列性质的二叉搜索树:它的 左右子树都是AV树且 左右子树的高度差的绝对值不超过1 。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡 2.AVL树实现这里我们引入一个平衡因子(balance factor)的概念每个结点都有一个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1 AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡 就像一个风向标一样。 二 AVL树的插入
AVL节点 的大概结构 AVL树 的大概结构 2.1先按二叉搜索树的规则插入
具体可以看这篇
二叉搜索树-CSDN博客
这里是二叉搜索树的简单的代码总结 2.2 AVL的重点平衡因子更新 因为左右子树的高度差的绝对值不超过1 。
这里我们可以规定
1. 平衡因子 右子树高度 - 左子树高度 。
2. 插入结点时会增加高度如果新增结点 在parent的右子树parent的平衡因子新增结点在parent的左子树parent平衡因子--parent的平衡因子初始化为 0.
3. parent的停止更新条件分为3种 3.1 更新后parent的平衡因子等于0。 3.2 更新后parent的平衡因子等于1 或 -1需要继续往上更新。 上面的总代码 3.3 更新后parent的平衡因子等于2 或 -2需要使用旋转处理。 下面为具体的分析 三.旋转 和 平衡因子等于2 或 -2 的处理
旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。
这里我们规定
1. 在parent的左边 插入孩子parent的平衡因子 - 1
2 .在parent的右边 插入孩子parent的平衡因子 1 1.右单旋(把左孩子变成爸爸)
需要 单纯的左边高 才可以使用
比如 if(parent-_bf -2 SubR-_bf -1)
如图 分析
因为 左右子树的高度差的绝对值不超过1
我们需要把 a 往上提把parent往下压 让SubL变成爸爸 才可以解决。
总的来说就是左边高就把左边提上来把右边压下去。
在这种情况下 他们的平衡因子就会为0.
代码为 RotateR 2.左单旋(把右孩子变成爸爸)
需要 单纯的右边高 才可以使用
比如 if(parent-_bf 2 SubR-_bf 1)
如图 分析
因为 左右子树的高度差的绝对值不超过1
我们需要把 a 往上提把parent往下压 让SubR变成爸爸 才可以解决。
总的来说就是右边高就把右边提上来把左边压下去。
在这种情况下 他们的平衡因子就会为0.
代码为 RotateL 3.左右双旋把LR_Child 变为爸爸
需要 左边的右边高 才可以使用
如图所示 当没插入节点时 在LR_Child 的左边插入节点 具体过程
1. 让节点5 左旋转 2.让节点8 右旋转 平衡因子
在LR_Child 为空时
平衡因子 都为0. 在LR_Child 的左边插入节点
LR_Child 平衡因子 为 0
L_Child 平衡因子 为 0
parent 平衡因子为 1 在LR_Child 的右边插入节点
LR_Child 平衡因子 为 0
L_Child 平衡因子 为 -1
parent 平衡因子为 0 代码 4.左右双旋把RL_Child 变为爸爸
太长了随便写点了脑子坏了 在LR_Child 为空时
平衡因子 都为0. 在LR_Child 的右边插入节点
RL_Child 平衡因子 为 0
R_Child 平衡因子 为 0
parent 平衡因子为 -1 在RL_Child 的左边插入节点
RL_Child 平衡因子 为 0
R_Child 平衡因子 为 1
parent 平衡因子为 0 代码 总代码
#pragma once
#includeiostream
#includeassert.h
using namespace std;
templateclass Tstruct AVLTreeNode
{AVLTreeNode(const T data T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _pLeft;AVLTreeNodeT* _pRight;AVLTreeNodeT* _pParent;T _data;int _bf; // 节点的平衡因子
};// AVL: 二叉搜索树 平衡因子的限制
templateclass T
class AVLTree
{typedef AVLTreeNodeT Node;
public:AVLTree(): _pRoot(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T data){//如果树为空就建立一个根节点if (_pRoot nullptr){_pRoot new Node(data);}//树不为空else{Node* parent nullptr;Node* tmp _pRoot;//用cur找位置 while (tmp){//插入值比当前结点小往左走if (tmp-_data data){parent tmp;tmp tmp-_pRight;}//插入值比当前结点大往右走else if (tmp-_data data){parent tmp;tmp tmp-_pLeft;}else{assert(false);}}//在parent的左边或者右边插入插入Node* cur new Node(data);if (parent-_data data){parent-_pRight cur;cur-_pParent parent;}else if (parent-_data data){parent-_pLeft cur;cur-_pParent parent;}//最困难的平衡因子部分while (parent){//cur插入在右边平衡因子if (cur parent-_pRight)parent-_bf;//反之亦然elseparent-_bf--;//平衡因子为0 结束if (parent-_bf 0)break;//平衡因子为1 或 -1往上更新else if(parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_pParent;}else if(parent-_bf -2 || parent-_bf 2){//...// //单纯左边高if (parent-_bf -2 cur-_bf -1){RotateR(parent);parent-_bf 0;cur-_bf 0;}//单纯右边高else if (parent-_bf 2 cur-_bf 1){RotateL(parent);parent-_bf 0;cur-_bf 0;}//左边的右边高else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}//右边的左边高else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}}return true;}// AVL树的验证bool IsAVLTree(){return _Height(_pRoot);}void InOrder(){return _InOrder(_pRoot);}size_t Height(){return _Height(_pRoot);}
private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* pRoot){if (pRoot nullptr)return true;int left _Height(pRoot-_pLeft);int right _Height(pRoot-_pRight);int differ right - left;if (differ 2 || differ -2)return false;if (differ ! pRoot-_bf)return false;return _IsAVLTree(pRoot-_pLeft) _IsAVLTree(pRoot-_pRight);}void _InOrder(Node* cur){if (cur nullptr)return;_InOrder(cur-_pLeft);cout cur-_data ;_InOrder(cur-_pRight);}size_t _Height(Node* pRoot){if (pRoot nullptr)return 0;size_t left _Height(pRoot-_pLeft);size_t right _Height(pRoot-_pRight);return right left ? right 1 : left 1;}// 右单旋void RotateR(Node* pParent){Node* L_Child pParent-_pLeft;Node* LR_Child L_Child-_pRight;//左边孩子的 右边的孩子 和parent相互连接if (LR_Child)LR_Child-_pParent pParent;pParent-_pLeft LR_Child;//左孩子变在上面 右边连接parent ,grandfather 相互连接Node* grandfather pParent-_pParent;pParent-_pParent L_Child;L_Child-_pRight pParent;L_Child-_pParent grandfather;if (grandfather nullptr){_pRoot L_Child;}else{if (grandfather-_pLeft pParent)grandfather-_pLeft L_Child;elsegrandfather-_pRight L_Child;}}// 左单旋void RotateL(Node* pParent){Node* R_Child pParent-_pRight;Node* RL_Child R_Child-_pLeft;//if(RL_Child)RL_Child-_pParent pParent;pParent-_pRight RL_Child;Node* grandfather pParent-_pParent;pParent-_pParent R_Child;R_Child-_pLeft pParent;R_Child-_pParent grandfather;if (grandfather nullptr){_pRoot R_Child;}else{if (grandfather-_pLeft pParent)grandfather-_pLeft R_Child;elsegrandfather-_pRight R_Child;}}// 右左双旋void RotateRL(Node* pParent){Node* RChild pParent-_pRight;Node* RLChild RChild-_pLeft;//旋转完之后再用bf来判断平衡因子int bf RLChild-_bf;RotateR(RChild);RotateL(pParent);if (bf 0){pParent-_bf 0;RChild-_bf 0;RLChild-_bf 0;}else if (bf 1){RLChild-_bf 0;RChild-_bf 0;pParent-_bf -1;}else if (bf -1){RLChild-_bf 0;RChild-_bf 1;pParent-_bf 0;}elseassert(false);}// 左右双旋void RotateLR(Node* pParent){Node* LChild pParent-_pLeft;Node* LRChild LChild-_pRight;int bf LRChild-_bf;RotateL(LChild);RotateR(pParent);if (bf 0){LRChild-_bf 0;pParent-_bf 0;LChild-_bf 0;}else if (bf 1){LRChild-_bf 0;LChild-_bf -1;pParent-_bf 0;}else if (bf -1){LRChild-_bf 0;LChild-_bf 0;pParent-_bf 1;}elseassert(false);}private:Node* _pRoot;};
