JavaScript 中的計算機科學：二叉搜索樹，第 2 部分
在我之前的文章中，我介紹了在 JavaScript 中創建一個簡單的二叉搜索樹。那篇文章討論了將節點添加到樹中並遍歷樹到位置和額外信息。討論中缺少的一個主要部分是從二叉搜索樹中刪除節點。從二叉搜索樹中刪除節點可能很複雜，因為樹必須保持平衡，左側的所有值都小於右側的所有值。
刪除節點時，您需要確定它是否是根節點。根節點的處理與其他節點類似，但明顯的例外是根節點最後需要設置為不同的值。為方便起見，這將被視為 JavaScript 代碼中的一種特殊情況。
移除節點的第一步是判斷該節點是否實際存在：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
parent = current;
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
parent = current;
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
if (found){
//continue
}
},
//more code here
};
remove()的第一部分 方法是使用二分搜索定位要刪除的節點，如果值小於當前節點，則向左，如果大於當前節點，則向右。當這種遍歷發生時，parent 節點也會被跟踪，因為您最終需要從其父節點中刪除該節點。當found 等於 true ，current的值 是要移除的節點。
移除節點時需要擔心三種情況：
- 葉節點
- 只有一個孩子的節點
- 一個有兩個孩子的節點
從二叉搜索樹中刪除除葉節點之外的任何內容意味著必須移動值才能正確排序樹。前兩個實現起來相對簡單，一個葉子節點被簡單地移除，一個有一個孩子的節點被移除並替換為它的孩子。最後一種情況有點複雜，後面會講到。
在知道如何刪除節點之前，您需要知道節點上存在多少個子節點。一旦知道了，你必須確定節點是否是根節點，留下一個相當簡單的決策樹：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//find the node (removed for space)
//only proceed if the node was found
if (found){
//figure out how many children
childCount = (current.left !== null ? 1 : 0) +
(current.right !== null ? 1 : 0);
//special case: the value is at the root
if (current === this._root){
switch(childCount){
//no children, just erase the root
case 0:
this._root = null;
break;
//one child, use one as the root
case 1:
this._root = (current.right === null ?
current.left : current.right);
break;
//two children, little work to do
case 2:
//TODO
//no default
}
//non-root values
} else {
switch (childCount){
//no children, just remove it from the parent
case 0:
//if the current value is less than its
//parent's, null out the left pointer
if (current.value < parent.value){
parent.left = null;
//if the current value is greater than its
//parent's, null out the right pointer
} else {
parent.right = null;
}
break;
//one child, just reassign to parent
case 1:
//if the current value is less than its
//parent's, reset the left pointer
if (current.value < parent.value){
parent.left = (current.left === null ?
current.right : current.left);
//if the current value is greater than its
//parent's, reset the right pointer
} else {
parent.right = (current.left === null ?
current.right : current.left);
}
break;
//two children, a bit more complicated
case 2:
//TODO
//no default
}
}
}
},
//more code here
};
在處理根時，這是一個簡單的覆蓋它的過程。對於非根節點，parent 上的相應指針 必鬚根據要移除的節點的值來設置：如果移除的值小於父節點，則left 指針必須重置為 null （對於沒有子節點的節點）或刪除節點的 left 指針;如果刪除的值大於父級，則 right 指針必須重置為 null 或者被移除節點的right 指針。
如前所述，刪除具有兩個子節點的節點是最複雜的操作。考慮以下二叉搜索樹的表示。
如果根為 8，左孩子為 3，如果刪除 3 會發生什麼？有兩種可能：1（3的左孩子，稱為有序前任）可以代替3或4（右子樹最左邊的孩子，稱為有序後繼）可以代替3 個。
這兩個選項中的任何一個都是合適的。要找到有序前驅，即要刪除的值之前的值，請檢查要刪除的節點的左子樹並選擇最右邊的後代；要找到有序後繼，即在刪除值之後立即出現的值，請反轉該過程並檢查最左邊的後代的右子樹。其中每一個都需要再次遍歷樹來完成操作：
BinarySearchTree.prototype = {
//more code here
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//find the node (removed for space)
//only proceed if the node was found
if (found){
//figure out how many children
childCount = (current.left !== null ? 1 : 0) +
(current.right !== null ? 1 : 0);
//special case: the value is at the root
if (current === this._root){
switch(childCount){
//other cases removed to save space
//two children, little work to do
case 2:
//new root will be the old root's left child
//...maybe
replacement = this._root.left;
//find the right-most leaf node to be
//the real new root
while (replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
//it's not the first node on the left
if (replacementParent !== null){
//remove the new root from it's
//previous position
replacementParent.right = replacement.left;
//give the new root all of the old
//root's children
replacement.right = this._root.right;
replacement.left = this._root.left;
} else {
//just assign the children
replacement.right = this._root.right;
}
//officially assign new root
this._root = replacement;
//no default
}
//non-root values
} else {
switch (childCount){
//other cases removed to save space
//two children, a bit more complicated
case 2:
//reset pointers for new traversal
replacement = current.left;
replacementParent = current;
//find the right-most node
while(replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
replacementParent.right = replacement.left;
//assign children to the replacement
replacement.right = current.right;
replacement.left = current.left;
//place the replacement in the right spot
if (current.value < parent.value){
parent.left = replacement;
} else {
parent.right = replacement;
}
//no default
}
}
}
},
//more code here
};
具有兩個子節點的根節點和非根節點刪除的代碼幾乎相同。這個實現總是通過查看左子樹並找到最右邊的後代節點來尋找有序的前任。使用 replacement 完成遍歷 和 replacementParent while 中的變量 環形。 replacement 中的節點 最終成為替換 current 的節點 ，因此通過設置其父級的 right 將其從當前位置移除 指向替換的 left 的指針 指針。在根節點的情況下，replacementParent 將是 null 當替換是根節點的直接子節點時，replacement 的 right 指針只是設置為根的 right 指針。最後一步是將替換節點分配到正確的位置。對於根節點，設置替換為新根；對於非根節點，替換被分配到原始 parent 上的適當位置 .
關於此實現的注意事項：總是用有序前驅替換節點可能導致不平衡樹，其中大多數值位於樹的一側。不平衡的樹意味著搜索效率較低，因此在現實世界場景中引起關注。有一些二叉搜索樹實現可以確定是使用有序前驅還是有序後繼來保持樹的適當平衡（通常稱為自平衡二叉搜索樹）。
此二叉搜索樹實現的完整源代碼可在我的 JavaScript GitHub 項目中的計算機科學中找到。對於替代實現，您還可以查看 Isaac Schlueter 的 GitHub fork。
