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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
درخت جستجوی دودویی
نوع درخت
پیچیدگی زمانی
بر حسب نماد اوی بزرگ
میانگین بدترین حالت
فضا 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. زیردرخت سمت راست و زیردرخت سمت چپ خود درختان جستجوی دودویی هستند.

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

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

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

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

جستجو[ویرایش]

برای پیدا کردن گرهی با یک کلید خاص مانند 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 را از درخت حذف می‌کنیم.

پیمایش درخت[ویرایش]

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

  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) هر گره یک اولویت دارد که این اولویت به شکل تصادفی به گره اختصاص می‌یابد و گره والد اولویت بیشتری نسبت به فرزندش دارد. درختان تانگو نوعی درخت جستجوی دودویی هستند که برای جستجوهای بسیار سریع مورد استفاده قرار می‌گیرند.

پیوند به بیرون[ویرایش]

پانویس[ویرایش]

  1. گره برگ به گرهی می‌گویند که درجه آن صفر باشد. به عبارتی دیگر، هیچ فرزندی نداشته باشد.

منابع[ویرایش]

  • هورویتز، الیس. ساختمان داده‌ها به زبان سی. انتشارات خراسان، ۱۳۷۷. 
  • جعفرنژاد قمی، عین الله. ساختمان داده‌ها در C++‎. انتشارات علوم رایانه، ۱۳۹۰.