عملیات در درخت جستجوی دودویی: جستجو و درج — به زبان ساده

۱۱۴۲ بازدید
آخرین به‌روزرسانی: ۲۰ خرداد ۱۴۰۳
زمان مطالعه: ۶ دقیقه
عملیات در درخت جستجوی دودویی: جستجو و درج — به زبان ساده

در این مطلب، تعریف «درخت جستجوی دودویی» (Binary Search Tree | BST) بیان و عملیات در درخت جستجوی دودویی شامل جستجو و درج آموزش داده شده و همچنین، پیاده‌سازی‌های مربوط به این اعمال، در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و «پایتون» (Python) انجام شده است. تعریف درخت جستجوی دودویی در ادامه آمده است. درخت جستجوی دودویی، یک ساختار درختی مبتنی بر گره و دارای مشخصات زیر است:

997696
  • زیردرخت سمت چپ یک گره تنها حاوی گره‌هایی با کلیدهای کمتر از کلید گره است.
  • زیردرخت سمت راست یک گره تنها حاوی گره‌هایی با کلیدهای بزرگ‌تر از کلید گره است.
  • هر یک از زیر درخت‌های چپ و راست نیز باید یک درخت جستجوی دودویی باشند.
  • هیچ گره تکراری نباید وجود داشته باشد.

عملیات در درخت جستجوی دودویی: جستجو و درج

خصوصیات بیان شده در بالا برای درخت جستجوی دودویی، ترتیبی را در میان کلیدها پدید می‌آورد، بنابراین عملیاتی مانند جستجو در آن به سرعت انجام می‌شوند. اگر هیچ ترتیبی وجود نداشت، ممکن است نیاز باشد هر کلید را طی جستجو با مقدار داده شده مقایسه کرد.

جستجوی یک کلید در درخت جستجوی دودویی

برای جستجوی یک کلید در درخت جستجوی دودویی، ابتدا باید آن را با ریشه مقایسه کرد، اگر کلید در ریشه نمایش داده شد، ریشه بازگردانده می‌شود. اگر یک کلید بزرگ‌تر از کلید ریشه باشد، بازگشت برای زیردرخت سمت راست یک گره انجام می‌شود. در غیر این صورت بازگشت برای زیردرخت سمت چپ انجام می‌شود.

جستجو در درخت جستجوی دودویی در ++C

1// C function to search a given key in a given BST 
2struct node* search(struct node* root, int key) 
3{ 
4    // Base Cases: root is null or key is present at root 
5    if (root == NULL || root->key == key) 
6       return root; 
7     
8    // Key is greater than root's key 
9    if (root->key < key) 
10       return search(root->right, key); 
11  
12    // Key is smaller than root's key 
13    return search(root->left, key); 
14}

جستجو در درخت جستجوی دودویی در پایتون

1# A utility function to search a given key in BST 
2def search(root,key): 
3      
4    # Base Cases: root is null or key is present at root 
5    if root is None or root.val == key: 
6        return root 
7  
8    # Key is greater than root's key 
9    if root.val < key: 
10        return search(root.right,key) 
11    
12    # Key is smaller than root's key 
13    return search(root.left,key) 
14  
15# This code is contributed by Bhavya Jain

جستجو در درخت جستجوی دودویی در جاوا

1// A utility function to search a given key in BST 
2public Node search(Node root, int key) 
3{ 
4    // Base Cases: root is null or key is present at root 
5    if (root==null || root.key==key) 
6        return root; 
7  
8    // val is greater than root's key 
9    if (root.key > key) 
10        return search(root.left, key); 
11  
12    // val is less than root's key 
13    return search(root.right, key); 
14}

مثال:

اکنون، مقدار ۶ در درختی که در ادامه آمده است جستجو می‌شود. مراحل انجام این کار، در ادامه بیان شده‌اند.

  1. از ریشه شروع کن.
  2. عنصر درج شده را با ریشه مقایسه کن. اگر کمتر از ریشه بود، برای چپ بازگشت کن، در غیر این صورت، برای راست بازگشت کن.
  3. اگر عنصری که باید جستجو شود در هر جایی یافت شد، مقدار true و در غیر این صورت، مقدار false را بازگردان.

عملیات در درخت جستجوی دودویی: جستجو و درج

درج کلید در درخت جستجوی دودویی

در درخت جستجوی دودویی، یک کلید جدید همیشه در برگ درج می‌شود. کار با جستجوی کلید از ریشه آغاز می‌شود و تا هنگامی که گره برگ ساخته شود ادامه دارد.

هنگامی که یک گره برگ پیدا شد، گره جدید به عنوان فرزند گره برگ اضافه می‌شود.

         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

درج کلید در درخت جستجوی دودویی در ++C

1// C program to demonstrate insert 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 \n", 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 if (key > node->key) 
41        node->right = insert(node->right, key);    
42  
43    /* return the (unchanged) node pointer */
44    return node; 
45} 
46   
47// Driver Program to test above functions 
48int main() 
49{ 
50    /* Let us create following BST 
51              50 
52           /     \ 
53          30      70 
54         /  \    /  \ 
55       20   40  60   80 */
56    struct node *root = NULL; 
57    root = insert(root, 50); 
58    insert(root, 30); 
59    insert(root, 20); 
60    insert(root, 40); 
61    insert(root, 70); 
62    insert(root, 60); 
63    insert(root, 80); 
64   
65    // print inoder traversal of the BST 
66    inorder(root); 
67   
68    return 0; 
69}

