聊城专业网站制作公司,广东省广州市白云区,制作小诗集,成都有没有做网站建设的二叉搜索树的查找和删除虽然最优情况下能够做到 O(logN) 的级别#xff0c;但是在一些特殊情况下#xff0c;它的查找速度只能到达 O(N)级别#xff0c;比如数据按顺序插入#xff0c;那么就一定是一棵单边树。 为了针对这种情况#xff0c;俄罗斯的两位数学家#xff1a… 二叉搜索树的查找和删除虽然最优情况下能够做到 O(logN) 的级别但是在一些特殊情况下它的查找速度只能到达 O(N)级别比如数据按顺序插入那么就一定是一棵单边树。 为了针对这种情况俄罗斯的两位数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉树中插入数据需要保证树的左右高度之差的绝对值不超过1通过这种方法能够有效的减少平均搜索长度这种树就是AVL树。
AVL树的概念
它的左右子树都是AVL树。左右子树的高度差的绝对值不超过1.
若一个二叉搜索树能够保持高度平衡他就是AVL树有n个节点它的高度为 O(logN)搜索时间为 O(logN)。
了解了AVL树的概念就来看看它的实现代码吧。
AVL树节点的实现
templateclass K,class V
class AVLNode {
public:pairK, V _kv;AVLNodeK, V* _left;AVLNodeK, V* _right;AVLNodeK, V* _parent;int _bf;AVLNode(pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};
AVL树相比于普通的二叉搜索树还多出了一个指向父节点的指针以及平衡因子 _bf 。 平衡因子:本博客中的平衡因子的值等于右子树的高度-左子树的高度。 刚创建的节点的平衡因子为0. AVL树节点的插入
bool Insert(const pairK, V kv)
{if (_root nullptr){pNode cur new Node(kv);_root cur;return true;}pNode cur _root;pNode parent nullptr;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应该到空了parent指向下一个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 (cur parent-_left){parent-_bf--;}else if (cur parent-_right){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){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(-1);}}
}AVL树的插入刚开始和二叉搜索树类似首先找到插入节点的位置然后再插入到该节点的位置。
不过不同的是根据cur插入位置的不同需要更新cur的父节点的平衡因子。
如果插入在左子树位置父节点的平衡因子就减减否则就加加。
而且根据父节点平衡因子的变化有可能需要一直更新父节点的平衡因子直到根节点。
比如这样的 假设我们插入新节点到e节点下(左右子树中任意一个) 我们发现其父节点的平衡因子都需要更新一直到根节点。
而这是有规律的。
当父节点的平衡因子变为 1/-1说明子树的高度变更需要向上更新平衡因子当父节点的平衡因子变为0则说明子树的高度不变只需要更新父节点的平衡因子当父节点的平衡因子变为2/-2则说明子树的高度过高需要父节点自旋。
节点的自旋
节点的共四种情况右单旋左单旋左右双旋右左双旋。
右单旋 当节点插入在较高左子树的左侧时就会出现左子树高度-右子树高度 -2导致左右不平衡此时需要使平衡因子-2的节点进行左旋变成下面的样子。 将a节点连接到b节点的右指针a肯定大于b节点将b节点的右子树连接到a节点的左指针b的右子树肯定都小于a再更新平衡因子
我们发现通过右单旋a节点和b节点的平衡因子都变为0了。
通过这个思路可以得到代码。
void RotateR(pNode parent)
{pNode pleft parent-_left;pNode pleft_R pleft-_right;pNode P_parent parent-_parent;//将左子树的右指针指向parentpleft-_right parent;//将parnet 的左指针指向左子树的右节点parent-_left pleft_R;if (pleft_R){//若左子树的右节点不为空就将它的父节点设置为parentpleft_R-_parent parent;}//将左子树设置为parent的父节点parent-_parent pleft;pleft-_parent P_parent;if (P_parent nullptr){_root pleft;pleft-_parent nullptr;}else{if (parent P_parent-_left){P_parent-_left pleft;}else if (parent P_parent-_right){P_parent-_right pleft;}}parent-_bf pleft-_bf 0;
}
左单旋
当节点插入在较高右子树的右节点就需要进行左单旋。 左单旋的过程和右单旋一样只是方向是不同的。
将a节点连接到b节点的左指针a肯定小于b节点将b节点的左子树连接到a节点的右指针b的左子树肯定都大于a再更新平衡因子 void RotateL(pNode parent){pNode pright parent-_right;pNode pright_L pright-_left;pNode P_parent parent-_parent;//将右子树的左指针指向parentpright-_left parent;//将parnet 的右指针指向左子树的右节点parent-_right pright_L;if (pright_L){//若左子树的右节点不为空就将它的父节点设置为parentpright_L-_parent parent;}//将左子树设置为parent的父节点parent-_parent pright;pright-_parent P_parent;if (P_parent nullptr){_root pright;pright-_parent nullptr;}else{if (parent P_parent-_left){P_parent-_left pright;}else if (parent P_parent-_right){P_parent-_right pright;}}parent-_bf pright-_bf 0;}
左右双旋
这种情况可以看做右单旋的另一种节点插入情况。
右单旋是插入较高左子树的左侧而当新节点插入较高左子树的右侧时就会出现新的情况。 此处新节点可以插在c节点的左子树或者右子树都一样只是最后平衡因子更新不同。 这种情况下无论是单纯的左单旋还是右单旋都没有用需要两个一起来。
先以b节点作为父节点来进行一次左单旋。然后再以a节点作为父节点来进行一次右单旋。最后查看新节点是在c节点的左子树还是右子树来进行平衡节点的更新。 通过左右双旋能够使AVL树平衡不过根据新节点的位置a和b的平衡因子会不同。
比如新节点在c节点的左子树上那么b的平衡因子为0a的平衡因子为1。
新节点在c节点的右子树上b的平衡因子为-1a的平衡因子为0。
void RotateLR(pNode parent)
{pNode subL parent-_left;pNode subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 1)//新增节点在右边{subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else if (bf -1)//新增节点在左边{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 0)//本身是新增节点{subL-_bf 0;parent-_bf 0;subLR-_bf 0;}else{assert(false);}
}
右左双旋
右左双旋就是左旋的另一种情况新节点在较高右子树的左节点情况和左右双旋一样需要两个单旋合作来实现平衡。
void RotateRL(pNode parent)
{pNode subR parent-_right;pNode subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 1)//新增节点在右边{subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1)//新增节点在左边{subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 0)//本身是新增节点{subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{assert(false);}
}
通过这四种方式能够保证AVL树的平衡。
AVL树的验证
验证AVL树是否是AVL树有两个条件
左右子树的高度差是否等于平衡因子节点的左右子树都是AVL树
因此我们通过递归来检查AVL树是否是AVL树。 bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(pNode root){if (root nullptr){return true;}int left Height(root-_left);int right Height(root-_right);int dff right - left;if (dff ! root-_bf){cout 平衡因子异常 endl;return false;}return abs(dff) ! 2 _IsBalance(root-_left) _IsBalance(root-_right);}int Height(pNode root){if (root nullptr){return 0;}int left Height(root-_left);int right Height(root-_right);return left right ? left 1 : right 1;}
通过递归遍历检查可以检查是否是AVL树。
AVL树的删除
AVL树的删除大致和二叉搜索树类似不过不同的是AVL树需要更新平衡因子当删除节点后有节点的平衡因子变为-2/2时就需要进行自旋。
平衡因子的更新
删除节点时的平衡因子的更新和插入节点时平衡因子的更新正好相反。
当左节点被删除时父节点的平衡因子需要当右节点被删除时父节点的平衡因子需要--当父节点的平衡因子变为1/-1时说明原本的平衡因子为0删除后节点的高度不变不用向上更新节点当父节点的平衡因子变为0时说明原本的平衡因子为1/-1删除后节点的高度变化需要向上更新节点当父节点的平衡因子变为2/-2时说明高度过高需要自旋
父节点的平衡因子为-2时
这种情况下有三种情况父节点的左子树的平衡因子为 0/1/-1。
左子树平衡因子为0时 如图删除c节点后a节点的平衡因子变为-2而b的平衡因子为0。
这种情况我们可以直接看做是插入的右单旋或者左右单旋的情况此处我们可以直接用右单旋。
左子树平衡因子为1时 这种情况下就是左右双旋的情况需要先对b节点进行左单旋再对a节点进行右单旋。
左子树的平衡因子为-1时 这种情况下就是单纯的右单旋了。
父节点的平衡因子为2时
右子树的平衡因子为0时 这种情况下可以单纯采用左单旋
右子树的平衡因子为-1时 这种情况下需要采用右左单旋 平衡因子为1时 这种情况下就可以直接采用左单旋。
删除的更新代码
void DelUpdate(pNode cur, pNode parent)
{while (parent){//删除左节点就需要if (cur parent-_left){parent-_bf;}else if (cur parent-_right){parent-_bf--;}if (parent-_bf 0){cur parent;parent parent-_parent;}else if (parent-_bf 1 || parent-_bf -1){break;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf 2){if (parent-_right-_bf 0){pNode p_right parent-_right;RotateL(parent);parent-_bf 1;p_right-_bf -1;break;}else if (parent-_right-_bf 1){RotateL(parent);}else if (parent-_right-_bf -1){RotateRL(parent);}cur parent;parent parent-_parent;}else if (parent-_bf -2){if (parent-_left-_bf 0){pNode p_left parent-_left;RotateR(parent);parent-_bf -1;p_left-_bf 1;break;}else if(parent-_bf 1){RotateLR(parent);}else if (parent-_left-_bf -1){RotateL(parent);}cur parent;parent parent-_parent;}}}
}
删除时的更新并未直接删除节点删除节点的操作应该在平衡因子更新后再进行操作。
节点的删除
节点的删除有三种情况左右为空有一边不为空左右都不为空。
左右为空
当节点的左右都为空时就在更新平衡因子后直接删除该节点然后根据节点的位置来使父节点的指针指向空。 如图删除的d节点是b节点的左节点那么需要使b节点的左节点指向空。
右一边不为空 这个时候还需要把d节点连接到a节点的左指针把d节点的父指针指向a节点后再删除b节点。
左一边不为空 这个时候需要把d节点连接到a节点的左指针上再更新d节点的父指针。
左右不为空
这个情况下我们需要找到cur被删除节点的右子树中的最小节点也就是右子树的最左节点然后交换最左节点和cur的值再删除最左节点即可。 注意minright是最左节点但不一定没有右子树因此需要检查是否有右子树将右子树连接到minright的父节点的左指针上。 代码实现
bool Erase(const pairK, V kv)
{pNode cur Find(kv);pNode parent cur-_parent;pNode delnode cur;if (cur nullptr){return false;}//若左右都是空树else if (cur-_left nullptr cur-_right nullptr){//若是根还需要将_root 置空if (_root cur){_root nullptr;delete cur;}//若不是根还需要向上调整else{//更新后cur和parent都会改变因此需要重新赋值DelUpdate(cur, parent);parent delnode-_parent;if (delnode parent-_left){parent-_left nullptr;}else{parent-_right nullptr;}delete delnode;}}else if (cur-_left nullptr cur-_right ! nullptr){//左为空右不为空if (cur _root){//若是根节点_root cur-_right;_root-_parent nullptr;delete cur;}else{pNode delnode cur;//更新平衡因子DelUpdate(cur, parent);parent delnode-_parent;pNode cur_R delnode-_right;cur_R-_parent parent;if (delnode parent-_left){parent-_left cur_R;}else if (delnode parent-_right){parent-_right cur_R;}delete delnode;}}else if (cur-_left ! nullptr cur-_right nullptr){if (cur _root){//若是根节点_root cur-_left;_root-_parent nullptr;delete cur;}else{pNode delnode cur;//更新平衡因子DelUpdate(cur, parent);parent delnode-_parent;pNode cur_L delnode-_left;cur_L-_parent parent;if (delnode parent-_left){parent-_left cur_L;}else if (delnode parent-_right){parent-_right cur_L;}delete delnode;}}//左右都不空else{pNode minRight cur-_right;pNode minRight_P cur;//找到右子树的最左节点while (minRight-_left){minRight_P minRight;minRight minRight-_left;}//交换它们的值cur-_kv.first minRight-_kv.first;cur-_kv.second minRight-_kv.second;//记录下最左节点的右子树,由于更新平衡因子会改变minRight的指向因此记录下minRightpNode minRight_R minRight-_right;pNode tmp minRight;//更新平衡因子DelUpdate(minRight, minRight_P);minRight tmp;minRight_P minRight-_parent;if (minRight minRight_P-_left){if (minRight_R ! nullptr){minRight_R-_parent minRight_P;}minRight_P-_left minRight_R;}else if (minRight minRight_P-_right){if (minRight_R ! nullptr){minRight_R-_parent minRight_P;}minRight_P-_right minRight_R;}delete minRight;}return true;
} 总结 这就是AVL树的总结和实现了作为map和set的底层结构AVL树的结构十分重要需要各位同学好好学习。
