درخت باینری

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

درخت باینری

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

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

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

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

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

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

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

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

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

با فرادرس

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

همراه شوید

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

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

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

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

آموزش ویدیویی الگوریتم 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 است ، اما هیچ گره فرزند وجود ندارد ، ما یک گره جدید ایجاد (وارد) می کنیم و روند کامل می شود. درخت دوتایی جدید ما شبیه این خواهد بود.

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

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

درخت های ریشه دار

در نظریهٔ گراف، یک «درخت ریشه‌دار» (Rooted Tree) به درختی گفته می‌شود که یک رأس در آن به عنوان ریشه برچسب خورده باشد. درخت درخت باینری ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است.

رأس‌هایی که به طور مستقیم به رأس دیگری متصل اند بچه‌های آن نامیده می‌شوند. مثلاً در شکل روبرو $E$ و $H$ بچه‌های $B$ هستند و $B$ پدر آنهاست. همچنین اگر یک رأس بچه‌ای نداشته باشند به آن برگ می‌گویند.(مانند گره $G$)

تعداد درخت‌های ریشه دار با $n$ رأس بر اساس دنباله روبرو است: ۱, ۱, ۲, ۴, ۹, ۲۰, ۴۸, ۱۱۵, ۲۸۶, ۷۱۹, ۱۸۴۲, ۴۷۶۶,… (http://mathworld.wolfram.com/RootedTree.html Rooted Tree, Wolfram MathWorld)

درخت $m$-تایی پر: درختی که هر راس داخلی آن دقیقا $m$ فرزند دارد.
- درخت $m$-تایی پر که دارای $n$-تا راس ، $i$-تا راس داخلی و $l$-تا برگ باشد ، روابط زیر برقرار است:
*

درخت $m$-تایی متقارن : درختی است که زیر درخت های ریشه ی آن دارای مسیر های تقریبا هم اندازه باشد. (اختلاف مسیر ها در حد $1$ یا $2$ باشد.)

سطح هر راس($Level$) : به طول کوتاه ترین مسیر از ریشه تا راس مورد نظر را سطح ($Level$) آن راس می گویند.

ارتفاع درخت($Height$): به ماکزیمم سطح هر درخت ارتفاع ($Height$)آن می گویند.

-اگر در درخت $m$-تایی ، $m$ را به توان ارتفاع برسانیم ، حداکثر تعداد برگ ها بدست می آید.

درخت دودویی

تعریف

در علوم رایانه، یک «درخت دودویی» یک ساختمان داده ی درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می‌شوند.درخت‌های دودویی برای پیاده‌سازی«درخت جستجوی دودویی» و «انبوه دودویی» و برای جستجوی کارآمد و مرتب‌سازی استفاده می‌شود. درخت دودویی یک حالت خاص از یک «درخت $k‌‌$-تای» است ،که در آن $k$ برابر $2$ می‌باشد.

انواع درختان دودویی

«درخت دودویی پر»(گاهی اوقات «درخت دودویی مناسب» یا «$2$_ درخت» یا «درخت اکیداً دودویی» گفته می‌شود ) یک درخت که در آن هر گره به غیر از برگ‌ها دارای دو فرزند است.هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است .یک درخت پر گاهی‌اوقات به‌طور ابهام‌انگیزی به عنوان «درخت دودویی کامل» تعریف می‌شود.فیزیکدانان یک «درخت دودویی» را به‌عنوان «درخت دودویی پر» تعریف می‌کنند.

«درخت دودویی کامل» ($complete$) یک درخت دودویی است که در آن هر سطح ،به جز احتمالاً آخرین سطح،به‌طور کامل پر شده‌است، و همۀ گره‌ها تا جایی که ممکن است در چپ درخت قرار می‌گیرند.درختی درخت باینری درخت باینری که این استثنا را داشته‌باشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند.این نوع درختان از ساختمان دادۀ ویژه‌ای به نام «هیپ» استفاده می‌کنند.

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

«درختی دودویی متوازن» که معمولاً به‌عنوان درخت دودویی است که در آن اختلاف عمق زیردرخت چپ و راست آن $1$ یا کمتر است، اگر چه به طور کلی درخت دودویی است که هیچ برگی نسبت با برگ‌های دیگر فاصلۀ زیادی تا ریشه ندارد.(طرح توازن متمایز اجازه می‌دهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود.) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش بینی باشد.(بسیاری از گره‌ها از ریشه تا برگ پیموده می‌شوند ، چنانکه شمارۀ ریشه به عنوان گرۀ $0$ و بقیۀ گره‌ها اعداد n … 2 1 را می‌گیرند.) این عمق (ارتفاع هم نامیده می‌شود) برابر قسمت صحیح ( log₂( n است، که در آن $n$ تعداد گره‌ها در درخت متوازن است. مثلاً، برای درخت متوازنی که دارای $1$ گره است ، log₂(1)=0 ،درنتیجه عمق درخت برابر صفر است.برای یک درخت متوازن با $100$ گره ، log₂(100)=6.64 ،درنتیجه عمق درخت برابر $6$ است. -

» درخت منحط» درختی است که هر گرۀ والدین فقط به یک گرۀ فرزند متصل است.این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادۀ «لیست پیوندی» است.

خواص درخت دودویی

تعداد $n$ گره در «درخت دودویی کامل» را می‌توان با استفاده از این فرمول بدست‌ آورد :n = 2 h + 1 - 1 که در آن $h$ ارتفاع درخت است.

تعداد $n$ گره در «درخت دودویی کامل» را همچنین می‌توان با استفاده از این فرمول بدست آورد : n = 2 l - 1 که در آن $l$ تعداد برگ‌های درخت است.

تعداد گره‌های داخلی (گره‌های غیر از برگ یا n - l ) در درخت دودویی کامل با $n$ گره برابر (floor (n/2 است.

عملیات متداول

انواع عملیات‌های مختلف را می‌توان روی درخت دودویی انجام‌داد.بعضی از عملیات‌ها تغیری ایجاد می‌کنند، درحالی که دیگر عمیات اطلاعات مفیدی را درمورد درخت برمی‌گرداند.

گره‌ها در درخت دودویی می‌توانند بین دو گره دیگر و یا بعد از گره خارجی درج شوند. در درخت دودویی گره درج شده به عنوان فرزند مشخص می‌شود.

گره‌های خارجی

گره خارجی اضافه شده گره $A$ است،برای اضافه کردن یک گره بعد از گره $A$ ، گره $A$ گره جدید را به عنوان فرزند مشخص خود می‌کند و گره جدید گره $A$ را به عنوان گره والد تعیین می‌کند.

گره‌های داخلی

درج در «گره‌های داخلی» پیچیده‌تر از گره‌های خارجی است.فرض می‌کنیم که $A$ گرۀ داخلی و $B$ فرزند گرۀ $A$ باشد.(اگر درج در قسمت فرزند راست باشد، آنگاه $B$ فرزند سمت راست $A$ است،برای درج فرزند سمت چپ هم همین‌طور است.) $A$ فرزند جدید را مشخص می‌کند و گرۀ جدید $A$ را که والدین آن است مشخص می‌کند.

حذف فرآیندی است که یک گره را از درخت حذف می‌کند.فقط می‌توان گره‌های خاصی را در درخت دودویی به وضوح حذف کرد.

گرۀ بدون فرزند یا دارای یک فرزند

فرض کنید گره‌ای که می‌خواهیم حذف کنیم گرۀ $A$ باشد. اگر گره بدون فرزند باشد (گرۀ خارجی) ، آنگاه فرزند والدین گرۀ $A$ تهی می‌شود. اگر دارای یک فرزند باشد ، آنگاه فرزند $A$ را به والدین گرۀ $A$ درخت باینری متصل می‌کنیم درنتیجه والدین فرزند $A$ والدین گرۀ $A$ می‌شود.

گره با دو فرزند

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

پیمایش

پیمایش‌های پسوندی ، میانوندی و پیشوندی پیمایش‌هایی هستند که به وسیلۀ آنها می‌توان همۀ گره‌ها زیردرخت چپ ، راست و ریشه را به طور بازگشتی ملاقات کرد.

پیمایش عمق نخستین

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

پیمایش عرض نخستین

پیمایش عرض نخستین در مقایسه با عمق نخستین در این است که در این پیمایش همیشه هدف ما ملاقات نزدیکترین گرۀ ملاقات نشده به ریشه است.
در یک درخت دودویی کامل، اندیس عرض گره 1) را می‌توان به عنوان دستور العمل پیماش از ریشه مورد استفاده قرار داد. با شروع از بیت d-1 از چپ به راست می خوانیم، که $d$ در آن همان فاصلۀ گره تا ریشه است 2) و در سؤال ، گره نباید خود ریشه باشد (d>0). هنگامی که اندیس عرضی گره بیت d-1 باشد، دارای بیت ارزش $0$و$1$ است یعنی در هر مرحله به طور مرتب چپ یا راست را می‌پوشاند. فرایند پی در پی با چک کردن بیت بعدی ادامه می‌یابد تا دیگر بیتی موجود نباشد. سمت راست ترین بیت نشان‌دهندۀ پیمایش نهایی والدین گرۀ مورد نظر تا خود گره است.

درخت دودویی

در علوم رایانه، یک درخت دودویی یک ساختمان دادهٔ درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می شوند. در درخت دودویی، در جهٔ هر گره حداکثر می تواند دو باشد. درخت های دودویی برای پیاده سازی درخت جستجوی دودویی و انبوه دودویی و برای جستجوی کارآمد و مرتب سازی استفاده می شود. درخت دودویی یک درخت باینری حالت خاص از یک درخت kتایی است، که در آن k برابر ۲ است.
درخت دودویی ریشه دار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد.
درخت دودویی پر(گاهی اوقات درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودویی گفته می شود) یک درخت که در آن هر گره به غیر از برگ ها دارای دو فرزند است. هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است. یک درخت پر گاهی اوقات به طور ابهام انگیزی به عنوان درخت دودویی کامل تعریف می شود. فیزیکدانان یک درخت دودویی را به عنوان درخت دودویی پر تعریف می کنند. یک تبارنامه که روی یک درخت دودویی کامل به عمق ۴ نگاشت شده است
یک درخت دودویی کامل (perfect) یک درخت دودویی پر است که در آن همه برگ ها دارای عمق یکسان یا هم سطح باشند، و در آن هر پدری دارای دو فرزند است.(به طور مبهم درخت دودویی کامل نامیده می شود (بعدی را مشاهده کنید).) نمونه ای از یک درخت دودویی کامل را می توان در تبارنامه از یک فرد به عمق داده شده مشاهده کرد، به طوری که هر فرد دقیقاً دو پدر و مادر (یک مادر و یک پدر) دارد؛ توجه داشته باشید که این معکوس قرارداد معمول درخت پدر\ فرزند است، و این درختان خلاف جهت معمول هستند (ریشه در پایین).
یک درخت دودویی کامل (complete) یک درخت دودویی است که در آن هر سطح، به جز احتمالاً آخرین سطح، به طور کامل پر شده است، و همهٔ گره ها تا جایی که ممکن است در چپ درخت قرار می گیرند. درختی که این استثناء را داشته باشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند. این نوع درختان از ساختمان دادهٔ ویژه ای به نام هیپ استفاده می کنند.
درخت دودویی کامل نا محدود درختی است که دارای بی نهایت سطح قابل شمارش است، که در آن هر گره دارای دو فرزند است به طوری که گره های 2d در سطح d هستند. مجموعهٔ گره ها شمارای نامتناهی است، ولی مجموعه ای از بی نهایت مسیر از ریشه، ناشمارا است، که دارای عدد کاردینالیتی پیوسته است. این مسیرها رابطهٔ دوسویی را با نقاط مجموعه کانتور، یا مجموعه ای از اعداد گنگ حفظ می کند.
درختی دودویی متوازن که معمولاً به عنوان درخت دودویی است درخت باینری که در آن اختلاف عمق زیردرخت چپ و راست آن ۱ یا کمتر است، اگر چه به طور کلی درخت دودویی است که هیچ برگی نسبت با برگ های دیگر فاصلهٔ زیادی تا ریشه ندارد. (طرح توازن متمایز اجازه می دهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش بینی باشد. (بسیاری از گره ها از ریشه تا برگ پیموده می شوند، چنان که شمارهٔ ریشه به عنوان گرهٔ ۰ و بقیهٔ گره ها اعداد ۱ ۲ … n را می گیرند) این عمق (ارتفاع هم نامیده می شود) برابر قسمت صحیح (log2(n است، که در آن n تعداد گره ها در درخت متوازن است. مثلاً، برای درخت متوازنی که دارای ۱ گره است، log2(1) = ۰، در نتیجه عمق درخت برابر صفر است. برای یک درخت متوازن با ۱۰۰ گره، log2(100) = ۶٫۶۴، در نتیجه عمق درخت برابر ۶ است.
درخت منحط درختی است که هر گرهٔ والدین فقط به یک گرهٔ فرزند متصل است. این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادهٔ لیست پیوندی است.
توجه داشته باشید که اغلب در ادبیات متفاوتند، به خصوص در رابطه با معنای کلمات «کامل» و «پر».
انواع عملیات های مختلف را می توان روی درخت دودویی انجام داد. بعضی درخت باینری از عملیات ها تغیری ایجاد می کنند، درحالی که دیگر عملیات اطلاعات مفیدی را در مورد درخت برمی گرداند.
گره ها در درخت دودویی می توانند بین دو گره دیگر یا بعد از گره خارجی درج شوند. در درخت دودویی گره درج شده درخت باینری به عنوان فرزند مشخص می شود.

ساختمان داده جستجوی درخت دودویی در جاوا (Java Binary Search Tree) آموزش برنامه نویسی جاوا Java

درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

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

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

۱- مقادیر تمامی گره‌های زیردرخت راست – در صورت وجود – از مقدار گره بزرگتر هستند.

۲- مقادیر تمامی گره‌های زیردرخت چپ – در صورت وجود – از مقدار گره کوچکتر هستند.

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

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

Java Binary Search Tree

مهمترین کاربرد چنین درختی از نام آن مشخص است. این درخت با توجه به تعریف آن برای انجام عملیات جستجو مناسب است. فرض کنید در مجموعه اعداد درخت فوق به دنبال عدد ۶ هستیم. ابتدا ۶ را با مقدار گره رأس یعنی۵ مقایسه می‌کنیم. این گره، گره مورد نظر ما نیست. عدد ۶ هم از عدد ۵ بزرگتر است. در نتیجه با توجه به تعریف درخت جستجوی دودویی، مطمئن هستیم که اگر گرهی با مقدار۶ وجود داشته باشد، به طور حتم در زیردرخت راست گره ۵ است. پس به سمت راست حرکت کرده و عدد ۶ را با ۸ مقایسه می‌کنیم. باز هم به گره مطلوب نرسیدیم. اما با توجه به اینکه ۶ از ۸ کوچکتر است، به زیردرخت چپ گره ۸ مراجعه می‌کنیم. در این مرحله به گره با مقدار ۶ می‌رسیم که گره مطلوب ما است.

اگر در حین جستجو مجبور به حرکت به سمتی شدیم که زیردرختی وجود ندارد، به این معنی است که گره مورد نظر در درخت وجود ندارد.

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

Java Binary Search Tree

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

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

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

Java Binary Search Tree

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

برای مثال فرض کنید می‌خواهیم گرهی با مقدار ۷ را به درخت زیر اضافه کنیم:

و اگر گرهی با مقدار صفر درج کنیم:

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

حذف گره از درخت جستجوی دودویی

Java Binary Search Tree

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

هر گره در درخت جستجوی دودویی ممکن است در یکی از سه وضعیت زیر باشد:

۱٫گره فاقد فرزند است: یعنی گره مذکور یک برگ است. در چنین حالتی به راحتی می‌توان گره را حذف کرده و فضای مصرفی آن را آزاد کرد.

۲٫گره دارای یک فرزند است: در این حالت گره فرزند را جایگزین گره مذکور می‌کنیم. به عبارت ساده‌تر، بین والد گره و فرزند گره ارتباط مستقیم برقرار کرده و گره مطلوب را حذف می‌کنیم.

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

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

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

Java Binary Search Tree

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