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

درخت جستجوی دودویی
گونه	درخت
زمان اجرای الگوریتم بر پایه نماد O بزرگ
الگوریتم میانگین بدترین حالت فضا O(n) O(n) جستجو O(log n) O(n) درج O(log n) O(n) حذف O(log n) O(n)

یک درخت جستجوی دودویی با اندازه ۹، عمق ۳، ریشه ۸ و برگ‌های ۱، ۴، ۷ و ۱۳.

در علوم رایانه، درخت جستجوی دودویی (به انگلیسی: Binary search tree یا به اختصار BST) که گاهی درخت دودویی مرتب هم نامیده می‌شود، یک ساختار داده است و نوعی درخت دودویی است.

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

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

انواع مختلفی از درخت‌های جست و جوی دودویی مورد بررسی و مطالعه قرار گرفته‌اند.

تعریف

درخت جستجوی دودویی، نوعی درخت دودویی است که ممکن است تهی باشد، اگر تهی نباشد، دارای خصوصیات زیر است:

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

این ویژگی تضمین می‌کند که پیمایش میان‌ترتیب یک درخت جستجوی دودویی، کلیدها را به ترتیب صعودی نمایش می‌دهد.

در ادامه برخی اصطلاح‌های مهم مربوط به درخت مورد اشاره قرار گرفته‌است:

• مسیر (path) – منظور از مسیر در یک درخت، یک توالی از گره‌ها در راستای یال‌های درخت است.
• ریشه (Root) – گرهی که در بخش فوقانی درخت قرار دارد، ریشه نامیده می‌شود. هر درختی تنها یک ریشه دارد و از گره ریشه تنها یک مسیر به هر گره دیگر وجود دارد.
• والد (parent) – هر گرهی به جز گره ریشه یالی به سمت بالا به یک گره دارد، که والد آن گره نامیده می‌شود.
• فرزند (child) – گرهی که زیر یک گره مفروض قرار دارد و از طریق یالی به سمت پایین به آن وصل شده‌است، گره فرزند آن نامیده می‌شود.
• برگ (leaf) – گرهی که هیچ فرزندی دارد، برگ نامیده می‌شود.
• زیردرخت (Subtree) – به مجموعه فرزندان یک گره، زیردرخت گفته می‌شود.
• بازدید (Visiting) – منظور از بازدید، بررسی ارزش یک گره است، هنگامی که کنترل روی گره قرار دارد.

• 

  جست و جوی دودویی روی آرایهٔ مرتب شده

  پیمایش (Traversing) – منظور از پیمایش، عبور از میان گره‌های یک درخت با ترتیب خاص است.
• سطوح (Levels) – سطح یک گره نماینده نسل آن فرزند است. اگر گره ریشه در سطح ۰ باشد، در این صورت فرزندان آن در سطح ۱، نوه‌های آن در سطح ۲ و همین‌طور تا آخر … قرار دارند.
• کلیدها (Keys) – کلید نماینده ارزش یک گره بر مبنای نوع عملیات جستجویی است که قرار است روی گره انجام شود.

