与之前创建的树不同，我们在使用AVL树的时候要考虑到树的高度，所以在节点上增加了一个height信息。通过Height函数来返回当前节点的高度
AVL树之所以可以保证尽可能的高度最小是因为它在创建的时候就考虑到了让每个节点的左右子树高度差不得大于2
AVL树的旋转
public TreeNode InsertAVL(int val, TreeNode node) {
if (node == null) {
node = new TreeNode(val, 0);
} else if (val < node.val) {
node.left = InsertAVL(val, node.left);
//对于高度差达到2的子树进行旋转操作
if (Height(node.left) - Height(node.rigth) == 2) {
if (val < node.left.val) {
node = SingleRotateWithLeft(node);
} else {
node = DoubleRotateWithLeft(node);
}
}
} else if (val > node.val) {
node.rigth = InsertAVL(val, node.rigth);
if (Height(node.rigth) - Height(node.left) == 2) {
if (val > node.rigth.val) {
node = SingleRotateWithRight(node);
} else {
node = DoubleRotateWithRight(node);
}
}
}
node.height = Math.max(Height(node.left), Height(node.rigth)) + 1;
return node;
}
public TreeNode SingleRotateWithLeft(TreeNode node2) {
TreeNode node1 = node2.left;
node2.left = node1.rigth;
node1.rigth = node2;
node2.height = Math.max(Height(node2.left), Height(node2.rigth)) + 1;
node1.height = Math.max(Height(node1.left), Height(node1.rigth)) + 1;
return node1;
}
public TreeNode SingleRotateWithRight(TreeNode node1) {
TreeNode node2 = node1.rigth;
node1.rigth = node2.left;
node2.left = node1;
node1.height = Math.max(Height(node1.left), Height(node1.rigth)) + 1;
node2.height = Math.max(Height(node2.left), Height(node2.rigth)) + 1;
return node2;
}
public TreeNode DoubleRotateWithLeft(TreeNode node) {
node.left = SingleRotateWithRight(node.left);
return SingleRotateWithLeft(node);
}
public TreeNode DoubleRotateWithRight(TreeNode node) {
node.rigth = SingleRotateWithLeft(node.rigth);
return SingleRotateWithRight(node);
}