پیاده سازی درخت جستجوی دودویی

2024 نویسنده: Angel Austin | [email protected]. آخرین اصلاح شده: 2023-12-17 05:24

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

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

نظریه و اصطلاحات عمومی

در درخت جستجوی دودویی، هر گره، به استثنای ریشه، توسط یک لبه جهت دار از یک گره به گره دیگر متصل می شود که به آن والد می گویند. هر یک از آنها را می توان به تعداد دلخواه گره که فرزند نامیده می شوند متصل کرد. گره های بدون "فرزند" برگ (گره های بیرونی) نامیده می شوند. عناصری که برگ نیستند درونی نامیده می شوند. گره هایی با والدین یکسان خواهر و برادر هستند. بالاترین گره ریشه نام دارد. در BST، یک عنصر را به هر گره اختصاص دهید و مطمئن شوید که آنها یک مجموعه ویژگی خاص برای آنها دارند.

اصطلاحات درختی:

1. عمق یک گره تعداد یال های تعریف شده از ریشه به آن است.
2. ارتفاع یک گره تعداد لبه های تعریف شده از آن تا عمیق ترین برگ است.
3. ارتفاع درخت با ارتفاع ریشه تعیین می شود.
4. درخت جستجوی باینری یک طراحی خاص است، بهترین نسبت ارتفاع و تعداد گره ها را ارائه می دهد.
5. ارتفاع h با N گره حداکثر O (log N).

می توانید این را به راحتی با شمارش گره ها در هر سطح، از ریشه شروع کنید، با این فرض که دارای بیشترین تعداد آنها باشد: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 حل این برای h h=O (log n) به دست می آید.

فواید چوب:

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

روش جستجو

به طور کلی، برای تعیین اینکه آیا یک مقدار در BST است، یک درخت جستجوی باینری را از ریشه آن شروع کنید و تعیین کنید که آیا شرایط مورد نیاز را برآورده می کند:

• در ریشه باشید؛
• در زیر درخت سمت چپ ریشه قرار بگیرید؛
• در زیردرخت سمت راست ریشه.

اگر هیچ رجیستر پایه ای راضی نشد، جستجوی بازگشتی در زیردرخت مربوطه انجام می شود. در واقع دو گزینه اساسی وجود دارد:

1. درخت خالی است - بازگشت نادرست.
2. مقدار در گره ریشه است - true را برگرداند.

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

به عبارت دیگر، بسته به "شکل" آن، بین تعداد گره ها در یک BST و ارتفاع یک درخت رابطه وجود دارد. در بدترین حالت، گره ها فقط یک فرزند دارند و درخت جستجوی دودویی متعادل اساساً یک لیست پیوندی است. به عنوان مثال:

50

/

10

15

30

/

20

این درخت دارای 5 گره و ارتفاع=5 است. یافتن مقادیر در محدوده 16-19 و 21-29 به مسیر زیر از ریشه تا برگ (گره حاوی مقدار 20) نیاز دارد. ، متناسب با تعداد گره ها زمان می برد. در بهترین حالت، همه آنها 2 فرزند دارند و برگها در همان عمق قرار دارند.

این درخت جستجوی دودویی دارای 7 گره و ارتفاع=3 است. به طور کلی، درختی مانند این (درخت کامل) ارتفاع تقریباً log 2 (N) خواهد داشت، که در آن N تعداد گره های درخت است.. مقدار log 2 (N) تعداد دفعاتی است که (2) می توان N را قبل از رسیدن به صفر تقسیم کرد.

خلاصه: بدترین زمان مورد نیاز برای جستجو در BST O (ارتفاع درخت) است. بدترین حالت "خطی" درخت O(N) است که N تعداد گره های درخت است. در بهترین حالت، یک درخت "کامل" O(log N) است.

BST درج باینری

تعجب می کنم که کجا باید باشدگره جدید در BST قرار دارد، شما باید منطق را درک کنید، باید در جایی قرار گیرد که کاربر آن را پیدا کند. علاوه بر این، باید قوانین را به خاطر بسپارید:

1. کارهای تکراری مجاز نیستند، تلاش برای درج یک مقدار تکراری یک استثنا ایجاد می کند.
2. روش درج عمومی از یک روش بازگشتی کمکی برای درج واقعی استفاده می کند.
3. یک گره حاوی یک مقدار جدید همیشه به عنوان یک برگ در BST درج می شود.
4. متد public insert void را برمی گرداند، اما متد helper یک BSTnode را برمی گرداند. این کار را برای رسیدگی به مواردی انجام می دهد که گره ارسال شده به آن null باشد.

به طور کلی، روش کمکی نشان می دهد که اگر درخت جستجوی باینری اصلی خالی باشد، نتیجه درختی با یک گره است. در غیر این صورت، نتیجه یک اشاره گر به همان گره ای خواهد بود که به عنوان آرگومان ارسال شده است.

