درخت باینری

درخت جستجوی باینری دیگه چه کوفتیه؟

درخت دودویی نوعی ساختار داده است که معمولاً برای نمایش داده های سلسله مراتبی استفاده می شود. این یک روش کارآمد برای ذخیره و سازماندهی داده ها است که در گره های مادر و گره های فرزند رتبه بندی می شود.

آموزش ویدیویی الگوریتم binary search در پایتون

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

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

به عنوان مثال ، در تصویر بالا ، می توان نتیجه گرفت که این یک درخت جستجوی دودویی است زیرا چون 3 کمتر از 8 است ، به زیر درخت چپ می رود و از آنجا که 10 بزرگتر از 8 است ، به زیر درخت راست می رود. علاوه بر این ، می توان فرض کرد که هیچ گره ای نمی تواند از زیر درختان عبور کند ، اطمینان حاصل شود که همه گره های کمتر از ریشه همیشه در زیر درخت چپ قرار دارند و برعکس. به خاطر داشته باشید که تغییر مقدار یک درخت باینری گره که آن را کمتر یا بیشتر از گره می کند ، مانع درخت می شود. اگر مقدار گره کودک راست 3 ، که 6 است ، به 9 تغییر کند ، این دیگر یک درخت دوتایی نخواهد بود ، زیرا اگرچه 9 بزرگتر از 3 است و در سمت راست 3 قرار دارد ، 9 نیز بزرگتر از ریشه 8 ، بنابراین نمی تواند در سمت چپ باقی بماند.

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

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

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

آموزش ویدیویی الگوریتم جستجوی خطی در پایتون

بیایید نگاهی به این مثال بیندازیم تا یک جستجوی دودویی از یک درخت دوتایی نامتعادل را انجام دهیم.

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

در مثال زیر ، گره درخت باینری ای با مقدار 64 را جستجو می کنیم. از آنجا که می دانیم 64 بزرگتر از ریشه ، 60 است ، در حالی که گره فرزند را با مقدار مورد نظر مقایسه می کنیم ، به زیر درخت راست نگاه می کنیم. به فضای جستجوی فعلی ما n/2 می شود. در ادامه ، ما به پایین رفتن درخت از طریق گره با مقدار 74 ادامه می دهیم. از آنجا که هدف ما کمتر است و والدین فقط یک فرزند دارند ، ما این کار را ادامه می دهیم. فضای جستجوی به روز شده ما: n/4. بعد ، 64 کمتر از 65 است که ما به سمت چپ نگاه می کنیم. فضای جستجو: n/8. در نهایت ، ما می بینیم که 64 بزرگتر از گره والدین 63 است ، ما به سمت راست نگاه می کنیم و گره را پیدا می کنیم. فضای نهایی جستجوی ما n/16 می شود زیرا 4 جستجوی دودویی برای یافتن گره مورد نظر ما طول کشید.

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

در مثال زیر ، گره ای با مقدار 18 وارد می کنیم. از ریشه شروع می کنیم ، 18 بزرگتر از 10 است ، بنابراین آن را در زیر درخت سمت راست قرار می دهیم. با حرکت رو به جلو ، می بینیم که 18 کمتر از 19 است ، بنابراین به سمت کودک چپ می رویم. از آنجا که 18 بزرگتر از 17 است ، اما هیچ گره فرزند وجود ندارد ، ما یک گره جدید ایجاد (وارد) می کنیم و روند کامل می شود. درخت دوتایی جدید ما شبیه این خواهد بود.

در اینجا نمونه ای از کد درج درخت جستجوی دودویی به نظر می رسد:

اگر تا اینجا خوانده اید ، اکنون درک اولیه ای از نحوه عملکرد ، درج و حذف درخت دوتایی دارید..

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

مفهوم درخت در نظریه گراف ها، نشان دهنده گره‌هایی است که به وسیله یال‌ها یا لبه ها به هم متصل شده‌اند. ما در این نوشته در مورد درخت‌های درخت باینری دودویی (باینری) یا درخت‌های جستجوی دودویی ( Binary Search Tree ) به اختصار BST صحبت خواهیم کرد. درخت دودویی نوع خاصی از ساختمان داده است که برای ذخیره‌سازی داده مورد استفاده قرار می‌گیرد.

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

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

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

عملیاتی که می توان در درخت دودویی انجام داد شامل جستجو Search، اضافه کردن یا درج Insertion و حذف Delete خواهد بود. که در ادامه این سه عملیات تشریح می شوند.

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

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

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

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

1. از ریشه شروع کنید (وضعیت 6 را با گره ریشه؟ کوچکتر است پس عدد در زیر دخت سمت چپ است )
2. عدد 6 را با ریشه زیر درخت سمت چپ مقایسه کنید. (درخت باینری بزرگتر است پس عدد در زیر دخت سمت راست است )
3. عدد 6 را با ریشه زیر درخت سمت راست مقایسه کنید. (برابر است پس پیدا شد)

عملیات درج در درخت دودویی

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

کد عملیات درج بصورت زیر خواهد بود.

حذف از درخت دودویی

