版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
二叉搜索樹中插入與刪除操作詳解一、概述
二叉搜索樹（BinarySearchTree，BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點的左子樹僅包含鍵值小于該節(jié)點的節(jié)點，右子樹僅包含鍵值大于該節(jié)點的節(jié)點。二叉搜索樹的插入和刪除操作是維護(hù)其有序性的關(guān)鍵，以下將詳細(xì)說明這兩種操作的具體步驟和實現(xiàn)方法。
二、二叉搜索樹的插入操作
（一）插入步驟
1.創(chuàng)建新節(jié)點：生成一個包含鍵值的新節(jié)點，并初始化其左右子節(jié)點為空。
2.空樹插入：如果二叉搜索樹為空，則新節(jié)點成為根節(jié)點。
3.非空樹插入：
（1）從根節(jié)點開始，比較新節(jié)點的鍵值與當(dāng)前節(jié)點的鍵值。
（2）如果新節(jié)點的鍵值小于當(dāng)前節(jié)點的鍵值，則移動到左子節(jié)點；否則移動到右子節(jié)點。
（3）重復(fù)步驟（2），直到找到空子節(jié)點位置，將新節(jié)點插入該位置。
（二）示例
假設(shè)插入鍵值序列[8,3,10,1,6,14,4,7,13]到空二叉搜索樹中：
1.插入8，樹為空，8成為根節(jié)點。
2.插入3，小于8，插入為左子節(jié)點。
3.插入10，大于8，插入為右子節(jié)點。
4.插入1，小于8且小于3，插入為3的左子節(jié)點。
5.插入6，大于3且小于8，插入為3的右子節(jié)點。
6.插入14，大于8且大于10，插入為10的右子節(jié)點。
7.插入4，大于3且小于6，插入為6的左子節(jié)點。
8.插入7，大于6且小于8，插入為6的右子節(jié)點。
9.插入13，大于10且小于14，插入為14的左子節(jié)點。
三、二叉搜索樹的刪除操作
（一）刪除步驟
1.查找目標(biāo)節(jié)點：通過遍歷二叉搜索樹定位待刪除節(jié)點。
2.刪除節(jié)點分類：
（1）葉節(jié)點：直接刪除節(jié)點，父節(jié)點的對應(yīng)子節(jié)點指針置為空。
（2）單子節(jié)點：刪除節(jié)點后，用其子節(jié)點替代該節(jié)點位置。
（3）雙子節(jié)點：
a.找到待刪除節(jié)點的中序后繼（右子樹的最小節(jié)點）或中序前驅(qū)（左子樹的最大節(jié)點）。
b.將后繼/前驅(qū)的鍵值替換到待刪除節(jié)點。
c.刪除后繼/前驅(qū)節(jié)點（此時變?yōu)閱巫庸?jié)點或葉節(jié)點，可按前述規(guī)則處理）。
（二）示例
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的7：
1.查找節(jié)點7，發(fā)現(xiàn)其左右子節(jié)點均存在。
2.找到節(jié)點7的右子樹最小節(jié)點13（中序后繼）。
3.將13的鍵值替換到節(jié)點7，節(jié)點7變?yōu)?3。
4.刪除原節(jié)點13，其為葉節(jié)點，直接刪除。
（三）邊界情況處理
1.根節(jié)點刪除：刪除根節(jié)點后，選擇新的根節(jié)點（如中序后繼）替代。
2.空樹刪除：無操作。
3.未找到節(jié)點：返回刪除失敗提示。
四、插入與刪除的效率分析
（一）插入操作
-時間復(fù)雜度：平均O(logn)，最壞O(n)（樹退化成鏈表）。
-空間復(fù)雜度：O(n)，用于存儲樹節(jié)點。
（二）刪除操作
-時間復(fù)雜度：平均O(logn)，最壞O(n)。
-空間復(fù)雜度：O(logn)，遞歸?；虻^程中的臨時變量。
五、總結(jié)
二叉搜索樹的插入和刪除操作通過維護(hù)節(jié)點間的鍵值有序性，保證了樹的搜索效率。正確處理不同類型的節(jié)點（葉節(jié)點、單子節(jié)點、雙子節(jié)點）是確保樹結(jié)構(gòu)完整性的關(guān)鍵。在實際應(yīng)用中，可通過平衡二叉搜索樹（如AVL樹、紅黑樹）進(jìn)一步優(yōu)化性能。
一、概述
二叉搜索樹（BinarySearchTree，BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點的左子樹僅包含鍵值小于該節(jié)點的節(jié)點，右子樹僅包含鍵值大于該節(jié)點的節(jié)點。二叉搜索樹的插入和刪除操作是維護(hù)其有序性的關(guān)鍵，以下將詳細(xì)說明這兩種操作的具體步驟和實現(xiàn)方法。二叉搜索樹的性質(zhì)是其所有操作的基礎(chǔ)，必須首先明確：
（一）二叉搜索樹的性質(zhì)
1.對于任何節(jié)點N，N的左子樹中所有節(jié)點的鍵值均小于N的鍵值。
2.對于任何節(jié)點N，N的右子樹中所有節(jié)點的鍵值均大于N的鍵值。
3.左子樹和右子樹本身也必須是一棵二叉搜索樹。
4.沒有重復(fù)的鍵值節(jié)點（根據(jù)具體實現(xiàn)，通常允許或禁止重復(fù)）。
二、二叉搜索樹的插入操作
（一）插入步驟
1.創(chuàng)建新節(jié)點：生成一個包含鍵值的新節(jié)點，并初始化其左右子節(jié)點指針為`null`（或空指針）。節(jié)點通常還包含其他字段，如數(shù)據(jù)值、左右子節(jié)點引用等。
示例代碼片段（偽代碼）：
```
NodenewNode=newNode(keyValue);
newNode.left=null;
newNode.right=null;
```
2.空樹插入：如果二叉搜索樹當(dāng)前為空（根節(jié)點為`null`），則新節(jié)點成為根節(jié)點。
操作步驟：
（1）檢查根節(jié)點是否為`null`。
（2）如果為`null`，將新節(jié)點賦值給根節(jié)點。
```
if(root==null){
root=newNode;
}
```
3.非空樹插入：如果二叉搜索樹不為空，則按照鍵值大小關(guān)系逐層查找插入位置。
（1）初始化當(dāng)前節(jié)點為根節(jié)點。
（2）比較新節(jié)點的鍵值與當(dāng)前節(jié)點的鍵值。
（3）如果新節(jié)點的鍵值小于當(dāng)前節(jié)點的鍵值：
-如果當(dāng)前節(jié)點的左子節(jié)點為`null`，則將新節(jié)點插入為當(dāng)前節(jié)點的左子節(jié)點。
-如果當(dāng)前節(jié)點的左子節(jié)點不為`null`，則將當(dāng)前節(jié)點更新為其左子節(jié)點，并返回步驟（2）。
（4）如果新節(jié)點的鍵值大于或等于當(dāng)前節(jié)點的鍵值（根據(jù)是否允許重復(fù)鍵值處理）：
-如果允許重復(fù)，且鍵值等于當(dāng)前節(jié)點，可以選擇插入到左或右（例如，統(tǒng)一插入左子樹）。
-如果不允許重復(fù)，且鍵值等于當(dāng)前節(jié)點，則不插入并返回。
-如果當(dāng)前節(jié)點的右子節(jié)點為`null`，則將新節(jié)點插入為當(dāng)前節(jié)點的右子節(jié)點。
-如果當(dāng)前節(jié)點的右子節(jié)點不為`null`，則將當(dāng)前節(jié)點更新為其右子節(jié)點，并返回步驟（2）。
```
Nodecurrent=root;
Nodeparent=null;//用于記錄父節(jié)點
while(current!=null){
parent=current;
if(newNode.keyValue<current.keyValue){
current=current.left;
}elseif(newNode.keyValue>current.keyValue){//或者處理等于的情況
current=current.right;
}else{
//鍵值已存在，根據(jù)需求處理（例如插入左子樹）
current=current.left;
}
}
//current==null時，parent是插入位置
if(newNode.keyValue<parent.keyValue){
parent.left=newNode;
}else{
parent.right=newNode;
}
```
（二）示例
假設(shè)插入鍵值序列[8,3,10,1,6,14,4,7,13]到空二叉搜索樹中，并展示每一步的樹結(jié)構(gòu)變化：
1.插入8：樹為空，8成為根節(jié)點。
```
8
```
2.插入3，小于8，插入為8的左子節(jié)點。
```
8
/
3
```
3.插入10，大于8，插入為8的右子節(jié)點。
```
8
/\
310
```
4.插入1，小于8且小于3，插入為3的左子節(jié)點。
```
8
/\
310
/
1
```
5.插入6，大于3且小于8，插入為3的右子節(jié)點。
```
8
/\
310
/\
16
```
6.插入14，大于8且大于10，插入為10的右子節(jié)點。
```
8
/\
310
/\
16
\
14
```
7.插入4，大于3且小于6，插入為6的左子節(jié)點。
```
8
/\
310
/\
16
//
414
```
8.插入7，大于6且小于8，插入為6的右子節(jié)點。
```
8
/\
310
/\
16
//\
4714
```
9.插入13，大于10且小于14，插入為14的左子節(jié)點。
```
8
/\
310
/\
16
//\
4714
\/
13
```
三、二叉搜索樹的刪除操作
（一）刪除步驟
刪除操作相對復(fù)雜，需要根據(jù)待刪除節(jié)點的子節(jié)點情況分情況處理。主要步驟如下：
1.查找目標(biāo)節(jié)點：通過遍歷二叉搜索樹定位待刪除節(jié)點（記為`targetNode`）。
-使用遞歸或迭代方式，比較鍵值并沿左或右子樹查找。
-同時記錄`targetNode`的父節(jié)點（記為`parentNode`）。
2.確定節(jié)點類型并執(zhí)行刪除：根據(jù)`targetNode`的子節(jié)點數(shù)量進(jìn)行分類處理。
（1）刪除葉節(jié)點（無子節(jié)點）：
a.檢查`targetNode`是否為左子節(jié)點（`parentNode.left==targetNode`）。
b.如果是，將`parentNode.left`指針置為`null`。
c.如果不是，將`parentNode.right`指針置為`null`。
d.刪除`targetNode`占用的內(nèi)存空間（在編程語言中）。
（2）刪除單子節(jié)點（一個子節(jié)點）：
a.檢查`targetNode`有一個左子節(jié)點或右子節(jié)點。
b.假設(shè)`targetNode`有左子節(jié)點（右子節(jié)點邏輯相同）：
-將`targetNode`的左子節(jié)點提升到`targetNode`的位置。
-更新`parentNode`的對應(yīng)指針（左或右）指向`targetNode`的左子節(jié)點。
c.假設(shè)`targetNode`有右子節(jié)點：
-將`targetNode`的右子節(jié)點提升到`targetNode`的位置。
-更新`parentNode`的對應(yīng)指針指向`targetNode`的右子節(jié)點。
d.刪除`targetNode`占用的內(nèi)存空間。
（3）刪除雙子節(jié)點（左右子節(jié)點均存在）：
a.尋找中序后繼：
-中序后繼是`targetNode`右子樹中的最小節(jié)點（即最左側(cè)節(jié)點）。
-從`targetNode.right`開始，不斷向左移動，直到到達(dá)最左側(cè)節(jié)點（`inorderSuccessor`）。
-記錄`inorderSuccessor`的父節(jié)點（`inorderSuccessorParent`）。
b.尋找中序前驅(qū)（作為替代方案）：
-中序前驅(qū)是`targetNode`左子樹中的最大節(jié)點（即最右側(cè)節(jié)點）。
-從`targetNode.left`開始，不斷向右移動，直到到達(dá)最右側(cè)節(jié)點（`inorderPredecessor`）。
-記錄`inorderPredecessor`的父節(jié)點（`inorderPredecessorParent`）。
c.替換鍵值：
-選擇中序后繼或中序前驅(qū)（通常選擇后繼，因為前驅(qū)可能需要同時處理其右子樹）。
-將`inorderSuccessor.keyValue`的值復(fù)制到`targetNode.keyValue`。
d.刪除原后繼節(jié)點：
-`inorderSuccessor`節(jié)點現(xiàn)在成為葉節(jié)點或單子節(jié)點（因為它取代了`targetNode`的位置，其原來的子節(jié)點現(xiàn)在直接掛在`inorderSuccessor`下）。
-根據(jù)其子節(jié)點情況執(zhí)行刪除葉節(jié)點或單子節(jié)點的操作（步驟（1）或（2））。
3.更新根節(jié)點（如果需要）：如果刪除的是根節(jié)點，則根節(jié)點指針需要指向新的樹根（通常由步驟（2）c中的替換操作間接完成）。
4.返回結(jié)果：返回刪除成功或未找到節(jié)點的指示。
（二）示例
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的7：
1.查找節(jié)點7：
-從根節(jié)點8開始，7小于8，移動到3。
-7大于3，移動到6。
-7大于6，移動到7節(jié)點，找到目標(biāo)節(jié)點。
-記錄父節(jié)點為6。
2.確定節(jié)點類型：節(jié)點7是葉節(jié)點（無子節(jié)點）。
3.執(zhí)行刪除：
-檢查`parentNode`（6）的右子節(jié)點是否為`targetNode`（7）。是。
-將`parentNode.right`指針置為`null`（即`6.right=null`）。
-刪除節(jié)點7占用的內(nèi)存空間。
4.結(jié)果樹結(jié)構(gòu)（對比刪除前）：
```
8
/\
310
/\
16
//\
4714
\/
13
```
刪除節(jié)點7后：
```
8
/\
310
/\
16
//
414
/
13
```
（三）示例（雙子節(jié)點刪除）
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的8（根節(jié)點）：
1.查找節(jié)點8：
-根節(jié)點就是8，`parentNode`為`null`。
2.確定節(jié)點類型：節(jié)點8是雙子節(jié)點（左子節(jié)點3和右子節(jié)點10）。
3.尋找中序后繼：
-從`targetNode.right`（節(jié)點10）開始，向左移動到節(jié)點13。
-`inorderSuccessor`是13，`inorderSuccessorParent`是10。
4.替換鍵值：
-將13的鍵值復(fù)制到8：`8.keyValue=13`。
5.刪除原后繼節(jié)點13：
-節(jié)點13現(xiàn)在是葉節(jié)點（原右子節(jié)點14直接掛在13下，但13作為右子節(jié)點被刪除）。
-將`inorderSuccessorParent.right`指針置為`null`（即`10.right=null`）。
6.更新根節(jié)點：新的根節(jié)點是8（現(xiàn)在包含鍵值13）。
7.結(jié)果樹結(jié)構(gòu)：
-刪除前：
```
8
/\
310
/\
16
//\
4714
\/
13
```
-刪除后：
```
13
/\
310
/\
16
//\
4714
```
（四）邊界情況處理
1.根節(jié)點刪除：
-需要找到新的根節(jié)點（通常為中序后繼或前驅(qū)），并將根節(jié)點指針指向該節(jié)點。
-如果新根節(jié)點有子節(jié)點，需要將其移動到原樹中。
2.空樹刪除：
-無法刪除，返回刪除失敗或空操作。
3.未找到節(jié)點：
-遍歷完成后未找到指定鍵值的節(jié)點，返回刪除失敗。
4.刪除不存在的鍵值：
-與未找到節(jié)點情況相同。
5.刪除導(dǎo)致樹結(jié)構(gòu)嚴(yán)重退化：
-雖然二叉搜索樹刪除操作不會自平衡，但如果連續(xù)刪除導(dǎo)致樹高度接近線性，性能會下降。在實際應(yīng)用中可結(jié)合AVL樹或紅黑樹等自平衡二叉搜索樹。
四、插入與刪除的效率分析
（一）插入操作
-時間復(fù)雜度：
-平均情況：O(logn)，樹相對平衡時，每次插入只需遍歷樹的高度。
-最壞情況：O(n)，樹完全退化成鏈表，每次插入需要遍歷所有節(jié)點。
-影響因素：樹的高度。
-空間復(fù)雜度：
-O(n)，用于存儲樹中的所有節(jié)點。
-遞歸實現(xiàn)時，空間復(fù)雜度為O(h)，h為樹的高度。
-優(yōu)化方法：
-確保插入順序盡量隨機(jī)，避免構(gòu)建極端不平衡的樹。
-使用自平衡二叉搜索樹。
（二）刪除操作
-時間復(fù)雜度：
-平均情況：O(logn)，查找目標(biāo)節(jié)點和中序后繼/前驅(qū)的時間復(fù)雜度均為O(logn)。
-最壞情況：O(n)，與查找和刪除操作相關(guān)的節(jié)點數(shù)量接近n（例如刪除根節(jié)點及其所有子節(jié)點）。
-影響因素：樹的平衡性。
-空間復(fù)雜度：
-O(logn)，主要來自遞歸調(diào)用?；虻^程中的臨時變量。
-優(yōu)化方法：
-與插入類似，保持樹的平衡。
-使用自平衡二叉搜索樹。
五、總結(jié)
二叉搜索樹的插入和刪除操作是維護(hù)其有序性的核心機(jī)制。插入操作通過比較鍵值大小逐層查找空位置完成，而刪除操作則根據(jù)節(jié)點子節(jié)點數(shù)量分情況處理，雙子節(jié)點刪除通常通過中序后繼/前驅(qū)替換實現(xiàn)。正確處理各種邊界情況是確保操作正確性的關(guān)鍵。雖然基本的二叉搜索樹在極端情況下效率會下降，但通過使用自平衡變體（如AVL樹、紅黑樹），可以保證其操作時間復(fù)雜度始終為O(logn)，使其在動態(tài)數(shù)據(jù)集中仍具有很高的實用價值。理解并熟練掌握這兩種操作，是深入學(xué)習(xí)和應(yīng)用二叉搜索樹的基礎(chǔ)。
一、概述
二叉搜索樹（BinarySearchTree，BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點的左子樹僅包含鍵值小于該節(jié)點的節(jié)點，右子樹僅包含鍵值大于該節(jié)點的節(jié)點。二叉搜索樹的插入和刪除操作是維護(hù)其有序性的關(guān)鍵，以下將詳細(xì)說明這兩種操作的具體步驟和實現(xiàn)方法。
二、二叉搜索樹的插入操作
（一）插入步驟
1.創(chuàng)建新節(jié)點：生成一個包含鍵值的新節(jié)點，并初始化其左右子節(jié)點為空。
2.空樹插入：如果二叉搜索樹為空，則新節(jié)點成為根節(jié)點。
3.非空樹插入：
（1）從根節(jié)點開始，比較新節(jié)點的鍵值與當(dāng)前節(jié)點的鍵值。
（2）如果新節(jié)點的鍵值小于當(dāng)前節(jié)點的鍵值，則移動到左子節(jié)點；否則移動到右子節(jié)點。
（3）重復(fù)步驟（2），直到找到空子節(jié)點位置，將新節(jié)點插入該位置。
（二）示例
假設(shè)插入鍵值序列[8,3,10,1,6,14,4,7,13]到空二叉搜索樹中：
1.插入8，樹為空，8成為根節(jié)點。
2.插入3，小于8，插入為左子節(jié)點。
3.插入10，大于8，插入為右子節(jié)點。
4.插入1，小于8且小于3，插入為3的左子節(jié)點。
5.插入6，大于3且小于8，插入為3的右子節(jié)點。
6.插入14，大于8且大于10，插入為10的右子節(jié)點。
7.插入4，大于3且小于6，插入為6的左子節(jié)點。
8.插入7，大于6且小于8，插入為6的右子節(jié)點。
9.插入13，大于10且小于14，插入為14的左子節(jié)點。
三、二叉搜索樹的刪除操作
（一）刪除步驟
1.查找目標(biāo)節(jié)點：通過遍歷二叉搜索樹定位待刪除節(jié)點。
2.刪除節(jié)點分類：
（1）葉節(jié)點：直接刪除節(jié)點，父節(jié)點的對應(yīng)子節(jié)點指針置為空。
（2）單子節(jié)點：刪除節(jié)點后，用其子節(jié)點替代該節(jié)點位置。
（3）雙子節(jié)點：
a.找到待刪除節(jié)點的中序后繼（右子樹的最小節(jié)點）或中序前驅(qū)（左子樹的最大節(jié)點）。
b.將后繼/前驅(qū)的鍵值替換到待刪除節(jié)點。
c.刪除后繼/前驅(qū)節(jié)點（此時變?yōu)閱巫庸?jié)點或葉節(jié)點，可按前述規(guī)則處理）。
（二）示例
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的7：
1.查找節(jié)點7，發(fā)現(xiàn)其左右子節(jié)點均存在。
2.找到節(jié)點7的右子樹最小節(jié)點13（中序后繼）。
3.將13的鍵值替換到節(jié)點7，節(jié)點7變?yōu)?3。
4.刪除原節(jié)點13，其為葉節(jié)點，直接刪除。
（三）邊界情況處理
1.根節(jié)點刪除：刪除根節(jié)點后，選擇新的根節(jié)點（如中序后繼）替代。
2.空樹刪除：無操作。
3.未找到節(jié)點：返回刪除失敗提示。
四、插入與刪除的效率分析
（一）插入操作
-時間復(fù)雜度：平均O(logn)，最壞O(n)（樹退化成鏈表）。
-空間復(fù)雜度：O(n)，用于存儲樹節(jié)點。
（二）刪除操作
-時間復(fù)雜度：平均O(logn)，最壞O(n)。
-空間復(fù)雜度：O(logn)，遞歸棧或迭代過程中的臨時變量。
五、總結(jié)
二叉搜索樹的插入和刪除操作通過維護(hù)節(jié)點間的鍵值有序性，保證了樹的搜索效率。正確處理不同類型的節(jié)點（葉節(jié)點、單子節(jié)點、雙子節(jié)點）是確保樹結(jié)構(gòu)完整性的關(guān)鍵。在實際應(yīng)用中，可通過平衡二叉搜索樹（如AVL樹、紅黑樹）進(jìn)一步優(yōu)化性能。
一、概述
二叉搜索樹（BinarySearchTree，BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點的左子樹僅包含鍵值小于該節(jié)點的節(jié)點，右子樹僅包含鍵值大于該節(jié)點的節(jié)點。二叉搜索樹的插入和刪除操作是維護(hù)其有序性的關(guān)鍵，以下將詳細(xì)說明這兩種操作的具體步驟和實現(xiàn)方法。二叉搜索樹的性質(zhì)是其所有操作的基礎(chǔ)，必須首先明確：
（一）二叉搜索樹的性質(zhì)
1.對于任何節(jié)點N，N的左子樹中所有節(jié)點的鍵值均小于N的鍵值。
2.對于任何節(jié)點N，N的右子樹中所有節(jié)點的鍵值均大于N的鍵值。
3.左子樹和右子樹本身也必須是一棵二叉搜索樹。
4.沒有重復(fù)的鍵值節(jié)點（根據(jù)具體實現(xiàn)，通常允許或禁止重復(fù)）。
二、二叉搜索樹的插入操作
（一）插入步驟
1.創(chuàng)建新節(jié)點：生成一個包含鍵值的新節(jié)點，并初始化其左右子節(jié)點指針為`null`（或空指針）。節(jié)點通常還包含其他字段，如數(shù)據(jù)值、左右子節(jié)點引用等。
示例代碼片段（偽代碼）：
```
NodenewNode=newNode(keyValue);
newNode.left=null;
newNode.right=null;
```
2.空樹插入：如果二叉搜索樹當(dāng)前為空（根節(jié)點為`null`），則新節(jié)點成為根節(jié)點。
操作步驟：
（1）檢查根節(jié)點是否為`null`。
（2）如果為`null`，將新節(jié)點賦值給根節(jié)點。
```
if(root==null){
root=newNode;
}
```
3.非空樹插入：如果二叉搜索樹不為空，則按照鍵值大小關(guān)系逐層查找插入位置。
（1）初始化當(dāng)前節(jié)點為根節(jié)點。
（2）比較新節(jié)點的鍵值與當(dāng)前節(jié)點的鍵值。
（3）如果新節(jié)點的鍵值小于當(dāng)前節(jié)點的鍵值：
-如果當(dāng)前節(jié)點的左子節(jié)點為`null`，則將新節(jié)點插入為當(dāng)前節(jié)點的左子節(jié)點。
-如果當(dāng)前節(jié)點的左子節(jié)點不為`null`，則將當(dāng)前節(jié)點更新為其左子節(jié)點，并返回步驟（2）。
（4）如果新節(jié)點的鍵值大于或等于當(dāng)前節(jié)點的鍵值（根據(jù)是否允許重復(fù)鍵值處理）：
-如果允許重復(fù)，且鍵值等于當(dāng)前節(jié)點，可以選擇插入到左或右（例如，統(tǒng)一插入左子樹）。
-如果不允許重復(fù)，且鍵值等于當(dāng)前節(jié)點，則不插入并返回。
-如果當(dāng)前節(jié)點的右子節(jié)點為`null`，則將新節(jié)點插入為當(dāng)前節(jié)點的右子節(jié)點。
-如果當(dāng)前節(jié)點的右子節(jié)點不為`null`，則將當(dāng)前節(jié)點更新為其右子節(jié)點，并返回步驟（2）。
```
Nodecurrent=root;
Nodeparent=null;//用于記錄父節(jié)點
while(current!=null){
parent=current;
if(newNode.keyValue<current.keyValue){
current=current.left;
}elseif(newNode.keyValue>current.keyValue){//或者處理等于的情況
current=current.right;
}else{
//鍵值已存在，根據(jù)需求處理（例如插入左子樹）
current=current.left;
}
}
//current==null時，parent是插入位置
if(newNode.keyValue<parent.keyValue){
parent.left=newNode;
}else{
parent.right=newNode;
}
```
（二）示例
假設(shè)插入鍵值序列[8,3,10,1,6,14,4,7,13]到空二叉搜索樹中，并展示每一步的樹結(jié)構(gòu)變化：
1.插入8：樹為空，8成為根節(jié)點。
```
8
```
2.插入3，小于8，插入為8的左子節(jié)點。
```
8
/
3
```
3.插入10，大于8，插入為8的右子節(jié)點。
```
8
/\
310
```
4.插入1，小于8且小于3，插入為3的左子節(jié)點。
```
8
/\
310
/
1
```
5.插入6，大于3且小于8，插入為3的右子節(jié)點。
```
8
/\
310
/\
16
```
6.插入14，大于8且大于10，插入為10的右子節(jié)點。
```
8
/\
310
/\
16
\
14
```
7.插入4，大于3且小于6，插入為6的左子節(jié)點。
```
8
/\
310
/\
16
//
414
```
8.插入7，大于6且小于8，插入為6的右子節(jié)點。
```
8
/\
310
/\
16
//\
4714
```
9.插入13，大于10且小于14，插入為14的左子節(jié)點。
```
8
/\
310
/\
16
//\
4714
\/
13
```
三、二叉搜索樹的刪除操作
（一）刪除步驟
刪除操作相對復(fù)雜，需要根據(jù)待刪除節(jié)點的子節(jié)點情況分情況處理。主要步驟如下：
1.查找目標(biāo)節(jié)點：通過遍歷二叉搜索樹定位待刪除節(jié)點（記為`targetNode`）。
-使用遞歸或迭代方式，比較鍵值并沿左或右子樹查找。
-同時記錄`targetNode`的父節(jié)點（記為`parentNode`）。
2.確定節(jié)點類型并執(zhí)行刪除：根據(jù)`targetNode`的子節(jié)點數(shù)量進(jìn)行分類處理。
（1）刪除葉節(jié)點（無子節(jié)點）：
a.檢查`targetNode`是否為左子節(jié)點（`parentNode.left==targetNode`）。
b.如果是，將`parentNode.left`指針置為`null`。
c.如果不是，將`parentNode.right`指針置為`null`。
d.刪除`targetNode`占用的內(nèi)存空間（在編程語言中）。
（2）刪除單子節(jié)點（一個子節(jié)點）：
a.檢查`targetNode`有一個左子節(jié)點或右子節(jié)點。
b.假設(shè)`targetNode`有左子節(jié)點（右子節(jié)點邏輯相同）：
-將`targetNode`的左子節(jié)點提升到`targetNode`的位置。
-更新`parentNode`的對應(yīng)指針（左或右）指向`targetNode`的左子節(jié)點。
c.假設(shè)`targetNode`有右子節(jié)點：
-將`targetNode`的右子節(jié)點提升到`targetNode`的位置。
-更新`parentNode`的對應(yīng)指針指向`targetNode`的右子節(jié)點。
d.刪除`targetNode`占用的內(nèi)存空間。
（3）刪除雙子節(jié)點（左右子節(jié)點均存在）：
a.尋找中序后繼：
-中序后繼是`targetNode`右子樹中的最小節(jié)點（即最左側(cè)節(jié)點）。
-從`targetNode.right`開始，不斷向左移動，直到到達(dá)最左側(cè)節(jié)點（`inorderSuccessor`）。
-記錄`inorderSuccessor`的父節(jié)點（`inorderSuccessorParent`）。
b.尋找中序前驅(qū)（作為替代方案）：
-中序前驅(qū)是`targetNode`左子樹中的最大節(jié)點（即最右側(cè)節(jié)點）。
-從`targetNode.left`開始，不斷向右移動，直到到達(dá)最右側(cè)節(jié)點（`inorderPredecessor`）。
-記錄`inorderPredecessor`的父節(jié)點（`inorderPredecessorParent`）。
c.替換鍵值：
-選擇中序后繼或中序前驅(qū)（通常選擇后繼，因為前驅(qū)可能需要同時處理其右子樹）。
-將`inorderSuccessor.keyValue`的值復(fù)制到`targetNode.keyValue`。
d.刪除原后繼節(jié)點：
-`inorderSuccessor`節(jié)點現(xiàn)在成為葉節(jié)點或單子節(jié)點（因為它取代了`targetNode`的位置，其原來的子節(jié)點現(xiàn)在直接掛在`inorderSuccessor`下）。
-根據(jù)其子節(jié)點情況執(zhí)行刪除葉節(jié)點或單子節(jié)點的操作（步驟（1）或（2））。
3.更新根節(jié)點（如果需要）：如果刪除的是根節(jié)點，則根節(jié)點指針需要指向新的樹根（通常由步驟（2）c中的替換操作間接完成）。
4.返回結(jié)果：返回刪除成功或未找到節(jié)點的指示。
（二）示例
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的7：
1.查找節(jié)點7：
-從根節(jié)點8開始，7小于8，移動到3。
-7大于3，移動到6。
-7大于6，移動到7節(jié)點，找到目標(biāo)節(jié)點。
-記錄父節(jié)點為6。
2.確定節(jié)點類型：節(jié)點7是葉節(jié)點（無子節(jié)點）。
3.執(zhí)行刪除：
-檢查`parentNode`（6）的右子節(jié)點是否為`targetNode`（7）。是。
-將`parentNode.right`指針置為`null`（即`6.right=null`）。
-刪除節(jié)點7占用的內(nèi)存空間。
4.結(jié)果樹結(jié)構(gòu)（對比刪除前）：
```
8
/\
310
/\
16
//\
4714
\/
13
```
刪除節(jié)點7后：
```
8
/\
310
/\
16
//
414
/
13
```
（三）示例（雙子節(jié)點刪除）
假設(shè)刪除鍵值序列[8,3,10,1,6,14,4,7,13]中的8（根節(jié)點）：
1.查找節(jié)點8：
-根節(jié)點就是8，`parentNode`為`null`。
2.確定節(jié)點類型：節(jié)點8是雙子節(jié)點（左子節(jié)點3和右子節(jié)點10）。
3.尋找中序后繼：
-
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2026年湖南九嶷職業(yè)技術(shù)學(xué)院單招綜合素質(zhì)考試模擬試題含詳細(xì)答案解析
- 2026年山西工程職業(yè)學(xué)院單招職業(yè)技能考試模擬試題含詳細(xì)答案解析
- 2026年武威職業(yè)學(xué)院單招綜合素質(zhì)筆試備考題庫含詳細(xì)答案解析
- 2026年河南推拿職業(yè)學(xué)院單招綜合素質(zhì)考試備考試題含詳細(xì)答案解析
- 2026中國科學(xué)院廣州地球化學(xué)研究所科研助理招聘1人(郗云飛老師團(tuán)隊)參考考試題庫及答案解析
- 2026年內(nèi)蒙古商貿(mào)職業(yè)學(xué)院單招職業(yè)技能考試模擬試題含詳細(xì)答案解析
- 2026年南京鐵道職業(yè)技術(shù)學(xué)院單招綜合素質(zhì)考試備考試題含詳細(xì)答案解析
- 2026河南洛陽瀍河區(qū)北窯社區(qū)衛(wèi)生服務(wù)中心招聘專業(yè)技術(shù)人才9人備考考試題庫及答案解析
- 2026年恩施職業(yè)技術(shù)學(xué)院單招綜合素質(zhì)考試備考題庫含詳細(xì)答案解析
- 2026年哈爾濱應(yīng)用職業(yè)技術(shù)學(xué)院單招綜合素質(zhì)考試參考題庫含詳細(xì)答案解析
- 危險化學(xué)品安全法解讀
- 廣東省佛山市南海區(qū)2025-2026學(xué)年上學(xué)期期末八年級數(shù)學(xué)試卷（含答案）
- 放射應(yīng)急演練及培訓(xùn)制度
- 儲能技術(shù)培訓(xùn)課件模板
- IT項目管理-項目管理計劃
- GB/T 7714-2025信息與文獻(xiàn)參考文獻(xiàn)著錄規(guī)則
- 2026元旦主題班會：馬年猜猜樂新春祝福版 教學(xué)課件
- 光伏收購合同范本
- 2025海洋水下機(jī)器人控制系統(tǒng)行業(yè)市場需求及發(fā)展趨勢分析投資評估規(guī)劃報告
- 物流金融管理培訓(xùn)課件
- 教學(xué)管理系統(tǒng)項目開發(fā)計劃大全五
評論
0/150
提交評論