حذف در الگوریتم باینری

همانطور که ممکن است انتظار داشته باشید، حذف یک عنصر مستلزم یافتن گره ای است که حاوی مقداری است که باید حذف شود. چندین چیز در این کد وجود دارد:

1. BST از روش حذف کمکی استفاده می کند. اگر عنصر مورد نظر شما در درخت نباشد، متد helper در نهایت با n==null فراخوانی می شود. این یک خطا در نظر گرفته نمی شود، درخت به سادگی در این مورد تغییر نمی کند. روش حذف کمکی یک مقدار - یک اشاره گر به درخت به روز شده را برمی گرداند.
2. هنگامی که یک برگ حذف می شود، حذف از درخت جستجوی دودویی، نشانگر فرزند مربوطه والد آن را تهی می کند، یا اگر برگه ای که حذف می شود، ریشه را تهی می کند.گره یک ریشه است و فرزندی ندارد.
3. توجه داشته باشید که تماس حذف باید یکی از موارد زیر باشد: root=delete (ریشه، کلید)، n.setLeft (حذف (n.getLeft ()، کلید))، n.setRight (حذف(n. getRight()، کلید)). بنابراین، در هر سه مورد صحیح است که روش حذف به سادگی null را برمی گرداند.
4. هنگامی که جستجوی گره حاوی مقداری که باید حذف شود با موفقیت انجام می شود، سه گزینه وجود دارد: گرهی که باید حذف شود یک برگ است (بدون فرزند)، گرهی که باید حذف شود دارای یک فرزند و دارای دو است. بچه ها.
5. وقتی گره ای که حذف می شود دارای یک فرزند است، می توانید به سادگی آن را با یک فرزند جایگزین کنید و یک اشاره گر را به کودک بازگردانید.
6. اگر گره ای که باید حذف شود دارای صفر یا 1 فرزند باشد، روش حذف از ریشه به آن گره "مسیر" را دنبال می کند. بنابراین بدترین زمان متناسب با ارتفاع درخت است، هم برای جستجو و هم برای درج.

اگر گره ای که باید حذف شود دو فرزند دارد، مراحل زیر انجام می شود:

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

ترتیب تراورس

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

• عمق عبور؛
• اولین پاس.

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

سه نوع مختلف تقاطع عمقی وجود دارد:

1. عبور از پیش سفارش - ابتدا به والدین و سپس فرزند چپ و راست مراجعه کنید.
2. Passing InOrder - بازدید از فرزند چپ، سپس والدین و فرزند راست.
3. پس از ارسال سفارش - بازدید از فرزند چپ، سپس فرزند راست، سپس والدین.

مثالی برای چهار پیمایش درخت جستجوی دودویی:

1. پیش سفارش - 8، 5، 9، 7، 1، 12، 2، 4، 11، 3.
2. InOrder - 9، 5، 1، 7، 2، 12، 8، 4، 3، 11.
3. سفارش پست - 9، 1، 2، 12، 7، 5، 3، 11، 4، 8.
4. LevelOrder - 8، 5، 4، 9، 7، 11، 1، 12، 3، 2.

شکل ترتیب بازدید از گره ها را نشان می دهد. عدد 1 اولین گره در یک پیمایش خاص و 7 آخرین گره است.

این پیمایش های کلی را می توان به عنوان یک الگوریتم واحد نشان داد، با این فرض که هر گره سه بار بازدید شده است. تور اویلر یک پیاده روی در اطراف یک درخت دوتایی است که در آن هر لبه به عنوان دیواری در نظر گرفته می شود که کاربر نمی تواند از آن عبور کند. در این پیاده روی، هر گره یا در سمت چپ، یا پایین و یا در سمت راست بازدید می شود. تور اویلر، که از گره های سمت چپ بازدید می کند، باعث دور زدن حرف اضافه می شود. هنگامی که گره های زیر بازدید می شوند، به ترتیب پیمایش می شوند. و هنگامی که گره های سمت راست بازدید می شوند - دریافت کنیددور زدن گام به گام.

ناوبری و اشکال زدایی

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

برای فهمیدن همه اینها، تابعی استفاده می شود که بررسی می کند آیا درخت درست است یا خیر، و به یافتن بسیاری از خطاها کمک می کند. به عنوان مثال، بررسی می کند که آیا گره والد یک گره فرزند است یا خیر. با assert(is_wellformed(root)) بسیاری از خطاها را می توان پیش از موعد کشف کرد. با استفاده از چند نقطه انفصال در این تابع، می‌توانید دقیقاً مشخص کنید که کدام نشانگر اشتباه است.

عملکرد Konsolenausgabe

