-
二叉排序樹
鎖定
- 中文名
- 二叉排序樹
- 外文名
- Binary Sort Tree
- 別 名
-
二叉查找樹
二叉搜索樹 - 別稱外文名
- Binary Search Tree
二叉排序樹定義
一棵空樹,或者是具有下列性質的二叉樹:
(1)若左子樹不空,則左子樹上所有結點的值均小於它的根結點的值;
(2)若右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;
(3)左、右子樹也分別為二叉排序樹;
【注】:以上的三種定義在不同的數據結構教材中均有不同的定義方式 但是都是正確的 在開發時需要根據不 同的需求進行選擇
【注2】:沒有鍵值相等的結點。
二叉排序樹查找
否則,若小於根結點的關鍵字值,遞歸查左子樹。
若大於根結點的關鍵字值,遞歸查右子樹。
若子樹為空,查找不成功。
平均情況分析(在成功查找兩種的情況下):
在一般情況下,設 P(n,i)為它的左子樹的結點個數為 i 時的平均查找長度。結點個數為 n = 6 且 i = 3; 則 P(n,i)= P(6, 3) = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意:這裏 P(3)、P(2) 是具有 3 個結點、2 個結點的二叉分類樹的平均查找長度。 在一般情況,P(i)為具有 i 個結點二叉分類樹的平均查找長度。平均查找長度= 每個結點的深度的總和 / 總結點數
(二叉樹圖中應為左子樹P(3),右子樹P(2))
P(3) = (1+2+2)/ 3 = 5/3
P(2) = (1+2)/ 2 = 3/2∴ P(n,i)= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P(n)=
P(n,i)/ n <= 2(1+I/n)lnn
因為 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
二叉排序樹插入刪除
與次優二叉樹相對,二叉排序樹是一種動態樹表。其特點是:樹的結構通常不是一次生成的,而是在查找過程中,當樹中不存在關鍵字等於給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點,並且是查找不成功時查找路徑上訪問的最後一個結點的左孩子或右孩子結點。
二叉排序樹插入算法
首先執行查找算法,找出被插結點的雙親結點。
判斷被插結點是其雙親結點的左、右兒子。將被插結點作為葉子結點插入。
注意:新插入的結點總是葉子結點。
struct BiTree { int data; BiTree *lchild; BiTree *rchild; }; //在二叉排序樹中插入查找關鍵字key BiTree* InsertBST(BiTree *t,int key) { if (t == NULL) { t = new BiTree(); t->lchild = t->rchild = NULL; t->data = key; return t; } if (key < t->data) t->lchild = InsertBST(t->lchild, key); else t->rchild = InsertBST(t->rchild, key); return t; } //n個數據在數組d中,tree為二叉排序樹根 BiTree* CreateBiTree(BiTree *tree, int d[], int n) { for (int i = 0; i < n; i++) tree = InsertBST(tree, d[i]); }
二叉排序樹刪除結點
在二叉排序樹刪去一個結點,分三種情況討論:
- 若*p結點為葉子結點,即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構,則可以直接刪除此子結點。
- 若*p結點只有左子樹PL或右子樹PR,此時只要令PL或PR直接成為其雙親結點*f的左子樹(當*p是左子樹)或右子樹(當*p是右子樹)即可,作此修改也不破壞二叉排序樹的特性。
- 若*p結點的左子樹和右子樹均不空。在刪去*p之後,為保持其它元素之間的相對位置不變,可按中序遍歷保持有序進行調整,可以有兩種做法:其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹,*s為*p左子樹的最右下的結點,而*p的右子樹為*s的右子樹;其二是令*p的直接前驅(或直接後繼)替代*p,然後再從二叉排序樹中刪去它的直接前驅(或直接後繼),即讓*p的左子樹的最右節點(或右子樹的最左節點)*s替代*p,再將原*s的左子樹根節點(或右子樹根節點)替代原*s。在二叉排序樹上刪除一個結點的算法如下:
C++代碼
#define Status bool Status Delete(BiTree*);//必須先聲明 Status DeleteBST(BiTree &TParent,BiTree &T, KeyType key)//若二叉排序樹T中存在關鍵字等於key的數據元素時,則刪除該數據 //元素,並返回TRUE;否則返回FALSE { if(!T)//不存在關鍵字等於key的數據元素 return false; else { if(key == T->data.key)//找到關鍵字等於key的數據元素 return Delete(TParent, T); else if(key < T->data.key) return DeleteBST(T, T->lchild,key); else return DeleteBST(T, T->rchild,key); } return true; } Status Delete(BiTree& fp , BiTree&p)//從二叉排序樹中刪除結點p,並重接它的左或右子樹 { if(!p->rchild)//右子樹空則只需重接它的左子樹 { fp->lchild = p->lchild; delete(p); } else if(!p->lchild)//左子樹空只需重接它的右子樹 { fp->rchild = p->rchild; delete(p); } else//左右子樹均不空 { q=p; fp->lchild = p->lchild; s=p->lchild;//轉左 while(s->rchild)//然後向右到盡頭 { q=s; s=s->rchild; } //此時q是s的父結點 s->rchild=p->rchild; //將s的左子樹作為q的右子樹 delete(p); } return true; }
Java代碼 /** *方法名稱:delete() *方法描述:刪除結點 *@param採用遞歸的方式進行刪除 *@returnString *@Exception */ private void deleteNode(BinarySortTree p) { //TODOAuto-generatedmethodstub if(p!=null) { //如果結點有左子樹 /*1。若p有左子樹,找到其左子樹的最右邊的葉子結點r,用該葉子結點r來替代p,把r的左孩子 作為r的雙親的右孩子。 2。若p沒有左子樹,直接用p的右孩子取代它。 */ if(p.lChild!=null) { BinarySortTree r=p.lChild; BinarySortTree prev=p.lChild; while(r.rChild!=null) { prev=r; r=r.rChild; } p.data=r.data; //若r不是p的左子樹,p的左子樹不變,r的左子樹作為r的雙親結點的右孩子結點 if(prev!=r) { prev.rChild=r.lChild; } else { //若r是p的左子樹,則p的左子樹指向r的左子樹 p.lChild=r.lChild; } } else { p=p.rChild; } } }
二叉排序樹性能分析
每個結點的C(i)為該結點的層次數。最壞情況下,當先後插入的關鍵字有序時,構成的二叉排序樹蜕變為單支樹,樹的深度為其平均查找長度(n+1)/2(和順序查找相同),最好的情況是二叉排序樹的形態和折半查找的判定樹相同,其平均查找長度和log 2 (n)成正比。
也就是説,最好情況下的算法時間複雜度為O(1),最壞情況下的算法時間複雜度為O(n)。
二叉排序樹優化
Size Balanced Tree(SBT)
Treap(Tree+Heap)
這些均可以使查找樹的高度為O(log(n))