【数据结构】平衡二叉树的调整(RR LL LR RL)旋转详解讲解

您所在的位置:网站首页 二叉树数据结构写法 【数据结构】平衡二叉树的调整(RR LL LR RL)旋转详解讲解

【数据结构】平衡二叉树的调整(RR LL LR RL)旋转详解讲解

2024-06-14 04:28| 来源: 网络整理| 查看: 265

平衡二叉树的调整 旋转的命名规则RR旋转(右单旋)LL旋转(左单旋)LR旋转(左右旋转)RL旋转(右左旋转)

旋转的命名规则

在这里插入图片描述   如图初始插入节点Nov后,Mar节点的平衡因子(左右两个子树的高度差的绝对值)大于1,不满足平衡二叉树性值,所以要对其进行调整。

  其中Mar节点的平衡因子大于了1,所以称Mar节点为“发现者”,因为插入了Nov节点导致平衡二叉树被破坏,所以Nov节点称为“麻烦节点”。

  所谓旋转,如RR旋转之所以叫RR旋转是因为:不平衡的“发现者”是Mar,“麻烦结点”Nov 在发现者(Mar)右子树的右边。

即:   旋转的命名(LL、RR、LR、RL)也都是根据被破坏节点Mar(平衡因子大于一)与麻烦节点(造成这种情况的结点)的相对位置命名。

  在发现结点的左子树还是右子树(L或R)的左节点还是右节点(L或R)上插入新节点。

  而旋转,如上图,对插入Nov后的不平衡树进行右旋转,就是对发现者Mar与破坏者的父节点May进行位置上的变化

即:   进行旋转的是发现节点(被破坏节点)与麻烦节点的父节点(平衡因子不等于0)

RR旋转(右单旋)

在这里插入图片描述 RR旋转,先看命名规则:   不平衡的“发现者”是Mar,“麻烦结点”Nov 在发现者(Mar)右子树的右边,因而叫 RR 插入,需要RR 旋转(右单旋) 在这里插入图片描述 旋转过程:   在RR旋转时B节点与A节点位置互换,节点B成为树的根节点。 关键节点A将向左移动并成为B的左子节点。

  B节点的右子树BR还是B的右子树,B节点的左子树BL成为A节点的右子树,和A的节点AL成为节点A的左右子树。

LL旋转(左单旋)

在这里插入图片描述 LL旋转,先看命名规则:   “发现者”是Mar,“麻烦结点”Apr在发现者左子树的左边,因面叫LL插入,需要LL旋转(左单旋) 在这里插入图片描述 旋转过程:   在LL旋转时B节点与A节点位置互换,节点B成为树的根节点。 关键节点A将向右移动并成为B的右子节点。

  B节点的左子树子树BL还是B的左子树,B节点的右子树BR成为A节点的左子树,和AR成为节点A的左右子树。

LR旋转(左右旋转)

在这里插入图片描述 LR旋转,先看命名规则:   “发现者”是May,麻烦结点”Jan在左子树的右边,因而叫LR 插入,需要LR 旋转 在这里插入图片描述 旋转过程:   麻烦节点的父节点即最下层平衡因子非0节点C,与其父节点B(发现节点的左节点)进行右旋转(RR),导致C代替B的位置,B成为C的左节点,C的左子树CL成为B的右子树。

  发现节点A与C进行左旋转(LL),导致C代替A的位置,A成为C的右节点,C的右子树成为A的左子树

RL旋转(右左旋转)

在这里插入图片描述 RL旋转,先看命名规则:   “发现者”是Aug,麻烦结点”feb在右子树的左边,因而叫RL 插入,需要RL 旋转

在这里插入图片描述 旋转过程:   麻烦节点的父节点即最下层平衡因子非0节点C,与其父节点B(发现节点的右节点)进行左旋转(LL),导致C代替B的位置B成为C的右节点,C的右子树CR成为B的左子树

  发现节点A与C进行右旋转(RR),导致C代替A的位置,A成为C的左节点,C的左子树成为A的右子树



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3