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