java平衡樹判斷

Ⅰ 數據結構：二叉排序樹和平衡二叉樹的判別

平衡二叉樹（AVL）

那對圖 1 進行下改造，把數據重新節點重新連接下，圖 2 如下：

圖 3 是一棵高度為 4 的 AVL 樹，有 5 層共 31 個節點，橙色是 ROOT 節點，藍色是葉子節點。對 AVL 樹的查找來看起來已經很完美了，能不能再優化下？比如，能否把這個節點里存放的 KEY 增加？能否減少樹的總層數？那減少縱深只能從橫向來想辦法，這時候可以考慮用多叉樹。

Ⅱ 數據結構 平衡二叉樹的操作演示

平衡二叉樹（AVL）

那對圖 1 進行下改造，把數據重新節點重新連接下，圖 2 如下：

圖 3 是一棵高度為 4 的 AVL 樹，有 5 層共 31 個節點，橙色是 ROOT 節點，藍色是葉子節點。對 AVL 樹的查找來看起來已經很完美了，能不能再優化下？比如，能否把這個節點里存放的 KEY 增加？能否減少樹的總層數？那減少縱深只能從橫向來想辦法，這時候可以考慮用多叉樹。

Ⅲ 平衡二叉樹是什麼

平衡二叉樹（AVL）

那對圖 1 進行下改造，把數據重新節點重新連接下，圖 2 如下：

圖 3 是一棵高度為 4 的 AVL 樹，有 5 層共 31 個節點，橙色是 ROOT 節點，藍色是葉子節點。對 AVL 樹的查找來看起來已經很完美了，能不能再優化下？比如，能否把這個節點里存放的 KEY 增加？能否減少樹的總層數？那減少縱深只能從橫向來想辦法，這時候可以考慮用多叉樹。

Ⅳ 如何判斷一棵二叉樹是否是平衡二叉樹

平衡二叉樹是指一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹，即所有結點，其左右子樹高度差不超過1。
判讀步驟是：
先計算所有結點的高度，高度是從葉節點開始（其高度為1）自底向上逐層累加的，不同葉子節點計算開始計算時，高度不同取最大值。
然後計算結點左右子樹的高度差，如果絕對值都不超過1，就是平衡的。
例子：
A
/ \
B C
/ \
D E
高度是 D:1 E:1 B:2 C:1 A:3，A的高度差為1， B為0 C為0 葉子結點可以不用計算，肯定為0。上述例子的二叉樹就是平衡的二叉樹。
看一下例子
A
/ \
B C
/ \
D E
/
F
高度是 F:1 D:2 E:1 B:3 C:1 A:4,其中A的左右子樹高度差B3 - A1 = 2，高度差大於2，所以不平衡。
當然實際判斷是不是平衡二叉樹，不一定需要計算每一個結點高度，因為左子樹高一點或者右子樹高一點，表面看過去還是比較明顯的，計算一下比較明顯的幾個點就可以。

Ⅳ 急！急！急！用java實現：二叉平衡樹的插入和刪除

另一道題的 給你放這里了 呵呵
沒找到郵箱
package Test;

import java.util.Random;
import java.io.*;
import java.util.Date;
import java.text.SimpleDateFormat;
import java.util.Calendar;

public class Bai {
/**
* 生成隨機數組
* @param n int
* @return int[]
*/
public int[] creatarray(int n) {

Random random = new Random();
int array[] = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt();
}
return array;
}

/**
* 排序函數
* @param data int[]
* @param n 參數長度
* @param cNo 比較的值 是0
*/
public int[] merge(int[] data, int n, int cNo) {
int length1 = 0;
int length2 = 0;
int length0 = 0;
int array1[] = new int[n]; //正數
int array2[] = new int[n]; //負數
int array0[] = new int[n]; //零
int redata[] = new int[n]; //返回數組
for (int i = 0; i < n; i++) {
if (data[i] > 0) {
array1[length1] = data[i];
length1++;
} else if (data[i] == 0) {
array0[length0] = data[i];
length0++;
} else {
array2[length2] = data[i];
length2++;
}
}
for (int i = 0; i < length1; i++) {
redata[i] = array1[i];
}
for (int i = 0; i < length0; i++) {
redata[length1 + i] = array0[i];
}
for (int i = 0; i < length2; i++) {
redata[length1 + length0 + i] = array2[i];
}
// for (int i = 0; i < n; i++) {
// System.out.println(data[i] + " " + redata[i]);
// }
return redata;
}

