转

平衡二叉树-旋转的四种情况 05

4199人阅读 2022/6/15 17:45 总访问：1445445 评论：0 收藏：0 手机

分类: Java集合

平衡二叉树-旋转的四种情况

左左、左右、右右、右左

1、左左

当根节点左子树的左子树有节点插入，导致二叉树不平衡

如将图一添加节点1变成图二的样子

1.2、我们可以根据右旋定义来使图二变成平衡二叉树
右旋∶将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点
2、左右

当根节点左子树的右子树有节点插入，导致二叉树不平衡
如将图一添加节点6变成图二的样子

变成图二的样子后，此时光一个右旋是不够的，要先左旋再右旋
2.1先将图三紫色部分左旋变成图四的样子
左旋∶就是将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点

2.2、再将图四整体右旋得到图五
右旋∶将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点
3、右右