1. 跪求平衡二叉树pascal代码

AVL树插入算法的基本步骤如下：
①在寻找新结点的插入位置的过程中，记下离该位置最近、且平衡因子不等于零的结点a（此结点即为可能出现的最小失衡子树的根）；
②修改自该结点至插入位置路径上所有结点的平衡因子（注意：树上其它结点的平衡因子均不受插入的影响）；
③判断实施插入操作之后，结点a的平衡因子的绝对值是否大于1（即判断是否失衡）。若是，进一步判断失衡类型并做相应调整；否则插入过程结束。
仍以二叉链表作为AVL树的存储结构。但每个结点需增加一个域用于存储平衡因
子。类型定义如下：
type avlpt=^anode;
anode=record
key:keytype;
bf:-1..1;
lchild,rchild:avlpt;
...
end;
在此存储结构上，AVL树的插入算法如下：
procere insert_avltree(K:keytype;var t:avlpt);
//在以T为根指针的AVL树上插入键值等于K的新结点//
begin
new(s);s^.key:=K;s^.lchild:=nil;s^.lchild:=nil;//生成以K为键值的新结点//
if t=nil
then t:=s //将新结点作为根结点插入空树//
else begin //4-10行：查找S^的插入位置，并记录a//
f:=nil;a:=t;p:=t;q:=nil;
while p<>nil do
[ if p^.bf<>0 then [a:=p;f:=p];
//a记录bf<>0的结点，其终值指向离插入位置最近的bf<>0的结点//
q:=p; //s^将插到q^上//
if s^.key<p^.key then p:=p^.lchild else p:=p^.rchild ];
if s^.key<q^.key then q^.lchild:=s else q^.rchild:=s; //插入s^//
if s^.key<a^.key
then [ p:=a^.lchild;b:=p; d:=1 ] //s^插在a^的左子树上，增量D为1//
else [ p:=a^.rchild;b:=p;d:=-1 ];//s^插在A^的右子树上，增量D为-1//
while p<>s do //修改自a^的孩子至S^路径上各结点的平衡因子//
if s^.key<p^.key //若S^在p^的左子树上//
then [ p^.bf:=1;p:=p^.lchild ]
//p^的平衡因子加工1—原来为O，因为p^是a^的子孙//
else [p^.bf:=-1;p:=p^.lchild]; //p^的平衡因子减1—原来为0//
case //判断是否失衡//
a^.bf=0: a^.bf:=d;
//找插入位置过程中未遇到bf<>0的结点，A指根树//
a^.bf+d=0: a^.bf:=0 //插入不导致以a^为根的子树失衡//
else //其它情况均失衡。差别失衡类型并调整//
[ if d=1
then case
b^.bf=1:LL-rotation;//LL型调整//
b^.bf=-1:LR-rotation//LR型调整，结束时令B指新子树的根//
end;
else case
b^.bf=-1:RR-rotation;
b^.bf=1:RL-rotation //结束时令b指新子树的根//
end;
case //将新子树链接到原a^的双亲f^上//
f=nil:t:=b;//原a^为树根//
f^.lchild=a:f^.lchild:=b;
f^.rchild=a:f^.rchild:=b
end ]
end
end;
二叉排序树（包括AVL树）适合于组织较小的、内存中能容纳的查找表。若查找表大得必须存放在外部存储器上，再用二叉排序树来表示就不合适了。对外存文件的组织来说，需考虑采用其他的数据结构（如B树和B+树）。

2. mysql innodb 索引到底是b+树还是b树

先从数据结构的角度来答。
题主应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。
这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。
从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。
那么Mysql如何衡量查询效率呢？磁盘IO次数，B-树（B类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用B+树就能很好的完成这个目的，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时啊！），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。
另一个优点是什么，B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。

至于MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。

总体来说，Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

3. Java用最少的代码写B树

可以参考一下这个例子http://blog.csdn.net/fyplinux/article/details/3434347