/**
* 輸出函數
* @param time int[]
* @param before int[]
* @param end int[]
* @param n int
*/
public void out(long[] time, int[] before, int[] end, int n) {
for (int v = 0; v < n; v++) {
System.out.println("第" + v + "組耗時：" + time[v] );
}
}

public static void main(String args[]) {
Bai tt = new Bai();
// Calendar cCalendar1 = Calendar.getInstance();
// long currTimebegin = cCalendar1.getTimeInMillis();
int[] array = new int[20];
int[] arrayEnd = new int[20];
int forNum = 3; //循環次數
long[] timeall = new long[forNum];
for (int i = 0; i < forNum; i++) {
array = tt.creatarray(100);
long currTimebegin = System.currentTimeMillis();
arrayEnd = tt.merge(array, 20, 0);
long currTimeend = System.currentTimeMillis();
long time = currTimeend - currTimebegin;
timeall[i] = time;
System.out.println(currTimeend + "-" + currTimebegin + "=" + time);
}
tt.out(timeall, array, arrayEnd, forNum);
}
}
可以用了 可是耗時都是在毫秒級別以下的 就是運行一次排序還不到1毫秒
我debug時看到每次時間確實可以取到 時間差也能算出來

Ⅵ 用Java怎麼實現平衡樹動態演示

publicclasstreenode1{//二叉樹的結點類
publicstringdata;//數據元數
publictreenode1left,right;//指向左,右孩子結點的鏈

publictreenode1(){
this("?");
}

publictreenode1(stringd){//構造有值結點
data=d;
left=right=null;
}

publicvoidpreorder(treenode1p){//先根次序遍歷二叉樹
if(p!=null){
system.out.print(p.data+"");
preorder(p.left);
preorder(p.right);
}
}

publicvoidinorder(treenode1p){//中根次序遍歷二叉樹
if(p!=null){inorder(p.left);
system.out.print(p.data+"");
inorder(p.right);
}
}

publicvoidpostorder(treenode1p){//後根次序遍歷二叉樹
if(p!=null){postorder(p.left);
postorder(p.right);
system.out.print(p.data+"");
}
}
}

Ⅶ 平衡樹的主要演算法

