درخت جستجوی دودویی: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Y.samadzadeh (بحث | مشارکتها) اضافه کردن متن به جست و جو |
Y.samadzadeh (بحث | مشارکتها) اضافه کردن 6 پیوند |
||
خط ۳۵:
در ادامه برخی اصطلاحهای مهم مربوط به درخت مورد اشاره قرار گرفته است:
* مسیر ([[:en:Path_(graph_theory)|path]]) – منظور از مسیر در یک
* ریشه ([[:en:Rooted_graph|Root]]) – گرهی که در بخش فوقانی درخت قرار دارد، ریشه نامیده میشود. هر درختی تنها یک ریشه دارد و از گره ریشه تنها یک مسیر به هر گره دیگر وجود دارد.
* والد (parent) – هر گرهی به جز گره ریشه یالی به سمت بالا به یک گره دارد، که والد آن گره نامیده میشود.
* فرزند (child) – گرهی که زیر یک گره مفروض قرار دارد و از طریق یالی به سمت پایین به آن وصل شده است، گره فرزند آن نامیده میشود.
* برگ (leaf) – گرهی که هیچ فرزندی دارد، برگ نامیده میشود.
* زیردرخت ([[:en:Tree_(data_structure)|Subtree]]) – به مجموعه فرزندان یک گره، زیردرخت گفته میشود.
* بازدید (Visiting) – منظور از بازدید، بررسی ارزش یک گره است، هنگامی که کنترل روی گره قرار دارد.
* پیمایش ([[:en:Tree_traversal|Traversing]]) – منظور از پیمایش، عبور از میان گرههای یک درخت با ترتیب خاص است.
* سطوح (Levels) – سطح یک گره نماینده نسل آن فرزند است. اگر گره ریشه در سطح 0 باشد، در این صورت فرزندان آن در سطح 1، نوههای آن در سطح 2 و همین طور تا آخر … قرار دارند.
* کلیدها (Keys) – کلید نماینده ارزش یک گره بر مبنای نوع عملیات جستجویی است که قرار است روی گره انجام شود.
خط ۶۴:
== جستجو ==
=== انواع جست و جو و [https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ پیمایش] در درخت جست و جوی دودویی ===
* جستجو (Search) – به دنبال یک عنصر در درخت میگردد.
خط ۲۰۸:
== انواع ==
درخت جستجوی دودویی گونههای مختلفی دارد. [[درخت ایویال]] و [[درخت سرخ-سیاه]] از جمله [[درخت جستجوی دودویی خود-متوازن]] هستند. [[درخت اسپلی]] نوعی درخت دودویی است که عناصری که مکرراً مورد استفاده قرار میگیرند را به صورت خودکار به ریشه درخت نزدیک میکند تا دسترسی به آنها راحتتر شود. در یک [[تریپ]]، (tree heap) هر گره یک اولویت دارد که این اولویت به شکل تصادفی به گره اختصاص مییابد و گره والد اولویت بیشتری نسبت به فرزندش دارد. [[
درختان جست و جوی دودویی هستند که برای کاهش حافظه ی استفاده شده . به طور گسترده برای پایگاه داده های درون حافظه ای استفاده می شود.
خط ۲۱۷:
=== مقایسه عملکرد ها ===
D. A. Heger در سال ۲۰۰۴ روشی برای مقایسه عملکرد درخت های جست و جوی دودویی ارائه داد. در این مقایسه تریپ را به عنوان بهترین عملکرد در حالت میانگین معرفی کرد در حالی که در همین مقایسه درخت سرخ-سیاه کمترین
=== درخت جست و جوی دودویی بهینه ===
خط ۲۴۷:
*سایت فرادرس
* {{یادکرد کتاب |نام خانوادگی= جعفرنژاد قمی|نام= عینالله|کتاب=ساختمان دادهها در C++{{چر}} | ناشر=انتشارات علوم رایانه |سال=۱۳۹۰}}
*[https://blog.faradars.org/binary-search-tree/#%D9%86%D9%85%D8%A7%DB%8C%D8%B4_%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A8%D8%A7%DB%8C%D9%86%D8%B1%DB%8C https://blog.faradars.org/]
{{ساختمان دادهها}}
|