Avl树旋转方式

给定一个平衡二叉树,对其进行插入操作.

上图是一颗平衡二叉树,满足每一个节点的左右子树都不大于1.

1.对该树的A节点的左儿子的左子树进行一次插入

得到如下的图.

 

F即为新插入的节点,F破坏了平衡,需要重新平衡.对B和A进行一次旋转即可,将A的左儿子旋转到A的位置.

旋转后的图如下.

 

旋转是应为A要比B大,所以A变成B的右子树,E要比B大,但比A小,所以变成A的左子树.可以想象把一个树从B哪里提起来,小的节点就向左掉,大的节点就向右掉.

private AvlNode<AnyType> rotateWithLeftChild(AvlNode A){
		AvlNode<AnyType> B=A.left;
		A.left=B.right;
		B.right=A;
		A.height=Math.Max(A.left.height(),A.right.height())+1;
		B.height=Math.Max(A.height,B.left.height())+1;
		return B;
	}

 

height()函数是用来求树的高度的函数.A的高度是左右子树的高度+1,B的高度是A的高度和B的左子树的高度的最大值

2.对A的左儿子的右子树进行一次插入.

 插入后的图如下

插入后也打破了平衡,但如果A和B进行一次旋转并不能解决问题,需要进行两次旋转.

先进行一次右旋转,再进行一次左旋转.

上图是进行一次右旋转的图,

上图是进行两次旋转后的图,又恢复了平衡.

3对A的右儿子的左子树进行一次插入与2类似.

4对A的右儿子的右子树进行一次插入与1类似.