این تابع کل درخت را به کنسول هدایت می کند و بنابراین بسیار مفید است. ترتیبی که هدف خروجی درخت اجرا می شود:

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

با این حال، استفاده از این تابع در درختان بزرگ دشوار خواهد بود.

کپی سازنده و تخریبگر

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

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

با این روش، پیاده سازی درخت جستجوی باینری همیشه در حالت سالم است و حتی در حالت ناقص نیز می تواند توسط تخریبگر حذف شود. اگر استثنایی رخ دهد، تنها کاری که باید انجام دهید این است که به تخریبگر دستور دهید درخت نیمه تمام را حذف کند. اپراتور واگذاریمی توان به راحتی با استفاده از Copy & Swap پیاده سازی کرد.

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

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

1. یک گره والد حداکثر ۲ گره فرزند دارد.
2. گره فرزند سمت چپ همیشه کمتر از گره والد است.
3. گره فرزند معتبر همیشه بزرگتر یا مساوی با گره والد است.

آرایه ای که برای ساخت درخت جستجوی باینری استفاده می شود:

1. آرایه اعداد صحیح پایه از هفت مقدار به ترتیب مرتب نشده.
2. اولین مقدار در آرایه 10 است، بنابراین اولین گام در ساختن درخت، ایجاد یک گره ریشه 10 است، همانطور که در اینجا نشان داده شده است.
3. با مجموعه ای از گره های ریشه، همه مقادیر دیگر فرزندان این گره خواهند بود. با اشاره به قوانین، اولین قدمی که باید برای افزودن 7 به درخت برداشته شود، مقایسه آن با گره ریشه است.
4. اگر مقدار 7 کمتر از 10 باشد، به گره فرزند سمت چپ تبدیل می شود.
5. اگر مقدار 7 بزرگتر یا مساوی 10 باشد، به سمت راست حرکت می کند. از آنجایی که 7 کمتر از 10 شناخته می شود، به عنوان گره فرزند سمت چپ تعیین می شود.
6. به صورت بازگشتی برای هر عنصر مقایسه انجام دهید.
7. با پیروی از الگوی یکسان، مقایسه مشابهی را با مقدار چهاردهم در آرایه انجام دهید.
8. مقایسه مقدار 14 با گره ریشه 10، با دانستن اینکه 14 فرزند صحیح است.
9. راه رفتن در آرایه،به 20 بیا.
10. با مقایسه آرایه با 10 شروع کنید، هر کدام بزرگتر است. بنابراین به سمت راست حرکت کنید و آن را با 14 مقایسه کنید، او بیش از 14 سال دارد و در سمت راست فرزندی ندارد.
11. اکنون مقدار 1 وجود دارد. با پیروی از الگوی مشابه سایر مقادیر، 1 را با 10 مقایسه کنید، به سمت چپ حرکت کنید و با 7 مقایسه کنید و در نهایت با 1 فرزند چپ گره 7.
12. اگر مقدار 5 است، آن را با 10 مقایسه کنید. از آنجایی که 5 کمتر از 10 است، به سمت چپ منتقل کنید و آن را با 7 مقایسه کنید.
13. با دانستن اینکه 5 کمتر از 7 است، به پایین درخت ادامه دهید و 5 را با مقدار 1 مقایسه کنید.
14. اگر 1 فرزند ندارد و 5 بزرگتر از 1 است، 5 فرزند معتبر 1 گره است.
15. در نهایت مقدار 8 را در درخت وارد کنید.
16. وقتی 8 کمتر از 10 است، آن را به سمت چپ ببرید و با 7 مقایسه کنید، 8 بزرگتر از 7 است، بنابراین آن را به سمت راست ببرید و درخت را کامل کنید، و 8 را فرزند مناسبی از 7 کنید.

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

مشکلات بالقوه جستجوی باینری

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

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

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

نمونه‌های محاسبه جستجوی باینری

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

10

/

/

5 15

/ /

/ /

2 12 20

هنگام درج x در درخت T که هنوز حاوی x نیست، کلید x همیشه در یک برگ جدید قرار می گیرد. در ارتباط با این، درخت جدید به شکل زیر خواهد بود:

10

/

/

5 15

/ /

/ /

2 12 20

25

اگر 7 را در درخت جستجوی دودویی زیر وارد کنید چه نوع درختی بدست می آورید؟

10

/

/

5 15

/ /

/ /

2 12 20

پاسخ:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

درخت جستجوی دودویی را می توان برای ذخیره هر شی مورد استفاده قرار داد. مزیت استفاده از درخت جستجوی دودویی به جای لیست پیوندی این است که اگر درخت به طور معقولی متعادل باشد و بیشتر شبیه درخت «پر» باشد تا «خطی»، درج، جستجو و تمام عملیات حذف را می توان برای اجرا در آن اجرا کرد. زمان O(log N).