حذف عنصر از درخت جستجوی دودویی — به زبان ساده
در این مطلب، روش حذف عنصر از درخت جستجوی دودویی بیان شده است. فرض میشود یک درخت جستجوی دودویی وجود دارد. هنگامی که یک «گره» (Node) از این درخت حذف میشود، سه احتمال وجود دارد.
۱. گره حذف شده، برگ است. به سادگی میتوان این گره را از درخت حذف کرد.
50 50 / \ delete(20) / \ 30 70 ---------> 30 70 / \ / \ \ / \ 20 40 60 80 40 60 80
۲. گره حذف شده، تنها یک فرزند دارد. فرزند گره در جای خود گره کپی و فرزند آن حذف میشود.
50 50 / \ delete(30) / \ 30 70 ---------> 40 70 \ / \ / \ 40 60 80 60 80
۳. گرهای که باید حذف شود، دارای دو فرزند است. به ترتیب، جانشین گره باید پیدا شود. محتوای جانشین به ترتیب، در گره کپی و جانشین به ترتیب حذف میشود. توجه به این نکته لازم است که جد به ترتیب نیز قابل استفاده است.
50 60 / \ delete(50) / \ 40 70 ---------> 40 70 / \ \ 60 80 80
مساله مهمی که باید به آن توجه داشت این است که جانشین مرتب تنها هنگامی مورد نیاز است که فرزند راست خالی نباشد. در این شرایط خاص، جانشین مرتب را میتوان با پیدا کردن کمترین مقدار در فرزند سمت راست گره به دست آورد.
حذف عنصر از درخت جستجوی دودویی در ++C
1// C program to demonstrate delete operation in binary search tree
2#include<stdio.h>
3#include<stdlib.h>
4
5struct node
6{
7 int key;
8 struct node *left, *right;
9};
10
11// A utility function to create a new BST node
12struct node *newNode(int item)
13{
14 struct node *temp = (struct node *)malloc(sizeof(struct node));
15 temp->key = item;
16 temp->left = temp->right = NULL;
17 return temp;
18}
19
20// A utility function to do inorder traversal of BST
21void inorder(struct node *root)
22{
23 if (root != NULL)
24 {
25 inorder(root->left);
26 printf("%d ", root->key);
27 inorder(root->right);
28 }
29}
30
31/* A utility function to insert a new node with given key in BST */
32struct node* insert(struct node* node, int key)
33{
34 /* If the tree is empty, return a new node */
35 if (node == NULL) return newNode(key);
36
37 /* Otherwise, recur down the tree */
38 if (key < node->key)
39 node->left = insert(node->left, key);
40 else
41 node->right = insert(node->right, key);
42
43 /* return the (unchanged) node pointer */
44 return node;
45}
46
47/* Given a non-empty binary search tree, return the node with minimum
48 key value found in that tree. Note that the entire tree does not
49 need to be searched. */
50struct node * minValueNode(struct node* node)
51{
52 struct node* current = node;
53
54 /* loop down to find the leftmost leaf */
55 while (current && current->left != NULL)
56 current = current->left;
57
58 return current;
59}
60
61/* Given a binary search tree and a key, this function deletes the key
62 and returns the new root */
63struct node* deleteNode(struct node* root, int key)
64{
65 // base case
66 if (root == NULL) return root;
67
68 // If the key to be deleted is smaller than the root's key,
69 // then it lies in left subtree
70 if (key < root->key)
71 root->left = deleteNode(root->left, key);
72
73 // If the key to be deleted is greater than the root's key,
74 // then it lies in right subtree
75 else if (key > root->key)
76 root->right = deleteNode(root->right, key);
77
78 // if key is same as root's key, then This is the node
79 // to be deleted
80 else
81 {
82 // node with only one child or no child
83 if (root->left == NULL)
84 {
85 struct node *temp = root->right;
86 free(root);
87 return temp;
88 }
89 else if (root->right == NULL)
90 {
91 struct node *temp = root->left;
92 free(root);
93 return temp;
94 }
95
96 // node with two children: Get the inorder successor (smallest
97 // in the right subtree)
98 struct node* temp = minValueNode(root->right);
99
100 // Copy the inorder successor's content to this node
101 root->key = temp->key;
102
103 // Delete the inorder successor
104 root->right = deleteNode(root->right, temp->key);
105 }
106 return root;
107}
108
109// Driver Program to test above functions
110int main()
111{
112 /* Let us create following BST
113 50
114 / \
115 30 70
116 / \ / \
117 20 40 60 80 */
118 struct node *root = NULL;
119 root = insert(root, 50);
120 root = insert(root, 30);
121 root = insert(root, 20);
122 root = insert(root, 40);
123 root = insert(root, 70);
124 root = insert(root, 60);
125 root = insert(root, 80);
126
127 printf("Inorder traversal of the given tree \n");
128 inorder(root);
129
130 printf("\nDelete 20\n");
131 root = deleteNode(root, 20);
132 printf("Inorder traversal of the modified tree \n");
133 inorder(root);
134
135 printf("\nDelete 30\n");
136 root = deleteNode(root, 30);
137 printf("Inorder traversal of the modified tree \n");
138 inorder(root);
139
140 printf("\nDelete 50\n");
141 root = deleteNode(root, 50);
142 printf("Inorder traversal of the modified tree \n");
143 inorder(root);
144
145 return 0;
146}
حذف عنصر از درخت جستجوی دودویی در جاوا
1// Java program to demonstrate delete operation in binary search tree
2class BinarySearchTree
3{
4 /* Class containing left and right child of current node and key value*/
5 class Node
6 {
7 int key;
8 Node left, right;
9
10 public Node(int item)
11 {
12 key = item;
13 left = right = null;
14 }
15 }
16
17 // Root of BST
18 Node root;
19
20 // Constructor
21 BinarySearchTree()
22 {
23 root = null;
24 }
25
26 // This method mainly calls deleteRec()
27 void deleteKey(int key)
28 {
29 root = deleteRec(root, key);
30 }
31
32 /* A recursive function to insert a new key in BST */
33 Node deleteRec(Node root, int key)
34 {
35 /* Base Case: If the tree is empty */
36 if (root == null) return root;
37
38 /* Otherwise, recur down the tree */
39 if (key < root.key)
40 root.left = deleteRec(root.left, key);
41 else if (key > root.key)
42 root.right = deleteRec(root.right, key);
43
44 // if key is same as root's key, then This is the node
45 // to be deleted
46 else
47 {
48 // node with only one child or no child
49 if (root.left == null)
50 return root.right;
51 else if (root.right == null)
52 return root.left;
53
54 // node with two children: Get the inorder successor (smallest
55 // in the right subtree)
56 root.key = minValue(root.right);
57
58 // Delete the inorder successor
59 root.right = deleteRec(root.right, root.key);
60 }
61
62 return root;
63 }
64
65 int minValue(Node root)
66 {
67 int minv = root.key;
68 while (root.left != null)
69 {
70 minv = root.left.key;
71 root = root.left;
72 }
73 return minv;
74 }
75
76 // This method mainly calls insertRec()
77 void insert(int key)
78 {
79 root = insertRec(root, key);
80 }
81
82 /* A recursive function to insert a new key in BST */
83 Node insertRec(Node root, int key)
84 {
85
86 /* If the tree is empty, return a new node */
87 if (root == null)
88 {
89 root = new Node(key);
90 return root;
91 }
92
93 /* Otherwise, recur down the tree */
94 if (key < root.key)
95 root.left = insertRec(root.left, key);
96 else if (key > root.key)
97 root.right = insertRec(root.right, key);
98
99 /* return the (unchanged) node pointer */
100 return root;
101 }
102
103 // This method mainly calls InorderRec()
104 void inorder()
105 {
106 inorderRec(root);
107 }
108
109 // A utility function to do inorder traversal of BST
110 void inorderRec(Node root)
111 {
112 if (root != null)
113 {
114 inorderRec(root.left);
115 System.out.print(root.key + " ");
116 inorderRec(root.right);
117 }
118 }
119
120 // Driver Program to test above functions
121 public static void main(String[] args)
122 {
123 BinarySearchTree tree = new BinarySearchTree();
124
125 /* Let us create following BST
126 50
127 / \
128 30 70
129 / \ / \
130 20 40 60 80 */
131 tree.insert(50);
132 tree.insert(30);
133 tree.insert(20);
134 tree.insert(40);
135 tree.insert(70);
136 tree.insert(60);
137 tree.insert(80);
138
139 System.out.println("Inorder traversal of the given tree");
140 tree.inorder();
141
142 System.out.println("\nDelete 20");
143 tree.deleteKey(20);
144 System.out.println("Inorder traversal of the modified tree");
145 tree.inorder();
146
147 System.out.println("\nDelete 30");
148 tree.deleteKey(30);
149 System.out.println("Inorder traversal of the modified tree");
150 tree.inorder();
151
152 System.out.println("\nDelete 50");
153 tree.deleteKey(50);
154 System.out.println("Inorder traversal of the modified tree");
155 tree.inorder();
156 }
157}
حذف عنصر از درخت جستجوی دودویی در پایتون
1# Python program to demonstrate delete operation
2# in binary search tree
3
4# A Binary Tree Node
5class Node:
6
7 # Constructor to create a new node
8 def __init__(self, key):
9 self.key = key
10 self.left = None
11 self.right = None
12
13
14# A utility function to do inorder traversal of BST
15def inorder(root):
16 if root is not None:
17 inorder(root.left)
18 print root.key,
19 inorder(root.right)
20
21
22# A utility function to insert a new node with given key in BST
23def insert( node, key):
24
25 # If the tree is empty, return a new node
26 if node is None:
27 return Node(key)
28
29 # Otherwise recur down the tree
30 if key < node.key:
31 node.left = insert(node.left, key)
32 else:
33 node.right = insert(node.right, key)
34
35 # return the (unchanged) node pointer
36 return node
37
38# Given a non-empty binary search tree, return the node
39# with minum key value found in that tree. Note that the
40# entire tree does not need to be searched
41def minValueNode( node):
42 current = node
43
44 # loop down to find the leftmost leaf
45 while(current.left is not None):
46 current = current.left
47
48 return current
49
50# Given a binary search tree and a key, this function
51# delete the key and returns the new root
52def deleteNode(root, key):
53
54 # Base Case
55 if root is None:
56 return root
57
58 # If the key to be deleted is smaller than the root's
59 # key then it lies in left subtree
60 if key < root.key:
61 root.left = deleteNode(root.left, key)
62
63 # If the kye to be delete is greater than the root's key
64 # then it lies in right subtree
65 elif(key > root.key):
66 root.right = deleteNode(root.right, key)
67
68 # If key is same as root's key, then this is the node
69 # to be deleted
70 else:
71
72 # Node with only one child or no child
73 if root.left is None :
74 temp = root.right
75 root = None
76 return temp
77
78 elif root.right is None :
79 temp = root.left
80 root = None
81 return temp
82
83 # Node with two children: Get the inorder successor
84 # (smallest in the right subtree)
85 temp = minValueNode(root.right)
86
87 # Copy the inorder successor's content to this node
88 root.key = temp.key
89
90 # Delete the inorder successor
91 root.right = deleteNode(root.right , temp.key)
92
93
94 return root
95
96# Driver program to test above functions
97""" Let us create following BST
98 50
99 / \
100 30 70
101 / \ / \
102 20 40 60 80 """
103
104root = None
105root = insert(root, 50)
106root = insert(root, 30)
107root = insert(root, 20)
108root = insert(root, 40)
109root = insert(root, 70)
110root = insert(root, 60)
111root = insert(root, 80)
112
113print "Inorder traversal of the given tree"
114inorder(root)
115
116print "\nDelete 20"
117root = deleteNode(root, 20)
118print "Inorder traversal of the modified tree"
119inorder(root)
120
121print "\nDelete 30"
122root = deleteNode(root, 30)
123print "Inorder traversal of the modified tree"
124inorder(root)
125
126print "\nDelete 50"
127root = deleteNode(root, 50)
128print "Inorder traversal of the modified tree"
129inorder(root)
130
131# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
حذف عنصر از درخت جستجوی دودویی در #C
1// C# program to demonstrate delete
2// operation in binary search tree
3using System;
4
5public class BinarySearchTree
6{
7 /* Class containing left and right
8 child of current node and key value*/
9 class Node
10 {
11 public int key;
12 public Node left, right;
13
14 public Node(int item)
15 {
16 key = item;
17 left = right = null;
18 }
19 }
20
21 // Root of BST
22 Node root;
23
24 // Constructor
25 BinarySearchTree()
26 {
27 root = null;
28 }
29
30 // This method mainly calls deleteRec()
31 void deleteKey(int key)
32 {
33 root = deleteRec(root, key);
34 }
35
36 /* A recursive function to insert a new key in BST */
37 Node deleteRec(Node root, int key)
38 {
39 /* Base Case: If the tree is empty */
40 if (root == null) return root;
41
42 /* Otherwise, recur down the tree */
43 if (key < root.key)
44 root.left = deleteRec(root.left, key);
45 else if (key > root.key)
46 root.right = deleteRec(root.right, key);
47
48 // if key is same as root's key, then This is the node
49 // to be deleted
50 else
51 {
52 // node with only one child or no child
53 if (root.left == null)
54 return root.right;
55 else if (root.right == null)
56 return root.left;
57
58 // node with two children: Get the
59 // inorder successor (smallest
60 // in the right subtree)
61 root.key = minValue(root.right);
62
63 // Delete the inorder successor
64 root.right = deleteRec(root.right, root.key);
65 }
66 return root;
67 }
68
69 int minValue(Node root)
70 {
71 int minv = root.key;
72 while (root.left != null)
73 {
74 minv = root.left.key;
75 root = root.left;
76 }
77 return minv;
78 }
79
80 // This method mainly calls insertRec()
81 void insert(int key)
82 {
83 root = insertRec(root, key);
84 }
85
86 /* A recursive function to insert a new key in BST */
87 Node insertRec(Node root, int key)
88 {
89
90 /* If the tree is empty, return a new node */
91 if (root == null)
92 {
93 root = new Node(key);
94 return root;
95 }
96
97 /* Otherwise, recur down the tree */
98 if (key < root.key)
99 root.left = insertRec(root.left, key);
100 else if (key > root.key)
101 root.right = insertRec(root.right, key);
102
103 /* return the (unchanged) node pointer */
104 return root;
105 }
106
107 // This method mainly calls InorderRec()
108 void inorder()
109 {
110 inorderRec(root);
111 }
112
113 // A utility function to do inorder traversal of BST
114 void inorderRec(Node root)
115 {
116 if (root != null)
117 {
118 inorderRec(root.left);
119 Console.Write(root.key + " ");
120 inorderRec(root.right);
121 }
122 }
123
124 // Driver code
125 public static void Main(String[] args)
126 {
127 BinarySearchTree tree = new BinarySearchTree();
128
129 /* Let us create following BST
130 50
131 / \
132 30 70
133 / \ / \
134 20 40 60 80 */
135 tree.insert(50);
136 tree.insert(30);
137 tree.insert(20);
138 tree.insert(40);
139 tree.insert(70);
140 tree.insert(60);
141 tree.insert(80);
142
143 Console.WriteLine("Inorder traversal of the given tree");
144 tree.inorder();
145
146 Console.WriteLine("\nDelete 20");
147 tree.deleteKey(20);
148 Console.WriteLine("Inorder traversal of the modified tree");
149 tree.inorder();
150
151 Console.WriteLine("\nDelete 30");
152 tree.deleteKey(30);
153 Console.WriteLine("Inorder traversal of the modified tree");
154 tree.inorder();
155
156 Console.WriteLine("\nDelete 50");
157 tree.deleteKey(50);
158 Console.WriteLine("Inorder traversal of the modified tree");
159 tree.inorder();
160 }
161}
162
163// This code has been contributed
164// by PrinciRaj1992
خروجی قطعه کدهای بالا به صورت زیر است.
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
پیچیدگی زمانی
پیچیدگی زمانی بدترین حالت از عملیات حذف برابر با (O(h است که در آن، h ارتفاع درخت جستجوی دودویی محسوب میشود. در بدترین حالت، ممکن است نیاز باشد از ریشه به عمیقترین گره برگ رفت. ارتفاع درخت دارای چولگی ممکن است n و پیچیدگی زمانی عملیات حذف ممکن است (O(n باشد.
روش دوم حذف یک گره از درخت جستجوی دودویی
اکنون، روش بیان شده در بالا بهینهسازی میشود. در کد بازگشتی بالا، به صورت بازگشتی ()delete برای جانشین فراخوانی میشد. میتوان از فراخوانی بازگشتی با نگهداری گره والد جانشین اجتناب کرد، بنابراین میتوان جانشین را با NULL کردن فرزند والد به سادگی حذف کرد. جانشین همیشه یک گره فرزند است.
حذف عنصر از درخت جستجوی دودویی در ++C
1// C++ program to implement optimized delete in BST.
2#include <bits/stdc++.h>
3using namespace std;
4
5struct Node {
6 int key;
7 struct Node *left, *right;
8};
9
10// A utility function to create a new BST node
11Node* newNode(int item)
12{
13 Node* temp = new Node;
14 temp->key = item;
15 temp->left = temp->right = NULL;
16 return temp;
17}
18
19// A utility function to do inorder traversal of BST
20void inorder(Node* root)
21{
22 if (root != NULL) {
23 inorder(root->left);
24 printf("%d ", root->key);
25 inorder(root->right);
26 }
27}
28
29/* A utility function to insert a new node with given key in BST */
30Node* insert(Node* node, int key)
31{
32 /* If the tree is empty, return a new node */
33 if (node == NULL)
34 return newNode(key);
35
36 /* Otherwise, recur down the tree */
37 if (key < node->key)
38 node->left = insert(node->left, key);
39 else
40 node->right = insert(node->right, key);
41
42 /* return the (unchanged) node pointer */
43 return node;
44}
45
46/* Given a binary search tree and a key, this function deletes the key
47 and returns the new root */
48Node* deleteNode(Node* root, int k)
49{
50 // Base case
51 if (root == NULL)
52 return root;
53
54 // Recursive calls for ancestors of
55 // node to be deleted
56 if (root->key > k) {
57 root->left = deleteNode(root->left, k);
58 return root;
59 }
60 else if (root->key < k) {
61 root->right = deleteNode(root->right, k);
62 return root;
63 }
64
65 // We reach here when root is the node
66 // to be deleted.
67
68 // If one of the children is empty
69 if (root->left == NULL) {
70 Node* temp = root->right;
71 delete root;
72 return temp;
73 }
74 else if (root->right == NULL) {
75 Node* temp = root->left;
76 delete root;
77 return temp;
78 }
79
80 // If both children exist
81 else {
82
83 Node* succParent = root->right;
84
85 // Find successor
86 Node *succ = root->right;
87 while (succ->left != NULL) {
88 succParent = succ;
89 succ = succ->left;
90 }
91
92 // Delete successor. Since successor
93 // is always left child of its parent
94 // we can safely make successor's right
95 // right child as left of its parent.
96 succParent->left = succ->right;
97
98 // Copy Successor Data to root
99 root->key = succ->key;
100
101 // Delete Successor and return root
102 delete succ;
103 return root;
104 }
105}
106
107// Driver Program to test above functions
108int main()
109{
110 /* Let us create following BST
111 50
112 / \
113 30 70
114 / \ / \
115 20 40 60 80 */
116 Node* root = NULL;
117 root = insert(root, 50);
118 root = insert(root, 30);
119 root = insert(root, 20);
120 root = insert(root, 40);
121 root = insert(root, 70);
122 root = insert(root, 60);
123 root = insert(root, 80);
124
125 printf("Inorder traversal of the given tree \n");
126 inorder(root);
127
128 printf("\nDelete 20\n");
129 root = deleteNode(root, 20);
130 printf("Inorder traversal of the modified tree \n");
131 inorder(root);
132
133 printf("\nDelete 30\n");
134 root = deleteNode(root, 30);
135 printf("Inorder traversal of the modified tree \n");
136 inorder(root);
137
138 printf("\nDelete 50\n");
139 root = deleteNode(root, 50);
140 printf("Inorder traversal of the modified tree \n");
141 inorder(root);
142
143 return 0;
144}
خروجی قطعه کد بالا به صورت زیر است.
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- برنامه تشخیص اعداد اول در پایتون — به زبان ساده
- برنامه تجزیه عدد به عوامل اول آن — به زبان ساده
- حل مساله رنگآمیزی گراف با الگوریتم پس گرد — به زبان ساده
^^