درج کلید در درخت جستجوی دودویی در پایتون

1# Python program to demonstrate insert operation in binary search tree  
2  
3# A utility class that represents an individual node in a BST 
4class Node: 
5    def __init__(self,key): 
6        self.left = None
7        self.right = None
8        self.val = key 
9  
10# A utility function to insert a new node with the given key 
11def insert(root,node): 
12    if root is None: 
13        root = node 
14    else: 
15        if root.val < node.val: 
16            if root.right is None: 
17                root.right = node 
18            else: 
19                insert(root.right, node) 
20        else: 
21            if root.left is None: 
22                root.left = node 
23            else: 
24                insert(root.left, node) 
25  
26# A utility function to do inorder tree traversal 
27def inorder(root): 
28    if root: 
29        inorder(root.left) 
30        print(root.val) 
31        inorder(root.right) 
32  
33  
34# Driver program to test the above functions 
35# Let us create the following BST 
36#      50 
37#    /      \ 
38#   30     70 
39#   / \    / \ 
40#  20 40  60 80 
41r = Node(50) 
42insert(r,Node(30)) 
43insert(r,Node(20)) 
44insert(r,Node(40)) 
45insert(r,Node(70)) 
46insert(r,Node(60)) 
47insert(r,Node(80)) 
48  
49# Print inoder traversal of the BST 
50inorder(r) 
51  
52# This code is contributed by Bhavya Jain

درج کلید در درخت جستجوی دودویی در جاوا

1// Java program to demonstrate insert 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        int key; 
7        Node left, right; 
8  
9        public Node(int item) { 
10            key = item; 
11            left = right = null; 
12        } 
13    } 
14  
15    // Root of BST 
16    Node root; 
17  
18    // Constructor 
19    BinarySearchTree() {  
20        root = null;  
21    } 
22  
23    // This method mainly calls insertRec() 
24    void insert(int key) { 
25       root = insertRec(root, key); 
26    } 
27      
28    /* A recursive function to insert a new key in BST */
29    Node insertRec(Node root, int key) { 
30  
31        /* If the tree is empty, return a new node */
32        if (root == null) { 
33            root = new Node(key); 
34            return root; 
35        } 
36  
37        /* Otherwise, recur down the tree */
38        if (key < root.key) 
39            root.left = insertRec(root.left, key); 
40        else if (key > root.key) 
41            root.right = insertRec(root.right, key); 
42  
43        /* return the (unchanged) node pointer */
44        return root; 
45    } 
46  
47    // This method mainly calls InorderRec() 
48    void inorder()  { 
49       inorderRec(root); 
50    } 
51  
52    // A utility function to do inorder traversal of BST 
53    void inorderRec(Node root) { 
54        if (root != null) { 
55            inorderRec(root.left); 
56            System.out.println(root.key); 
57            inorderRec(root.right); 
58        } 
59    } 
60  
61    // Driver Program to test above functions 
62    public static void main(String[] args) { 
63        BinarySearchTree tree = new BinarySearchTree(); 
64  
65        /* Let us create following BST 
66              50 
67           /     \ 
68          30      70 
69         /  \    /  \ 
70       20   40  60   80 */
71        tree.insert(50); 
72        tree.insert(30); 
73        tree.insert(20); 
74        tree.insert(40); 
75        tree.insert(70); 
76        tree.insert(60); 
77        tree.insert(80); 
78  
79        // print inorder traversal of the BST 
80        tree.inorder(); 
81    } 
82} 
83// This code is contributed by Ankur Narain Verma

خروجی قطعه کدهای بالا، به صورت زیر است.

20
30
40
50
60
70
80

مثال:

در ادامه، مثالی ارائه شده که طی آن، عدد ۲ در درختی که تصویر آن در زیر آمده، درج می‌شود. مراحل انجام این کار، در زیر بیان شده است.

  1. از ریشه شروع کن.
  2. عنصر درج شده را با ریشه مقایسه کن، اگر از ریشه کمتر بود، برای چپ بازگشت کن، در غیر این صورت، برای راست بازگشت کن.
  3. پس از رسیدن به پایان، آن گره را (اگر کمتر از مقدار کنونی بود) در چپ و در غیر این صورت، در راست قرار بده.

عملیات در درخت جستجوی دودویی: جستجو و درج

پیچیدگی زمانی جستجو و درج در درخت جستجوی دودویی

پیچیدگی زمانی در بدترین حالت از عملیات جستجو و درج، برابر با (O(h است که در آن، h ارتفاع درخت جستجوی دودویی محسوب می‌شود. در بدترین حالت، ممکن است نیاز باشد از ریشه به عمیق‌ترین گره برگ پیمایش شود. ارتفاع درخت دارای چولگی ممکن است برابر با n و پیچیدگی زمانی جستجو و درج ممکن است از درجه (O(n باشد.

نکاتی جالب پیرامون درخت جستجوی دودویی

  • پیمایش مرتب درخت جستجوی دودویی همیشه یک خروجی مرتب شده تولید می‌کند.
  • یک درخت جستجوی دودویی را می‌توان با پیمایش پیش‌ترتیب، پس‌ترتیب و یا پیمایش مرتبه سطحی ساخت. توجه به این نکته نیز لازم است که همیشه می‌توان پیمایش مرتب را با مرتب‌سازی تنها پیمایش داده شده به دست آورد.
  • تعداد درخت‌های جستجوی دودویی با n کلید متمایز، یک «عدد کاتالان» (Catalan Number) است.

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

^^

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

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