- 註冊時間
- 2006-10-8
- 最後登錄
- 2019-6-20
- 主題
- 查看
- 積分
- 1306
- 閱讀權限
- 110
- 文章
- 1393
- 相冊
- 0
- 日誌
- 1
   
狀態︰
離線
|
二元排序樹的查找演算法
在二元排序樹b中查找x的過程為:
1.若b是空樹,則搜索失敗,否則:
2.若x等於b的根節點的數據域之值,則查找成功;否則:
3.若x小於b的根節點的數據域之值,則搜索左子樹;否則:
4.查找右子樹。
/* 以下代码为C++写成, 下同 */
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){
//在根指针T所指二元排序樹中递归地查找其關键字等於key的數據元素,若查找成功,
//則指针p指向該數據元素節點,并返回TRUE,否則指针指向查找路徑上訪問的最後
//一個節點并返回FALSE,指针f指向T的雙親,其初始调用值為NULL
if(!T) { //查找不成功
p=f;
return false;
}
else if (key == T->data.key) { //查找成功
p=T;
return true;
}
else if (key < T->data.key) //在左子樹中繼續查找
return SearchBST(T->lchild, key, T, p);
else //在右子樹中繼續查找
return SearchBST(T->rchild, key, T, p);
}
[编辑] 在二叉排序樹插入結點的演算法向一個二叉排序樹b中插入一個結點s的演算法,過程為:
1.若b是空樹,則將s所指結點作為根結點插入,否則:
2.若s->data等於b的根結點的數據域之值,則返回,否則:
3.若s->data小於b的根結點的數據域之值,則把s所指結點插入到左子樹中,否則:
4.把s所指結點插入到右子樹中
/*当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE,否则返回FALSE*/
Status InsertBST(BiTree &T, ElemType e){
if(!SearchBST(T, e.key, NULL,p){
s = new BiTNode;
s->data = e; s->lchild = s->rchild = NULL;
if(!p)
T=s; //被插结点*s为新的根结点
else if (e.key < p->data.key)
p->lchld = s; //被子插结点*s为左孩子
else
p->rchild = s; //被插结点*s为右孩子
return true;
}
else
return false; //树中已有关键字相同的结点,不再插入
}
}
在二叉排序樹刪除結點的演算法
在二叉排序樹刪去一個結點,分三種情況討論:
1.若*p結點為葉子結點,即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構,則只需修改其雙親結點的指針即可。
2.若*p結點只有左子樹PL或右子樹PR,此時只要令PL或PR直接成為其雙親結點*f的左子樹(當*p是左子樹)或右子樹(當*p是右子樹)即可,作此修改也不破壞二叉排序樹的特性。
3.若*p結點的左子樹和右子樹均不空。在刪去*p之後,為保持其它元素之間的相對位置不變,可按中序遍歷保持有序進行調整,可以有兩種做法:其一是令*p的左子樹為*f的左子樹,*s為*f左子樹的最右下的結點,而*p的右子樹為*s的右子樹;其二是令*p的直接前驅(或直接後繼)替代*p,然後再從二叉排序樹中刪去它的直接前驅(或直接後繼)。在二叉排序樹上刪除一個結點的演算法如下:
Status DeleteBST(BiTree &T, KeyType key){
//若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素,并返回
//TRUE;否则返回FALSE
if(!T)
return false; //不存在关键字等于key的数据元素
else{
if(key == T->data.key) { // 找到关键字等于key的数据元素
return Delete(T);
}
else if(key < T->data.key)
return DeleteBST(T->lchild, key);
else
return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree &p){
//从二叉排序树中删除结点p,并重接它的左或右子树
if(!p->rchild){ //右子树空则只需重接它的左子树
q=p;
p=p->lchild;
delete q;
}
else if(!p->lchild){ //左子树空只需重接它的右子树
q=p;
p=p->rchild;
delete q;
}
else{ //左右子树均不空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
} //转左,然后向右到尽头
p->data = s->data; //s指向被删结点的“前驱”
if(q!=p)
q->rchild = s->lchild; //重接*q的右子树
else
q->lchild = s->lchild; //重接*q的左子树
delete s;
}
return true;
}
二叉排序樹性能分析
每個結點的為該結點的層次數。最壞情況下,當先後插入的關鍵字有序時,構成的二叉排序樹蛻變為單支樹,樹的深度為,其平均查找長度為(和順序查找相同),最好的情況是二叉排序樹的形態和折半查找的判定樹相同,其平均查找長度和成正比()。
二叉排序樹的優化
請參見主條目平衡樹。
1.Size Balanced Tree(SBT)
2.AVL樹
3.紅黑樹
4.Treap(Tree+Heap)
這些均可以使查找樹的高度為
計算機科學中的樹
二元樹 二元樹 · 二元搜尋樹 (BST) · 笛卡爾樹 · Top tree · T樹
自平衡二元搜尋樹 AA樹 · AVL樹 · 紅黑樹 · 伸展樹 · 樹堆 · 節點大小平衡樹
B樹 B樹 · B+樹 · B*樹 · Bx樹 · UB樹 · 2-3樹 · 2-3-4樹 · (a,b)-樹 · Dancing tree · H樹
Trie 前綴樹 · 後綴樹 · 基數樹
空間劃分樹 四叉樹 · 八叉樹 · k-d樹 · vp-樹 · R樹 · R*樹 · R+樹 · X樹 · M樹 · 線段樹 · 希爾伯特R樹 · 優先R樹
非二元樹 Exponential tree · Fusion tree · 區間樹 · PQ tree · Range tree · SPQR tree · Van Emde Boas tree
其他類型 堆 · 散列樹 · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree · 樹狀數組
|
-
總評分: 威望 + 2
查看全部評分
|