平衡二叉树的旋转

ゝ一纸荒年。 2023-07-10 14:16 91阅读 0赞

## 平衡二叉树的旋转 ##

在一棵平衡二叉树增加或删除结点的时候，可能会破坏原本的平衡状态，在此时需要对被破坏平衡的结点进行处理，使其恢复到平衡状态，即旋转。  
有四种不同的不平衡状态：LL型、RR型、LR型、RL型

##### LL型 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]  
此时的树是左孩子深度大于右孩子，即左子树较深，所以需进行右旋  
根据二叉搜索树的性质（左孩子<根结点<右孩子）：  
若将a2上升到根结点，则a2的子树要归并到右子树，  
而a2的右子树又小于根结点a1，则需将a2右子树归并为a1的左子树  
然后将a1作为a2右子树

旋转步骤：  
①将a2的右孩子存储为a1的左孩子  
②将a1作为a2的右孩子，把a2作为根

/**
      * LL型进行右旋
      * @param rootNode 破坏结点
      * @return 平衡后的破坏结点
      */
     public static TreeNode LLSpin(TreeNode rootNode) {
      	//先对破坏结点左孩子进行存储
      	TreeNode midNode = rootNode.getLeChild();
      	//将存储结点的右结点赋给破坏结点的左结点
     	rootNode.setLeChild(midNode.getRiChild());
      	//将破坏结点置于存储结点的右结点处
      	midNode.setRiChild(rootNode);
      	//返回新结点，用以将破坏结点父结点处的引用做修改
      	return midNode;
     }

##### RR型 #####

RR型的旋转步骤同于LL型，不过是进行左旋

/**
      *  RR型进行左旋
      * @param rootNode 破坏结点
      * @return 平衡后的破坏结点
      */
     public static TreeNode RRSpin(TreeNode rootNode) {
      	//先对破坏结点右孩子进行存储
      	TreeNode midNode = rootNode.getRiChild();
      	//将存储结点的左结点赋给破坏结点的右结点
      	rootNode.setRiChild(midNode.getLeChild());
      	//将破坏结点置于存储结点的左结点处
      	midNode.setLeChild(rootNode);
      	//将破坏结点父结点处的引用做修改
      	return midNode;
     }

##### LR型 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]  
LR型的树无法在进行一次旋转后就达到平衡。  
此时则需先对不平衡结点的左孩子进行一次左旋，  
然后对根结点进行一次右旋

/**
      * LR型先左旋后右旋
      * @param rootNode
      * @return 平衡后的破坏结点
      */
     public static TreeNode LRSpin(TreeNode rootNode) {
      	//先对破坏结点的左孩子进行左旋
      	rootNode.setLeChild(RRSpin(rootNode.getLeChild()));
      
      	//再对破坏结点进行右旋
      	return LLSpin(rootNode);
     }

##### RL型 #####

RL型同LR型，方向相反

/**
      * RL型先右旋后左旋
      * @param rootNode
      * @return 平衡后的破坏结点
      */
     public static TreeNode RLSpin(TreeNode rootNode) {
      //先对破坏结点的右孩子进行右旋
      rootNode.setRiChild(LLSpin(rootNode.getRiChild()));;
      
      //再对破坏结点进行左旋
      return RRSpin(rootNode);
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303094825902.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200303094859202.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020030310514521.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200303112512955.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关平衡二叉树是什么？平衡二叉树旋转的4种情况

二叉查找树的作用是提高检索数据的性能，小的存左边，大的存右边，一样的不存。但出现瘸子现象，导致查询的性能与单链表一样，拉低查询速度。这时候需要用到平衡二叉树，在满足查找二

- 日理万妓/ 2024年02月21日 11:29/ 0 赞/ 39 阅读

相关 AVL 平衡二叉树旋转方法

1、预备知识定义树（tree）的一种自然的方式是递归的方式。一棵树使一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根（root）的节点 r 以及 0 个或多

╰+哭是因爲堅強的太久メ/ 2024年02月18日 21:47/ 0 赞/ 13 阅读

相关平衡二叉树四种旋转情况

说明平衡二叉树首先要满足二叉排序树，其次还要满足树中每个节点的平衡因子的绝对值不能超过1，节点的平衡因子 = 左子树高度-右子树高度。若插入后导致二叉排序树失去平衡，

迷南。/ 2023年10月11日 18:27/ 0 赞/ 37 阅读

相关二叉树、二叉搜索树，平衡二叉树（旋转）红黑树（红黑规则）

文章目录 3.数据结构 3.1二叉树【理解】 3.2 二叉查找树【理解】 3.3平衡二叉树【理解】 3.4 红黑树【理

待我称王封你为后i/ 2023年10月07日 19:49/ 0 赞/ 76 阅读

相关平衡二叉树的旋转

平衡二叉树的旋转在一棵平衡二叉树增加或删除结点的时候，可能会破坏原本的平衡状态，在此时需要对被破坏平衡的结点进行处理，使其恢复到平衡状态，即旋转。有四种不同的不平

ゝ一纸荒年。/ 2023年07月10日 14:16/ 0 赞/ 92 阅读

相关平衡二叉树旋转法则

新添加元素直接作为叶结点加到对应结点后面 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

素颜马尾好姑娘i/ 2022年02月01日 06:09/ 0 赞/ 232 阅读

相关平衡二叉树 (平衡查找树)

平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上

小咪咪/ 2021年10月29日 07:24/ 0 赞/ 477 阅读

相关平衡二叉树(AVL 树)双旋转算法

一点睛在某些情况下，进行一次单旋转就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如下面两组数列。 int\[\] a

女爷i/ 2021年07月24日 20:57/ 0 赞/ 416 阅读

相关平衡二叉树(AVL 树)右旋转算法

一二叉排序树转化为AVL树的算法——单旋转(右旋转) 1 要求有一个数列\{10,12,8,9,7,6\}，创建出对应的平衡二叉树。 2 思路分析原始

布满荆棘的人生/ 2021年07月24日 20:29/ 0 赞/ 354 阅读

相关平衡二叉树(AVL 树)左旋转算法

一平衡二叉树的引入 1 二叉排序树存在的问题有一个数列\{1,2,3,4,5,6\}，创建一颗二叉排序树(BST), 分析它存在的问题。 ![waterma

太过爱你忘了你带给我的痛/ 2021年07月24日 12:24/ 0 赞/ 374 阅读