二叉平衡树 avl树

哇，大学时代的习题来了，好久没做过这东东了
不知道生锈没有。

二叉平衡树是指左右两子树的深度之差不超过一层的二叉树；
先定义数据结构:
public Class TreeNode{
int value=0;//值
public TreeNode left;//左子树
public TreeNode right;//右子树
}

树的存储： 以一维数组进行存储
[1][2][3][4][5][6][7][8][9][10][11][12][13][14]
树的插入: 直接插入追加到数组后面，这样就能保证是二叉平衡树
[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15]

为什么？ 有什么规律可循？
如何生成平衡树？

A： 1节点为第根节点， 2，3节点分别为1节点的左右子树
B： 2节点时, 4，5节点分别为 2节点的左右子树
C： 3节点时, 6，7节点分别为 3节点的左右子树
D： 4节点时, 8，9节点分别为 4节点的左右子树
E: 5节点时，10，11节点分别为5节点的左右子树
... 以此类推，得到公式： （很重要!!!!）

公式： 某个节点位置值为 N ，则
它的左子节点位置 = N*2；
它的右子节点位置 = N*2+1;

以此公式可生成上述二叉树便是二叉平衡树；

Step1:先生成该数组
TreeNode[] nodes=new TreeNode[];
nodes[0]=null;// 第0个节点不要，因为0不满足公式，直接从1开始
for(int i=1;i< nodes.length;i++){
nodes[i]=new TreeNode();
nodes[i].value=i;
}

Step2: 通过该数组构建成二叉平