分类:
Java集合
平衡二叉树-旋转的四种情况
左左、左右、右右、右左
1、左左
当根节点左子树的左子树有节点插入，导致二叉树不平衡
如将图一添加节点1变成图二的样子
1.2、我们可以根据右旋定义来使图二变成平衡二叉树
右旋∶将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点
2、左右
当根节点左子树的右子树有节点插入，导致二叉树不平衡
如将图一添加节点6变成图二的样子
变成图二的样子后，此时光一个右旋是不够的，要先左旋再右旋
2.1先将图三紫色部分左旋变成图四的样子
左旋∶就是将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
2.2、再将图四整体右旋得到图五
右旋∶将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点
3、右右
当根节点右子树的右子树有节点插入，导致二叉树不平衡
如将图一添加节点12变成图二的样子
3.1、将上面图二右旋得到平衡二叉树图三
4、右左
当根节点右子树的左子树有节点插入，导致二叉树不平衡
如将图一添加节点8变成图二的样子
变成图二的样子后，此时光一个右旋是不够的，要先右旋再左旋
4.1先将图三紫色部分右旋变成图四的样子
4.2再将图四整体左旋得到图五
评价