عملیات اصلی بر روی یک درخت جستجوی دودویی به زمانی متناسب با ارتفاع درخت احتیاج دارد. برای یک درخت دودویی کامل با n گره چنین عملیاتی در بدترین حالت در زمان (o(logn اجرا می‌شود؛ بنابراین اگر درخت یک زنجیر خطی با n گره باشد همین عملیات در زمان بدترین حالت (o(n اجرا می‌شود. امید ریاضی ارتفاع یک درخت جستجوی دودویی که به تصادف ساخته شده‌است برابر با (o(logn است؛ بنابراین عملیات اصلی مجموعه پویا بر روی چنین درختی در حالت میانگین به زمان (o(logn احتیاج دارد.

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

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

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

معمولاً عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود:

1. ایجاد یک درخت جستجوی خالی
2. آزمایش خالی بودن درخت
3. درج کردن یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت
4. جستجو کردن و یافتن یک کلید خاص در درخت
5. حذف کردن یک کلید از درخت، با حفظ خاصیت درخت
6. پیمایش درخت جستجوی دودویی، به‌طوری تمام گره‌ها دقیقاً یک بار مورد دسترسی قرار گیرند.

جستجو

انواع جست و جو و پیمایش در درخت جست و جوی دودویی

• جستجو (Search) – به دنبال یک عنصر در درخت می‌گردد.
• پیمایش پیش‌ترتیبی (Preorder Traversal) – یک درخت را به روش پیش‌ترتیبی پیمایش می‌کند
• پیمایش میان‌ترتیبی (Inorder Traversal) – یک درخت را به روش میان‌ترتیبی پیمایش می‌کند.
• پیمایش پس‌ترتیبی (Postorder Traversal) – یک درخت را به روش پس‌ترتیبی پیمایش می‌کند.

پیمایش میان ترتیبی

پیمایش میان‌ترتیبی

در این روش از پیمایش، زیردرخت چپ ابتدا بازدید می‌شود، سپس از گره ریشه بازدید می‌شود و در نهایت زیردرخت راست پیمایش می‌شود. همواره باید به خاطر داشته باشید که هر گره می‌تواند خود نماینده یک زیردرخت باشد.

اگر یک درخت باینری به صوت میان‌ترتیبی پیموده شود، مقادیر کلیدهای ذخیره شده در خروجی به ترتیب نزولی نمایش داده می‌شود

الگوریتم

• تا زمانی که همه گره‌ها بازدید شوند:
• گام ۱- زیردرخت چپ را به صورت بازگشتی پیمایش کن
• گام ۲ – گره ریشه را بازدید کن
• گام ۳ – زیردرخت سمت راست را به صورت بازگشتی پیمایش کن.

پیمایش پیش ترتیبی

پیمایش پیش‌ترتیبی

در این روش پیمایش، گره ریشه ابتدا مورد بازدید قرار می‌گیرد، سپس زیردرخت چپ و در نهایت زیردرخت راست پیموده می‌شوند.

الگوریتم

• تا زمانی که همه گره‌ها پیمایش شوند:
• گام ۱ – از گره ریشه بازدید کن.
• گام ۲ – زیردرخت چپ را به صورت بازگشتی پیمایش کن.
• گام ۳ – زیردرخت راست را به صورت بازگشتی پیمایش کن.

پیمایش پس ترتیبی

پیمایش پس‌ترتیبی

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

الگوریتم

• تا زمانی که همه گره‌ها پیمایش شوند:
• گام ۱ – زیردرخت چپ را به صورت بازگشتی پیمایش کن.
• گام ۲ – زیردرخت راست را به صورت بازگشتی پیمایش کن.
• گام ۳ – از گره ریشه بازدید کن.

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

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

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

node_t search(node_t *root, T value)
{
 if(NULL != root)
 {

  if(root->key == value)
   return root;

  else if(value <root->key)
   search(root->left, value)

  else
   search(root->right, value)
 }

 return NULL;
}

درج عنصر جدید

برای درج کردن یک گره جدید در درخت جستجوی دودویی، باید گره را طوری درج کرد که خاصیت درخت برهم نخورد و درخت همچنان یک درخت جستجوی دودویی باقی بماند. برای حفظ خاصیت اول (منحصربه‌فرد بودن کلیدها)، باید ابتدا درخت را جستجو کنیم تا مطمئن شویم که عنصر قبلاً در درخت درج نشده‌است. پس از اینکه مطمئن شدیم کلید مورد نظر از قبل در درخت وجود ندارد، می‌توانیم کلید را در درخت درج کنیم. اگر درخت تهی بود، کافیست گره جدید را به عنوان گره ریشه درج کنیم تا عمل درج خاتمه یابد. اگر درخت خالی نبود، کلید جدید را با ریشه مقایسه می‌کنیم، که دو حالت جستجو پیش می‌آید:

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

درج عنصر

عمل درج در درخت جستجوی دودویی، از مرتبه O(h)‎ است.

درج

درج

typedef int T

void insert(node_t **tree, T data)
{
        node_t *temp;

        if(!(*tree))
        {
                temp = malloc(sizeof(node_t));
                temp->left = temp->right = NULL;
                temp->key = data;

                *tree = temp;

                return;
        }

        if(data <(*tree)->key)
                insert(&(*tree)->left, data);

        if(data> (*tree)->key)
                insert(&(*tree)->right, data);

}

حذف یک گره

فرض کنید می‌خواهیم گره i را از درخت جستجوی دودویی حذف کنیم. به‌طوری که P(i)‎ نشان‌دهنده والد گره i و C(i)‎ نشان‌دهنده فرزند گره i است (چپ یا راست). در مورد حذف یک گره از درخت دودویی، سه حالت مختلف پیش می‌آید:

1. i یک گره برگ است.
2. i یک فرزند دارد.
3. i دو فرزند دارد.

در حالت اول، کافیست اشاره‌گر مناسبی (چپ یا راست) از P(i)‎ را برابر تهی قرار دهیم، عمل حذف خاتمه می‌یابد. در حالت دوم که i یک فرزند دارد، ابتدا گره i را حذف می‌کنیم، سپس فرزند i یا همان C(i)‎ را جانشین گره i می‌کنیم.

حذف

حذف

حذف

حذف یک گره با دو فرزند از یک درخت جستجوی دودویی

در حالتی که i دو فرزند دارد، باید بزرگ‌ترین عنصر در زیردرخت چپ یا کوچک‌ترین عنصر در زیردرخت راست را پیدا کرده و سپس آن را با گره i جایگزین و تعویض می‌کنیم. سپس ما این فرایند را با حذف کردن این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. به عبارتی دیگر، اگر بخواهیم گره N را از درخت حذف کنیم (که این گره دو فرزند دارد)، به جای اینکه خود گره N را پاک کنیم، یا گره بعد از N در پیمایش میانوندی یا گره قبلی N در پیمایش میانوندی را انتخاب می‌کنیم و آن گره را R می‌نامیم. سپس مقادیر N و R را تعویض کرده و سپس R را از درخت حذف می‌کنیم.

تابع transplant

این تابع در تابع حذف گره از درخت استفاده می‌شود، این تابع دوگره u و v را به عنوان ورودی می‌گیرد و اگر u ریشه درخت باشد آنگاه v را ریشه درخت قرار می‌دهد، اگر u ریشه دره نباشد پدر u را به v اشاره می‌دهد، و اگر v نال نبود پدر v را پدر u قرار می‌دهد، در واقع این تابع v را جای u قرار می‌دهد و از نظر رابطه با گرهٔ پدر کارها را درست می‌کند ولی کاری به جابه‌جا کردن فرزندان u , v ندارد.

پیمایش درخت

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

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

الگوریتم بالا بازگشتی است.

void inorder(node_t *root)
{
 if(!root)
 {
  if(root->left)
   inorder(root->left)

  process(root->key);

  if(root->right)
   inorder(root->right);
}

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

انواع

درخت جستجوی دودویی گونه‌های مختلفی دارد. درخت ای‌وی‌ال و درخت سرخ-سیاه از جمله درخت جستجوی دودویی خود-متوازن هستند. درخت اسپلی نوعی درخت دودویی است که عناصری که مکرراً مورد استفاده قرار می‌گیرند را به صورت خودکار به ریشه درخت نزدیک می‌کند تا دسترسی به آن‌ها راحت‌تر شود. در یک تریپ، (tree heap) هر گره یک اولویت دارد که این اولویت به شکل تصادفی به گره اختصاص می‌یابد و گره والد اولویت بیشتری نسبت به فرزندش دارد. درختان تانگو نوعی درخت جستجوی دودویی هستند که برای جستجوهای بسیار سریع مورد استفاده قرار می‌گیرند.

درختان جست و جوی دودویی هستند که برای کاهش حافظهٔ استفاده شده. به‌طور گسترده برای پایگاه داده‌های درون حافظه ای استفاده می‌شود.

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

کرد.

مقایسه عملکردها

D. A. Heger در سال ۲۰۰۴ روشی برای مقایسه عملکرد درخت‌های جست و جوی دودویی ارائه داد. در این مقایسه تریپ را به عنوان بهترین عملکرد در حالت میانگین معرفی کرد در حالی که در همین مقایسه درخت سرخ-سیاه کمترین اختلاف را بین بدترین حالت و بهترین حالتش دارد هرچند به‌طور میانگین تریپ بهتر ازآن عمل می‌کند.

درخت جست و جوی دودویی بهینه

برای این که bstهایی که داریم را به نحوی تغییر دهیم که الگوریتم جست وجوی بهینه ای داشته باشیم از روش زیر مب توان استفاده کرد:

گره‌هایی که بیشترین استفاده را دارند و دسترسی به آن‌ها مورد نیاز است را نزدیک ریشه قرار می‌دهیم. همچین گره‌هایی که کمترین به آن دسترسی داریم را نزدیک برگ‌ها قرار می‌دهیم. با این روش بهینه هزینه جیت و جوی کمتری خواهیم داشت.

جستارهای وابسته

• الگوریتم جستجوی دودویی
• جستجوی درختی
• درخت جستجوی دودویی خود-متوازن
• درخت ای‌وی‌ال
• درخت سرخ-سیاه
• داده ساختار تیریپ
• درخت جستجوی دودویی بهینه

پیوند به بیرون

• معرفی، درج و حذف از درخت جستجوی دودویی

منابع

• هورویتز، الیس (۱۳۷۷). ساختمان داده‌ها به زبان سی. انتشارات خراسان.
• سایت فرادرس
• جعفرنژاد قمی، عین‌الله (۱۳۹۰). ساختمان داده‌ها در C++‎. انتشارات علوم رایانه.
• https://en.wikipedia.org/wiki/Binary_search_tree