搞懂平衡二叉树的左旋右旋双旋（Java实现）

article/2025/9/29 5:57:14

刚看到韩顺平老师的数据结构与算法对于平衡二叉树的讲解（最后会附上地址），有如下理解，希望能帮助大家！哪里需要改正的欢迎指正！

平衡二叉树：一种二叉排序树（BST Binary Sort Tree）的升级，传统的二叉排序树容易形成类似链表的结构，造成平均查询次数较高，所以引入平衡二叉树，使得左右子树的高度差不超过1；
在这里插入图片描述我们知道了平衡二叉树的原理之后，就要在添加结点后就要判断是否需要将此树转化成平衡二叉树！如下例：4，3，5，2，1，0
如图，当添加到1这个结点的时候，4的左子树高为2，4的右子树高为0。两者高度差为2，此时这棵树不是平衡二叉树，那么就需要将其转换成平衡二叉树（先按照这个例子来进行，下面会说明其他情况）：具体操作如下：
先将必要类和方法写出：

class Node{int value;Node left;Node right;public Node(int value) {super();this.value = value;}//添加结点public void add(Node node) {if(node==null) {System.out.println("此结点为空，不可添加");	return;}if(this.value>node.value) {if(this.left==null) {this.left=node;}else {this.left.add(node);}}else {if(this.right==null) {this.right=node;}else {this.right.add(node);}}}@Overridepublic String toString() {return "Node [value=" + value + "]";}//中序遍历public void infixOrder() {if(this.left!=null) {this.left.infixOrder();}System.out.println(this);if(this.right!=null) {this.right.infixOrder();}}
}

同时：我们还要写计算左子树高和右子树高的方法！这个方法可以帮助我们判断当添加数据之后是否需要进行转化。

	//计算左子树的高度public int leftHeigh() {if(left==null) {return 0;}return left.height();}//计算右子树的高度public int rightHeigh() {if(right==null) {return 0;}return right.height();}//计算结点的树高度public int height() {return Math.max(left==null ? 0 : left.height(), right==null?0:right.height())+1;}

当有了这些方法之后就可以进行转换了：举韩老师在课堂上的例子4，3，6，5，7，8 在这里插入图片描述
当我们添加完8后，发现不满足平衡二叉树的条件了，就需要对其进行操作使其转化成平衡二叉树，这里的操作叫做左旋（当然还有右旋，双旋，放到后面来讲那些例子）！
操作如下：将其分为两步，很简单就是赋值的两步操作；
第一步.创建新节点，
新结点的值=当前结点的值（也就是4）；
新结点的左节点=当前节点的左节点（3）
新结点的右节点=当前结点的右结点的左节点（5）
第二步.修改当前节点
当前结点的值=当前节点的右节点
当前节点的右子树=当前节点的右子树的右子树
当前节点的左子树=新结点

这里第一步的操作实质上可以理解成，将上面三个点记录下来，作为第二步当前结点的右节点在这里插入图片描述
第二步的操作为：将当前节点的值修改成6，并将当前节点的左右结点修改，如图，到此，转化过程就到此结束了，（这里的白色6因为没有被任何的GC roots指向，将会被回收）
左旋的代码

	public void leftRotate() {//创建新节点Node node=new Node(this.value);//对新结点进行操作node.left=this.left;node.right=this.right.left;//修改当前节点this.value=this.right.value;this.right=this.right.right;this.left=node;}

在add方法加上左旋转的代码

		if(this.rightHeigh()-this.leftHeigh()>1) {this.leftRotate();}

右旋

其实右旋和左旋的操作相似，举个例子10，12，8，9，7，6
在这里插入图片描述当添加6后，发现需要调整，调整的操作也为两步
第一步.创建新节点，
新结点的值=当前结点的值（也就是10）；
新结点的右节点=当前节点的右节点（12）
新结点的左节点=当前结点的左结点的右节点（9）
第二步.修改当前节点
当前结点的值=当前节点的左节点的值（8）
当前节点的左子树=当前节点的左子树的左子树
当前节点的右子树=新结点
在这里插入图片描述
右旋方法

	//右旋转public void rightRotate() {//创建新节点Node node = new Node(this.value);//操作新节点node.left=this.left.right;node.right=this.right;//修改当前节点this.value=this.right.value;this.left=this.left.left;this.right=node;}

在add方法添上如下代码

		if(this.leftHeigh()-this.rightHeigh()>1) {this.rightRotate();}

双旋

但是当我们遇到这样的情况该怎么办呢？
如：左子树高>右子树---->采用右旋（但是当前节点的左子树的左子树高>它的左子树的右子树）
举例：10，7，11，6，8，9
7的左子树高（1）<右子树高（2）
在这里插入图片描述
我们发现直接右旋无法将其转化成平衡二叉树！
解决办法：
当我们发现：7的左子树高（1）<右子树高（2），先对7进行左旋，将其转化成左子树高>右子树高的形式，操作步骤如下图，
先将左子树（7）进行左旋之后，我们就可以直接将整棵树进行右旋了！
小结一下：当发现整个树需要右旋的时候，我们要先判断对于它的左子树，是否存在它的左子树的左子树高<它的左子树的右子树高的情况，若存在，则需要先对左子树进行左旋！再对其进行右旋！

对于整棵树要先左旋的情况，我们要先判断对于它的右子树，是否存在它的左=右子树的左子树高>它的左=右子树的右子树高的情况，若存在，则需要先对左子树进行右旋！再对整棵树进行左旋！
对add进行调整修改

		//左子树高>右子树高===>右旋转if(this.leftHeigh()-this.rightHeigh()>1) {if(this.left!=null&&this.left.leftHeigh()<this.left.rightHeigh()) {this.left.leftRotate();}this.rightRotate();}//右子树高》左子树高---》左旋转if(this.rightHeigh()-this.leftHeigh()>1) {if(this.right!=null&&this.right.leftHeigh()>this.right.rightHeigh()) {this.right.rightRotate();}this.leftRotate();}