درخت جستجوی دودویی: تفاوت میان نسخه‌ها

[[پرونده:Binary search tree.svg|چپ|200px|بندانگشتی|یک درخت جستجوی دودویی با اندازه ۹، عمق ۳، ریشه ۸ و برگ‌های ۱، ۴، ۷ و ۱۳.]]

 

 

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

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

 

* والد (parent) – هر گرهی به جز گره ریشه یالی به سمت بالا به یک گره دارد، که والد آن گره نامیده می‌شود.

* فرزند (child) – گرهی که زیر یک گره مفروض قرار دارد و از طریق یالی به سمت پایین به آن وصل شده است، گره فرزند آن نامیده می‌شود.

* برگ (leaf) – گرهی که هیچ فرزندی دارد، برگ نامیده می‌شود.

* بازدید (Visiting) – منظور از بازدید، بررسی ارزش یک گره است، هنگامی که کنترل روی گره قرار دارد.

* کلیدها (Keys) – کلید نماینده ارزش یک گره بر مبنای نوع عملیات جستجویی است که قرار است روی گره انجام شود.

 

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

 

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

 

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

# جستجو کردن و یافتن یک کلید خاص در درخت

# حذف کردن یک کلید از درخت، با حفظ خاصیت درخت

 

== جستجو ==

<br />

[[پرونده:Bst-insert-1.jpg|بندانگشتی|درج]]

 

<syntaxhighlight lang="c">typedef int T

</syntaxhighlight><br />

== حذف یک گره ==

# i یک گره برگ است.<ref>گره برگ به گرهی می‌گویند که درجه آن صفر باشد. به عبارتی دیگر، هیچ فرزندی نداشته باشد.</ref>

# i یک فرزند دارد.

[[پرونده:Bst-delete-2.jpg|بندانگشتی|حذف]]

[[پرونده:Bst-delete-3.jpg|بندانگشتی|حذف]]

 

[[File:AVL-tree-delete.svg|thumb|500px|left|حذف یک گره با دو فرزند از یک درخت جستجوی دودویی]]

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

 

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

 

 

== انواع ==

 

 

 

کرد.

 

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

 

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

 

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

 

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