与えられた BST 、タスクはこのノードを削除することです。 BST 、これは 3 つのシナリオに分類できます。
ケース 1. BST でリーフ ノードを削除する
BSTでの削除
ケース 2. BST で単一の子を持つノードを削除する
BST では、単一の子ノードの削除も簡単です。 子をノードにコピーし、ノードを削除します 。
Mavenリポジトリ
BSTでの削除
ケース 3. BST で両方の子を持つノードを削除する
両方の子を持つノードを削除するのはそれほど簡単ではありません。ここで私たちはしなければなりません ノードを削除すると、結果のツリーが BST のプロパティに従います。
秘訣は、ノードの順序後継者を見つけることです。インオーダーサクセサの内容をノードにコピーし、インオーダーサクセサを削除します。
注記： 順序先行も使用できます。
Javaの文字列形式
バイナリツリーの削除
注記： Inorder継承子は、右側の子が空でない場合にのみ必要です。この特定のケースでは、ノードの右側の子の最小値を見つけることによって、順序後続者を取得できます。
推奨される実践方法 BST からノードを削除します。 試してみてください。BST での削除操作の実装:
C++ #include using namespace std; struct Node { int key; struct Node *left, *right; }; // A utility function to create a new BST node Node* newNode(int item) { Node* temp = new Node; temp->キー = アイテム; 一時->左 = 一時->右 = NULL; 戻り温度; } // BST の順序トラバーサルを行うユーティリティ関数 void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(ルート->右); } } /* 指定されたキーを持つ新しいノードを * BST に挿入するユーティリティ関数 */ Node* insert(Node* node, int key) { /* ツリーが空の場合は、新しいノードを返します */ if (node = = NULL) newNode(key) を返します。 /* それ以外の場合は、ツリーを下に向かって再帰します */ if (key< node->キー) ノード->左 = 挿入(ノード->左, キー); else ノード->右 = 挿入(ノード->右, キー); /* (変更されていない) ノード ポインタを返します */ return node; } /* 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルートを返します */ Node* deleteNode(Node* root, int k) { // 基本ケース if (root == NULL) return root; // 削除するキーがルートのキーより小さい場合、 // 左側のサブツリーにあります if (k< root->key) { root->left = deleteNode(root->left, k); ルートを返します。 } // 削除するキーがルートのキーより大きい場合、 // キーは右のサブツリーにあります。そうでない場合は (k> root->key) { root->right = deleteNode(root->right 、k); ルートを返します。 } // キーが root のキーと同じ場合、これが削除されるノードです // 子が 1 つだけあるノード、または子が存在しないノード if (root->left == NULL) { Node* temp = root->右; ルートを削除します。 戻り温度; } else if (root->right == NULL) { Node* temp = root->left; ルートを削除します。 戻り温度; } // 2 つの子を持つノード: 順序の後続ノード (// 右のサブツリー内の最小のもの) を取得します。 Node* succParent = root; ノード* 成功 = ルート->右; while (succ->left != NULL) { succParent = succ; succ = succ->left; } // 順序後続者のコンテンツをこのノードにコピーします。 root->key = succ->key; // 順序後続を削除 if (succParent->left == succ) succParent->left = succ->right; それ以外の場合は、succParent->right = succ->right; 削除成功; ルートを返します。 } // ドライバーコード int main() { /* 以下の BST を作成しましょう 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; ルート = 挿入(ルート, 50); ルート = 挿入(ルート, 30); ルート = 挿入(ルート, 20); ルート = 挿入(ルート, 40); ルート = 挿入(ルート, 70); ルート = 挿入(ルート, 60); ルート = 挿入(ルート, 80); printf('元の BST: '); インオーダー(ルート); printf('
リーフ ノードの削除: 20
'); root = deleteNode(root, 20); printf('リーフ ノードの削除後に BST ツリーが変更されました:
'); インオーダー(ルート); printf('
単一の子を持つノードを削除: 70
'); root = deleteNode(root, 70); printf('単一の子ノードを削除した後に BST ツリーが変更されました:
'); インオーダー(ルート); printf('
両方の子を持つノードを削除: 50
'); root = deleteNode(root, 50); printf('両方の子ノードを削除した後に BST ツリーを変更しました:
'); インオーダー(ルート); 0を返します。 }>> C #include #include struct Node { int key; struct Node *left, *right; }; // A utility function to create a new BST node struct Node* newNode(int item) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->キー = アイテム; 一時->左 = 一時->右 = NULL; 戻り温度; } // BST の順序トラバーサルを行うユーティリティ関数 void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(ルート->右); } } /* 指定されたキーを持つ新しいノードを BST に挿入するユーティリティ関数 */ struct Node* insert(struct Node* node, int key) { /* ツリーが空の場合は、新しいノードを返します */ if (node == NULL) newNode(key) を返します。 /* それ以外の場合は、ツリーを下位に再帰します */ if (key< node->キー) ノード->左 = 挿入(ノード->左, キー); else ノード->右 = 挿入(ノード->右, キー); /* (変更されていない) ノード ポインタを返します */ return node; } /* 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルートを返します */ struct Node* deleteNode(struct Node* root, int k) { // 基本ケース if (root == NULL) return根; // 削除するキーがルートのキーより小さい場合、そのキーは左側のサブツリーにあります if (k< root->key) { root->left = deleteNode(root->left, k); ルートを返します。 } // 削除するキーがルートのキーより大きい場合、そのキーは右のサブツリーにあり、それ以外の場合は if (k> root->key) { root->right = deleteNode(root->right, k ); ルートを返します。 } // キーが root のキーと同じ場合、これが削除されるノードです // 子が 1 つだけあるノード、または子が存在しないノード if (root->left == NULL) { struct Node* temp = root->そうだね。 無料(ルート); 戻り温度; } else if (root->right == NULL) { struct Node* temp = root->left; 無料(ルート); 戻り温度; } // 2 つの子を持つノード: 順序後継者 (右側のサブツリーの最小のもの) を取得します。 struct Node* succParent = root; struct Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->left; } // 順序後続者のコンテンツをこのノードにコピーします。 root->key = succ->key; // 順序後続を削除 if (succParent->left == succ) succParent->left = succ->right; それ以外の場合は、succParent->right = succ->right; 無料(成功); ルートを返します。 } // ドライバコード int main() { /* 以下の BST を作成しましょう 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; ルート = 挿入(ルート, 50); 挿入(ルート、30); 挿入(ルート、20); 挿入(ルート、40); 挿入(ルート、70); 挿入(ルート、60); 挿入(ルート、80); printf('元の BST: '); インオーダー(ルート); printf('
リーフ ノードの削除: 20
'); root = deleteNode(root, 20); printf('リーフ ノードの削除後に BST ツリーが変更されました:
'); インオーダー(ルート); printf('
単一の子を持つノードを削除: 70
'); root = deleteNode(root, 70); printf('単一の子ノードを削除した後に BST ツリーが変更されました:
'); インオーダー(ルート); printf('
両方の子を持つノードを削除: 50
'); root = deleteNode(root, 50); printf('両方の子ノードを削除した後に BST ツリーを変更しました:
'); インオーダー(ルート); 0を返します。 }>> ジャワ class Node { int key; Node left, right; Node(int item) { key = item; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } // A utility function to insert a new node with the given key Node insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) { return new Node(key); } // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>ノード.キー) { ノード.右 = 挿入(ノード.右, キー); } // (変更されていない) ノード ポインタを返します return node; } // BST の順序トラバーサルを行うユーティリティ関数 void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + ' '); inorder(root.right); } } // 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルート ノードを返します deleteNode(Node root, int key) { // 基本ケース if (root == null) { return root; } // 削除するキーがルートのキーより小さい場合、そのキーは左側のサブツリーにあります。 if (key< root.key) { root.left = deleteNode(root.left, key); } // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) { root.right = deleteNode(root.right, key); } // キーが root のキーと同じ場合、これが削除されるノードになります else { // 子が 1 つだけあるノード、または子が存在しないノード if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // 2 つの子を持つノード: 順序の後続者 (右側のサブツリーの最小のもの) を取得します。 root.key = minValue(root.right); // 順序後続を削除 root.right = deleteNode(root.right, root.key); ルートを返します。 int minValue(ノードルート) { int minv = root.key; while (root.left != null) { minv = root.left.key; ルート = root.left; minv を返します。 } // ドライバー コード public static void main(String[] args) { BinaryTree Tree = new BinaryTree(); /* 以下の BST を作成しましょう 50 / 30 70 / / 20 40 60 80 */tree.root =tree.insert(tree.root, 50); ツリー.インサート(ツリー.ルート, 30); ツリー.インサート(ツリー.ルート, 20); ツリー.インサート(ツリー.ルート, 40); ツリー.インサート(ツリー.ルート, 70); ツリー.インサート(ツリー.ルート, 60); ツリー.インサート(ツリー.ルート, 80); System.out.print('元の BST: '); ツリー.inorder(ツリー.ルート); System.out.println(); System.out.println('
リーフ ノードを削除: 20'); ツリー.ルート = ツリー.deleteNode(ツリー.ルート, 20); System.out.print('リーフ ノードの削除後に変更された BST ツリー:
'); ツリー.inorder(ツリー.ルート); System.out.println(); System.out.println('
単一の子を持つノードを削除: 70'); ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 70); System.out.print('単一の子ノードを削除した後に BST ツリーが変更されました:
'); ツリー.inorder(ツリー.ルート); System.out.println(); System.out.println('
両方の子を持つノードを削除: 50'); ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 50); System.out.print('両方の子ノードを削除した後に BST ツリーを変更しました:
'); ツリー.inorder(ツリー.ルート); } }>> Python3 class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None # A utility function to insert a new node with the given key def insert(self, node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = self.insert(node.left, key) elif key>node.key: node.right = self.insert(node.right, key) # (変更されていない) ノード ポインタを返す return node # BST の順序トラバーサルを行うユーティリティ関数 def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルートを返します def deleteNode (self, root, key): # ルートが None の場合の基本ケース: return root # 削除するキーがルートのキーより小さい場合、そのキーは左側のサブツリーにあります。< root.key: root.left = self.deleteNode(root.left, key) # If the key to be deleted is greater than the root's key, then it lies in the right subtree elif key>root.key: root.right = self.deleteNode(root.right, key) # key が root のキーと同じ場合、これは削除されるノードです。それ以外の場合: # 子が 1 つだけあるノード、または子がないノードの場合root.left is None: return root.right elif root.right is None: return root.left # 2 つの子を持つノード: 順序の後継者 (右側のサブツリーの最小のもの) を取得 root.key = self.minValue(root.right) # 後続の順序を削除します root.right = self.deleteNode(root.right, root.key) return root def minValue(self, root): minv = root.key while root.left: minv = root.left.key root = root.left return minv # ドライバーコード if __name__ == '__main__':tree = BinaryTree() # 次の BST を作成しましょう # 50 # / # 30 70 # / / # 20 40 60 80tree.root = ツリー.インサート(ツリー.ルート, 50) ツリー.インサート(ツリー.ルート, 30) ツリー.インサート(ツリー.ルート, 20) ツリー.インサート(ツリー.ルート, 40) ツリー.インサート(ツリー.ルート, 70) )tree.insert(tree.root, 60)tree.insert(tree.root, 80) print('オリジナル BST:', end=' ')tree.inorder(tree.root) print() print ('
リーフ ノードの削除: 20')tree.root =tree.deleteNode(tree.root, 20) print('リーフ ノードの削除後の変更された BST ツリー:')tree.inorder(tree.root) print() print('
単一の子ノードを持つノードを削除: 70') Tree.root =tree.deleteNode(tree.root, 70) print('単一の子ノードを削除した後に変更された BST ツリー:') ツリー。 inorder(tree.root) print() print('
両方の子ノードを持つノードを削除: 50') Tree.root =tree.deleteNode(tree.root, 50) print('両方の子ノードを削除した後の変更された BST ツリー:')tree.inorder(tree.root)>> C# using System; public class Node { public int key; public Node left, right; public Node(int item) { key = item; left = right = null; } } public class BinaryTree { public Node root; // A utility function to insert a new node with the given key public Node Insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) return new Node(key); // Otherwise, recur down the tree if (key < node.key) node.left = Insert(node.left, key); else if (key>ノード.キー) ノード.右 = 挿入(ノード.ライト, キー); // (変更されていない) ノード ポインタを返します return ノード; } // BST の順序トラバーサルを行うユーティリティ関数 public void Inorder(Node root) { if (root != null) { Inorder(root.left); Console.Write(root.key + ' '); Inorder(root.right); } } // 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルート public ノードを返します。 DeleteNode(Node root, int key) { // 基本ケース if (root == null) return root; // 削除するキーがルートのキーより小さい場合、そのキーは左側のサブツリーにあります。 if (key< root.key) root.left = DeleteNode(root.left, key); // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) root.right = DeleteNode(root.right, key); // キーが root のキーと同じである場合、これが削除されるノードになります。 else { // 子が 1 つだけあるノード、または子が存在しないノード if (root.left == null) return root.right; それ以外の場合 (root.right == null) は root.left を返します。 // 2 つの子を持つノード: 順序の後継者 (右側のサブツリーの最小のもの) を取得します。 root.key = MinValue(root.right); // 順序後続を削除 root.right = DeleteNode(root.right, root.key); ルートを返します。 public int MinValue(ノードルート) { int minv = root.key; while (root.left != null) { minv = root.left.key; ルート = root.left; minv を返します。 } // ドライバー コード public static void Main(string[] args) { BinaryTree Tree = new BinaryTree(); /* 以下の BST を作成しましょう 50 / 30 70 / / 20 40 60 80 */tree.root =tree.Insert(tree.root, 50); Tree.Insert(tree.root, 30); Tree.Insert(tree.root, 20); Tree.Insert(tree.root, 40); Tree.Insert(tree.root, 70); Tree.Insert(tree.root, 60); Tree.Insert(tree.root, 80); Console.Write('元の BST: '); ツリー.Inorder(ツリー.ルート); Console.WriteLine(); Console.WriteLine('
リーフ ノードを削除: 20'); ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 20); Console.Write('リーフ ノードの削除後に変更された BST ツリー:
'); ツリー.Inorder(ツリー.ルート); Console.WriteLine(); Console.WriteLine('
単一の子を持つノードを削除: 70'); ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 70); Console.Write('単一の子ノードを削除した後に BST ツリーが変更されました:
'); ツリー.Inorder(ツリー.ルート); Console.WriteLine(); Console.WriteLine('
両方の子を持つノードを削除: 50'); ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 50); Console.Write('両方の子ノードを削除した後に BST ツリーを変更しました:
'); ツリー.Inorder(ツリー.ルート); }>> JavaScript class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class BinaryTree { constructor() { this.root = null; } // A utility function to insert a new node with the given key insert(node, key) { // If the tree is empty, return a new node if (node === null) return new Node(key); // Otherwise, recur down the tree if (key < node.key) node.left = this.insert(node.left, key); else if (key>node.key)node.right = this.insert(node.right, key); // (変更されていない) ノード ポインタを返します return ノード; } // BST の順序トラバーサルを行うユーティリティ関数 inorder(node) { if (node !== null) { this.inorder(node.left); console.log(node.key + ' '); this.inorder(node.right); } } // 二分探索ツリーとキーを指定すると、この関数はキーを削除し、新しいルートを返します deleteNode(root, key) { // 基本ケース if (root === null) return root; // 削除するキーがルートのキーより小さい場合、そのキーは左側のサブツリーにあります。 if (key< root.key) root.left = this.deleteNode(root.left, key); // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) root.right = this.deleteNode(root.right, key); // キーが root のキーと同じである場合、これが削除されるノードになります。 else { // 子が 1 つだけあるノード、または子が存在しないノード if (root.left === null) return root.right; それ以外の場合 (root.right === null) は root.left を返します。 // 2 つの子を持つノード: 順序の後継者 (右側のサブツリーの最小のもの) を取得します。 root.key = this.minValue(root.right); // 順序後続を削除 root.right = this.deleteNode(root.right, root.key); ルートを返します。 minValue(node) { minv = node.key; } while (node.left !== null) { minv = node.left.key; ノード = ノード.左; minv を返します。 } } // ドライバー コード let Tree = new BinaryTree(); /* 以下の BST を作成しましょう 50 / 30 70 / / 20 40 60 80 */tree.root =tree.insert(tree.root, 50);ツリー.インサート(ツリー.ルート, 30);ツリー.インサート(ツリー.ルート, 20);ツリー.インサート(ツリー.ルート, 40);ツリー.インサート(ツリー.ルート, 70);ツリー.インサート(ツリー.ルート, 60);ツリー.インサート(ツリー.ルート, 80); console.log('元の BST:');ツリー.inorder(ツリー.ルート); console.log('
リーフ ノードの削除: 20');ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 20); console.log('リーフ ノードの削除後に変更された BST ツリー:');ツリー.inorder(ツリー.ルート); console.log('
単一の子を持つノードを削除: 70');ツリー.ルート = ツリー.削除ノード(ツリー.ルート, 70); console.log('単一の子ノードを削除した後に変更された BST ツリー:');ツリー.inorder(ツリー.ルート); console.log('
両方の子を持つノードを削除: 50');ツリー.ルート = ツリー.deleteNode(ツリー.ルート, 50); console.log('両方の子ノードを削除した後に変更された BST ツリー:');ツリー.inorder(ツリー.ルート);>> 出力
Original BST: 20 30 40 50 60 70 Delete a Leaf Node: 20 Modified BST tree after deleting Leaf Node: 30 40 50 60 70 Delete Node with single child: 70 Modified BST tree after deleting single child No...>
時間計算量: O(h)、ここで h は BST の高さです。
補助スペース: の上）。
関連リンク：