برای حذف یک عنصر از درخت دودویی ابتدا باید بررسی شود که عنصر مورد نظر در درخت وجود داشته باشد. اگر جواب مثبت باشد سه حالت پیش خواهد آمد.

1. عنصر حذف شده در برگ باشد یعنی هیچ فرزندی نداشته باشد.
2. دارای یک فرزند باشد
3. دارای دو فرزند باشد.

حذف عنصر از برگ

این حالت ساده ترین حالت حذف می باشد. بدین صورت که عنصر پس از جستجو براحتی از برگ حذف می شود شکل زیر نمونه ای از این عملیات است.

حذف عنصر با یک فرزند

گرهی که باید حذف شود اگر تنها یک فرزند داشته باشد. در این صورت عنصر حذف می شود و فرزند جایگزین گره حذف شده می شود. شکل زیر نمونه ای از این عملیات است.

حذف عنصر با دو فرزند

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

کد عملیات حذف بصورت زیر خواهد بود.

تحلیل الگوریتم درخت جستجوی دودویی BST

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

عمق یک درخت با n گره حداکثر n و حداقل log2n]+1] است. پس می‌توان گفت این روش جستجو حداقل از مرتبه‌ی یک، حداکثر از مرتبه‌ی n و به طور متوسط از مرتبه‌ی logn است.

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

درباره امین جلیل زاده رزین

کارشناس ارشد رشته مهندسی کامپیوتر گرایش نرم افزار - پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.

درخت باینری

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

در ریاضیات و بخصوص نظریه مجموعه ها، مجموعه کانتور (Cantor Set) از اهمیت زیادی برخوردار است. «توپولوژی نقطه-مجموعه» (Point-set Topology) در بسیاری از موارد وام…

در این مطلب، با حوزه «بینایی ماشین» (Machine Vision) از منظر «علوم کامپیوتر» (Computer Science) آشنا خواهید شد. مطلب پیش رو را می‌توان به عنوان…

در این مطلب، تعریف «درخت جستجوی دودویی» (Binary Search Tree | BST) بیان و عملیات در درخت جستجوی دودویی شامل جستجو و درج آموزش داده…

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

در این راهنما عملیات مقدماتی را برای یک درخت دودویی با استفاده از زبان برنامه‌نویسی کاتلین معرفی می‌کنیم. بدین ترتیب با پیاده‌سازی درخت دودویی در…

در این مقاله به بررسی روش پیاده‌سازی درخت دودویی در جاوا می‌پردازیم. ما در این راهنما از یک درخت دودویی مرتب استفاده می‌کنیم که شامل…

درخت، ساختمان داده‌ای است که امکان نمایش شکل‌های مختلفی از داده‌های سلسله مراتبی را به ما می‌دهد. DOM در صفحه‌های HTML، فایل‌ها و پوشه‌های روی…

درخت نشان دهنده گره‌هایی است که به وسیله یال‌ها به هم متصل شده‌اند. ما در این نوشته به طور خاص درخت‌های دودویی یا درخت‌های جستجوی…

با فرادرس

آموزش‌های ویدئویی فرادرس

همراه شوید

سازمان علمی و آموزشی «فرادرس» (Faradars) از قدیمی‌ترین وب‌سایت‌های یادگیری آنلاین است که توانسته طی بیش از ده سال فعالیت خود بالغ بر ۱۲۰۰۰ ساعت آموزش ویدیویی در قالب فراتر از ۲۰۰۰ عنوان علمی، مهارتی و کاربردی را منتشر کند و به بزرگترین پلتفرم آموزشی ایران مبدل شود. فرادرس با پایبندی به شعار «دانش در دسترس همه، همیشه و همه جا» با همکاری بیش از ۱۸۰۰ مدرس برجسته در زمینه‌های علمی گوناگون از جمله آمار و درخت باینری داده‌کاوی، هوش مصنوعی، برنامه‌نویسی، طراحی و گرافیک کامپیوتری، آموزش‌های دانشگاهی و تخصصی، آموزش نرم‌افزارهای گوناگون، دروس رسمی دبیرستان و پیش دانشگاهی، آموزش‌های دانش‌آموزی و نوجوانان، آموزش زبان‌های خارجی، مهندسی برق، الکترونیک و رباتیک، مهندسی کنترل، مهندسی مکانیک، مهندسی شیمی، مهندسی صنایع، مهندسی معماری و مهندسی عمران توانسته بستری را فراهم کند تا افراد با شرایط مختلف زمانی، مکانی و جسمانی بتوانند با بهره‌گیری از آموزش‌های با کیفیت، به روز و مهارت‌محور همواره به یادگیری بپردازند. شما هم با پیوستن به جمع بزرگ و بالغ بر ۶۰۰ هزار نفری دانشجویان و دانش‌آموزان فرادرس و با درخت باینری بهره‌گیری از آموزش‌های آن، می‌توانید تجربه‌ای متفاوت از علم و مهارت‌آموزی داشته باشید. مشاهده بیشتر

هر گونه بهره‌گیری از مطالب مجله فرادرس به معنی پذیرش شرایط استفاده از آن بوده و کپی بخش یا کل هر کدام از مطالب، تنها با کسب مجوز مکتوب امکان پذیر است.
© فرادرس ۱۴۰۱