【数据结构】平衡二叉树的调整(RR LL LR RL)旋转详解讲解 |
您所在的位置:网站首页 › 二叉树数据结构写法 › 【数据结构】平衡二叉树的调整(RR LL LR RL)旋转详解讲解 |
平衡二叉树的调整
旋转的命名规则RR旋转(右单旋)LL旋转(左单旋)LR旋转(左右旋转)RL旋转(右左旋转)
旋转的命名规则
其中Mar节点的平衡因子大于了1,所以称Mar节点为“发现者”,因为插入了Nov节点导致平衡二叉树被破坏,所以Nov节点称为“麻烦节点”。 所谓旋转,如RR旋转之所以叫RR旋转是因为:不平衡的“发现者”是Mar,“麻烦结点”Nov 在发现者(Mar)右子树的右边。 即: 旋转的命名(LL、RR、LR、RL)也都是根据被破坏节点Mar(平衡因子大于一)与麻烦节点(造成这种情况的结点)的相对位置命名。 在发现结点的左子树还是右子树(L或R)的左节点还是右节点(L或R)上插入新节点。 而旋转,如上图,对插入Nov后的不平衡树进行右旋转,就是对发现者Mar与破坏者的父节点May进行位置上的变化 即: 进行旋转的是发现节点(被破坏节点)与麻烦节点的父节点(平衡因子不等于0) RR旋转(右单旋)
B节点的右子树BR还是B的右子树,B节点的左子树BL成为A节点的右子树,和A的节点AL成为节点A的左右子树。 LL旋转(左单旋)
B节点的左子树子树BL还是B的左子树,B节点的右子树BR成为A节点的左子树,和AR成为节点A的左右子树。 LR旋转(左右旋转)
发现节点A与C进行左旋转(LL),导致C代替A的位置,A成为C的右节点,C的右子树成为A的左子树 RL旋转(右左旋转)
发现节点A与C进行右旋转(RR),导致C代替A的位置,A成为C的左节点,C的左子树成为A的右子树 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |