平衡二叉树的Java实现——插入操作【无泛型】

//自己理解写的
推荐一篇关于讲解AVL的Blog平衡二叉树讲解——有详细插图。下面的代码没有使用泛型实现了插入操作，删除太麻烦了orz…

public class AVLTree {
private Node root;
private Node insert(Node node, int v){
//若该结点为空，则生成新的结点
if(node == null) {
return new Node(v);
        }
        Node left = root.getLeft();
        Node right = root.getRight();
//如果当前值小于结点的值，则插入到左子树；否则，插入到右子树
if(v < node.getV()) {
           node.setLeft(insert(node.getLeft(), v));
if(Height(node.getLeft()) - Height(node.getRight()) == 2){
//LL类型
if(v < node.getLeft().getV()) node = LL(node);
//LR类型
else node = LR(node);
           }
        } else {
            node.setRight(insert(node.getRight(), v ));
if(Height(node.getRight()) - Height(node.getLeft()) == 2){
//RR类型
if(v > node.getRight().getV()) node = RR(node);
//RL类型
else node = RL(node);
            }
        }
//更新当前结点的高度
        left.setHeight(Math.max(Height(node.getLeft()), Height(node.getRight())) + 1);
return node;
    }
private int Height(Node node) {
return node == null ? -1 : node.getHeight();
    }
//LL类型
private Node LL(Node node) {
        Node left = node.left;
        node.setLeft(left.getRight());
        left.setLeft(node);
        node.setHeight(Math.max(Height(node.getLeft()), Height(node.getRight())) + 1);
        left.setHeight(Math.max(Height(left.getLeft()), Height(left.getRight())) + 1);
return left;
    }
//RR类型
private Node RR(Node node) {
        Node right = node.right;
        node.setRight(right.getLeft());
        right.setLeft(node);
        node.setHeight(Math.max(Height(node.getLeft()), Height(node.getRight())) + 1);
        right.setHeight(Math.max(Height(right.getLeft()), Height(right.getRight())) + 1);
return right;
    }
//LR类型
private Node LR(Node node) {
        node.setLeft(RR(node.getLeft()));
return LL(node);
    }
//RL类型
private Node RL(Node node) {
        node.setRight(LL(node.getRight()));
return RR(node);
    }
}
class Node{
private int height = 0;
private int v = 0;
    Node left;
    Node right;
public Node(int v) {
this.v = v;
    }
public int getHeight() {
return height;
    }

public void setHeight(int height) {
this.height = height;
    }

public int getV() {
return v;
    }

public void setV(int v) {
this.v = v;
    }

public Node getLeft() {
return left;
    }

public void setLeft(Node left) {
this.left = left;
    }

public Node getRight() {
return right;
    }

public void setRight(Node right) {
this.right = right;
    }
}