مجموعه آموزشی پی استور - https://programstore.ir

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

مفهوم درخت در نظریه گراف ها، نشان دهنده گره‌هایی است که به وسیله یال‌ها یا لبه ها به هم متصل شده‌اند. ما در این نوشته در مورد درخت‌های دودویی (باینری) یا درخت‌های جستجوی دودویی ( Binary Search Tree [1] ) به اختصار BST صحبت  خواهیم کرد. درخت دودویی نوع خاصی از ساختمان داده [2] است که برای ذخیره‌سازی داده مورد استفاده قرار می‌گیرد.

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

یک درخت دودویی شرایط خاصی دارد که در آن هر گره در حالت ماگزیمم دو فرزند دارد. درخت جستجوی دودوی یک ساختار داده مبتنی بر گره است که دارای خواص زیر است:

مثال درخت جستجوی دودویی

عملیاتی که می توان در درخت دودویی انجام داد شامل جستجو Search، اضافه کردن یا درج Insertion و حذف Delete خواهد بود. که در ادامه این سه عملیات تشریح می شوند.

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

برای پیدا کردن گرهی با مقدار خاص در درخت، ابتدا باید از ریشه درخت شروع کنیم. اگر ریشه تهی باشد، درخت فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت، key را با مقدار گره ریشه مقایسه می‌کنیم، اگر برابر بودند، جستجو موفق است و گره ریشه همان گره مورد نظر است. در غیر این صورت، دو حالت پیش خواهد آمد:

  1. key از گره ریشه کوچکتر است. در این حالت، هیچ عنصری در زیردرخت سمت راست وجود ندارد که مقدار کلید آن برابر با key باشد؛ بنابراین جستجو باید در زیردرخت سمت چپ ادامه یابد.
  2. key بزرگتر از گره ریشه است. در این حالت، هیچ عنصری در زیردرخت سمت چپ وجود ندارد که مقدار کلید آن برابر با key باشد؛ بنابراین جستجو باید در زیردرخت سمت راست ادامه یابد.

بسته به حالت 1 و 2، زیردرخت سمت چپ یا زیردرخت سمت راست را با استفاده از الگوریتم بالا جستجو می‌کنیم. عمل جستجو در درخت جستجوی دودویی، از مرتبه O(h)‎ است که در آن h ارتفاع درخت است. چرا که حداکثر باید به میزان عمق درخت، به طرف پایین حرکت کنیم. برای مثال عدد 6 را می خواهیم در درخت بالا جستجو کنیم. برای این کار عملیات زیر را باید انجام داد:

  1. از ریشه شروع کنید (وضعیت 6 را با گره ریشه؟ کوچکتر است پس عدد در زیر دخت سمت چپ است )
  2. عدد 6 را با ریشه زیر درخت سمت چپ مقایسه کنید. (بزرگتر است پس عدد در زیر دخت سمت راست است )
  3. عدد 6 را با ریشه زیر درخت سمت راست مقایسه کنید. (برابر است پس پیدا شد)
// C function to search a given key in a given BST 
struct node* search(struct node* root, int key) 
{ 
    // Base Cases: root is null or key is present at root 
    if (root == NULL || root->key == key) 
       return root; 
     
    // Key is greater than root's key 
    if (root->key < key) 
       return search(root->right, key); 
  
    // Key is smaller than root's key 
    return search(root->left, key); 
}

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

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

Insertion of a key

کد عملیات درج بصورت زیر خواهد بود.

struct node* insert(struct node* node, int key) 
{ 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    
  
    /* return the (unchanged) node pointer */
    return node; 
}

حذف از درخت دودویی

برای حذف یک عنصر از درخت دودویی ابتدا باید بررسی شود که عنصر مورد نظر در درخت وجود داشته باشد. اگر جواب مثبت باشد سه حالت پیش خواهد آمد.

  1. عنصر حذف شده در برگ باشد یعنی هیچ فرزندی نداشته باشد.
  2. دارای یک فرزند باشد
  3. دارای دو فرزند باشد.

حذف عنصر از برگ

این حالت ساده ترین حالت حذف می باشد. بدین صورت که عنصر پس از جستجو براحتی از برگ حذف می شود شکل زیر نمونه ای از این عملیات است.

درخت BST

حذف عنصر با یک فرزند

گرهی که باید حذف شود اگر تنها یک فرزند داشته باشد. در این صورت عنصر حذف می شود و فرزند جایگزین گره حذف شده می شود. شکل زیر نمونه ای از این عملیات است.

درخت BST

حذف عنصر با دو فرزند

اگر گرهی که دو فرزند دارد حذف شود باید ابتدا گرهی با کوچک‌ترین مقدار در زیردرخت راست گره را پیدا می‌کنیم. درج این گره به جای گره قبلی شرایط درخت جستجوی دودویی را به هم نمی‌زند (چرا؟). در نتیجه می‌توان به راحتی آن را جایگزین کرد. شکل زیر نمونه ای از این عملیات است.

درخت BST

کد عملیات حذف بصورت زیر خواهد بود.

/* Given a binary search tree and a key, this function deletes the key 
   and returns the new root */
struct node* deleteNode(struct node* root, int key) 
{ 
    // base case 
    if (root == NULL) return root; 
  
    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    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 right subtree 
    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 
  
    // if key is same as root's key, then This is the node 
    // to be deleted 
    else
    { 
        // node with only one child or no child 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 
  
        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        struct node* temp = minValueNode(root->right); 
  
        // Copy the inorder successor's content to this node 
        root->key = temp->key; 
  
        // Delete the inorder successor 
        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 
}

تحلیل الگوریتم درخت جستجوی دودویی BST

در جستجو با استفاده از درخت جستجوی دودویی، در هر مرحله اگر به گره مورد نظر نرسیم، یک لایه در درخت به سمت پایین حرکت می‌کنیم. بنابراین تعداد مقایسه‌ها حداکثر برابر با عمق درخت است. حداقل تعداد مقایسه‌ها هم زمانی اتفاق می‌افتد که گره مورد نظر در رأس درخت قرار داشته باشد. در این حالت تنها یک مقایسه صورت می‌گیرد.

عمق یک درخت با n گره حداکثر n و حداقل log2n]+1] است. پس می‌توان گفت این روش جستجو حداقل از مرتبه‌ی یک، حداکثر از مرتبه‌ی n و به طور متوسط از مرتبه‌ی logn است.

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