紅黑樹的平衡是在插入和刪除的過程中取得的。對一個要插入的數據項，插入程序要檢查不會破壞樹一定的特徵。如果破壞了，程序就會進行糾正，根據需要更改樹的結構。通過維持樹的特徵，保持了樹的平衡。
紅黑樹有兩個特徵：
(1) 節點都有顏色
(2) 在插入和刪除過程中，要遵循保持這些顏色的不同排列的規則。
紅黑規則：
1. 每一個節點不是紅色的就是黑色的
2. 根總是黑色的
3. 如果節點是紅色的，則它的子節點必須是黑色的（反之不一定成立）
4. 從根到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點。
（空子節點是指非葉節點可以接子節點的位置。換句話說，就是一個有右子節點的節點可能接左子節點的位置，或是有左子節點的節點可能接右子節點的位置） AVL樹，它或者是一顆空二叉樹，或者是具有下列性質的二叉樹：
(1) 其根的左右子樹高度之差的絕對值不能超過1；
(2) 其根的左右子樹都是二叉平衡樹。
AVL樹查找的時間復雜度為O(logN)，因為樹一定是平衡的。但是由於插入或刪除一個節點時需要掃描兩趟樹，依次向下查找插入點，依次向上平衡樹，AVL樹不如紅黑樹效率高，也不如紅黑樹常用。
AVL樹插入的C++代碼： template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新節點p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新節點插入左子樹result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重復元素，插入失敗unBalanced=false;x=p->element;result=Duplicate;}else...{//新節點插入右子樹result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋轉s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子樹的根}else...{//LR旋轉u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子樹的根}s->bF=0;//s的平衡因子為0unBalanced=false;//結束重新平衡操作}通常我們使用二叉樹的原因是它可以用O（logn）的復雜度來查找一個數，刪除一個數，對吧？？可是有時候會發現樹會退化，這個就可能使O（logn）->O（n）的了，那麼還不如用直接搜一次呢！！所以我們就要想辦法使一棵樹平衡。而我僅僅看了（AVL）的那個，所以也僅僅能說（AVL）的那個，至於（TREAP），我還不懂，如果你們知道演算法的話，歡迎告訴我~！謝謝~
首先引入一個變數，叫做平衡因子（r），節點X的r就表示x的左子樹的深度-右子樹的深度。然後我們要保證一棵樹平衡，就是要保證左右子樹的深度差小於等於1.所以r的取值能且僅能取0，-1，1.
其次，我要介紹旋轉，旋轉有兩種方式，就是左旋（順時針旋轉）和右旋（逆時針旋轉）。
左旋（左兒子代替根）：即用左兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那麼我們只需要把L的右兒子取代X的左兒子，然後把更新後的X賦值為L的右兒子，就可以了。
右旋（右兒子代替根）：即用右兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那麼我們只需要把R的左兒子取代X的右兒子，然後把更新後的X賦值為R的左兒子，就可以了。 Size Balanced Tree(SBT平衡樹）是2007年Winter Camp上由我國著名OI選手陳啟峰發布的他自己創造的數據結構。相比於一般的平衡樹，此平衡樹具有的特點是：快速（遠超Treap，超過AVL)、代碼簡潔、空間小（是線段樹的1/4左右）、便於調試和修改等優勢。
與一般平衡搜索樹相比，該數據結構只靠維護一個Size來保持樹的平衡，通過核心操作Maintain(修復）使得樹的修改平攤時間為O(1)。因而大大簡化代碼實現復雜度、提高運算速度。
參見網路SBT。 平衡樹的一種，每次將待操作節點提到根，每次操作時間復雜度為O(logn)。見伸展樹。 constintSPLAYmaxn=200005;constintSPLAYinf=100000000;structSplay_Node{intl,r,fa,v,sum;};structSplay{Splay_Nodet[SPLAYmaxn];introot,tot;voidcreate(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}voipdate(intnow){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}voidleft(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}voidright(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}voidsplay(intnow,intFA=0){while(t[now].fa!=FA){intfa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);elseleft(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);elseleft(now),right(now);elseif(t[fa].l==now)right(now),left(now);elseleft(fa),left(now);}update(now);if(!FA)root=now;}intlower_bound(intv){intans=0,la=0;for(intnow=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;elsenow=t[now].r;}splay(la);returnans;}voidinsert(intv){for(intnow=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}intget_lower(inta){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);returna;}intget_upper(inta){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);returna;}intget_rank(inta){splay(a);returnt[t[a].l].sum;}voiddel(intl,intr){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}intget_kth(intk){++k;for(intnow=root;;){if(t[t[now].l].sum==k-1)returnnow;if(t[t[now].l].sum>=k)now=t[now].l;elsek-=t[t[now].l].sum+1,now=t[now].r;}}};

Ⅷ 什麼是平衡二叉樹

平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。

常用演算法有：紅黑樹、AVL樹、Treap等。

平衡二叉樹的調整方法

平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：
⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；
⑵ 若插入結點的某祖先結點的平衡因子的絕對值大於1，則找出其中最小不平衡子樹的根結點；
⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整；
⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或LR型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；
⑸ 計算調整後的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整後的平衡二叉樹中是否存在平衡因子大於1的結點。