حذف عنصر از درخت جستجوی دودویی — به زبان ساده

۱۰۴۹ بازدید
آخرین به‌روزرسانی: ۱۸ اردیبهشت ۱۴۰۲
زمان مطالعه: ۱۱ دقیقه
دانلود PDF مقاله
حذف عنصر از درخت جستجوی دودویی — به زبان سادهحذف عنصر از درخت جستجوی دودویی — به زبان ساده

در این مطلب، روش حذف عنصر از درخت جستجوی دودویی بیان شده است. فرض می‌شود یک درخت جستجوی دودویی وجود دارد. هنگامی که یک «گره» (Node) از این درخت حذف می‌شود، سه احتمال وجود دارد.

997696

۱. گره حذف شده، برگ است. به سادگی می‌توان این گره را از درخت حذف کرد.

              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

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *