学习视频:【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

（1）平衡二叉树也称平衡二叉搜索树，又叫AVL树，可以保证查询效率较高。

（2）特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有红黑树，AVL,替罪羊树,Treap,伸展树等。

目录

左旋转处理

代码实现

AVL树高度处理

右旋转的处理

双旋转的处理

主要代码处理

左旋转处理

想插入8时，右子树的高度减去左子树的高度大于1，此时不再是一颗AVL树了。

用左旋转进行处理.

创建一个新结点 newNode,值等于当前根结点的值(4)把新结点的左子树设置为当前根结点的左子树把新结点的右子树设置为当前根结点的右子树的左子树把当前根结点的值换为右子结点的值把当前根结点的右子树设置成右子树的右子树把当前根结点的左子树设置为新结点

 

中间的那个6结点没有任何结点指向也就是引用它，所以它会被销毁

左旋转的目的：降低右子树的高度

代码实现

	private void leftRotate()
	{
		//创建新的节点，以当前根节点的值
		Node newNode =new Node(value);
		//把新的节点的左子树设置为当前根节点的左子树
		newNode.left=left;
		//把新的节点的右子树设置成当前根节点的右子树的左子树
		newNode.right=right.left;
		//把当前根节点的值替换成右子节点的值
		value=right.value;
		//把当前根节点的右子树设置成右子树的右子树
		right=right.right;
		//把当前根节点的左子节点设置成新节点
		left=newNode;
	}
	
	

在写添加节点的方法的代码里，最后我们得判断当添加完一个节点后，如果（右子树的高度-左子树的高度）>1,我们就要实行左旋转.

即

if(rightHeight()-leftHeight()>1)
{
leftRotate();
}

AVL树高度处理

大致代码不变，编写重点也就是计算高度(该节点为根节点)的方法如下

public int height()
{
return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
}

返回左子树的高度

public int leftHeight()
{
    if(left==null)
{
return 0;
}
    return left.height();
}

同理返回右子树的高度

public int rightHeight()
{
    if(right==null)
{
return 0;
}
    return right.height();
}

该创建的创建以后，调用时求树的高度

avlTree.getRoot().height();

右旋转的处理

一个数列{10,12,8,9,7,6}创建出对应的二叉排序树

同理，这时相应代码变为

if(leftHeight()-rightHeight()>1)
{ 
leftRotate();
}

创建新节点，值等于当前根节点的值把新节点的右子树设置为当前根节点的右子树   newNode.right=right;把新节点的左子树设置为当前根节点的左子树的右子树 newNode.left=left.right;把当前根节点的值换为左子节点的值 value=left.value;把当前根节点的左子树设置为左子树的左子树 left=left.left;把当前根节点的右子树设置为新节点 right=newNode;

双旋转的处理

当左右旋转的处理不能满足需求时(左旋转或右旋转后，仍然为非平衡二叉树)，我们需要双旋转来处理.

问题分析：

当符合右旋转的条件时，如果它的左子树的右子树的高度大于它的右子树的高度，先对当前这个节点的左节点进行左旋转，再对当前节点进行右旋转即可。

主要代码处理

	if(leftHeight()-rightHeight()>1)//右旋转
	{
		if(left!=null&&left.rightHeight()>left.leftHeight())
		{
			//先对当前根节点的左节点(左子树)进行左旋转
			left.leftRotate();
			//再对当前根节点进行右旋转
			rightRotate();
		}
		else
		{
			//直接进行右旋转即可
			rightRotate();
		}	
        return ;
	}

if(rightHeight()-leftHeight()>1)//左旋转
{
	if(right!=null&&right.leftHeight()>right.rightHeight())
	{
		//先对当前根节点的右节点(右子树)进行右旋转
		right.rightRotate();
		//再对当前根节点进行右旋转
		rightRotate();
	}
	else
	{
		//直接进行右旋转即可
		leftRotate();
	}
}

学习如逆水行舟，不进则退。和小吴一起加油吧！