تفاوت کلیدی – درخت دودویی در مقابل درخت جستجوی باینری
ساختار داده روشی سیستماتیک برای سازماندهی داده ها به منظور استفاده کارآمد از آن است. ترتیب داده ها با استفاده از ساختار داده باید زمان اجرا یا زمان اجرا را کاهش دهد. همچنین، ساختار داده باید به حداقل مقدار حافظه نیاز داشته باشد. گاهی اوقات داده ها را می توان در یک ساختار درختی مرتب کرد. یک درخت نشان دهنده گره ای است که توسط لبه ها متصل شده است. بالاترین گره ریشه است. هر گره می تواند حداکثر دو گره داشته باشد. آنها به عنوان گره های کودک شناخته می شوند. گره سمت چپ گره والد، گره فرزند چپ است در حالی که گره سمت راست گره والد، گره سمت راست است. Binary Tree و Binary Search Tree دو ساختار داده درختی هستند. درخت باینری نوعی ساختار داده است که در آن هر گره والد حداکثر می تواند دو گره فرزند داشته باشد. درخت جستجوی دودویی یک درخت دودویی است که در آن فرزند سمت چپ فقط شامل گره هایی با مقادیر کمتر یا مساوی با گره والد است و فرزند سمت راست فقط شامل گره هایی با مقادیر بیشتر از گره والد است. این تفاوت کلیدی است. برخلاف ساختارهای داده‌ای مانند آرایه‌ها، درخت باینری و درخت جستجوی باینری محدودیت بالایی برای ذخیره داده‌ها ندارند.
درخت باینری چیست؟
هنگامی که داده ها را در ساختار درختی مرتب می کنیم، گره بالای درخت به عنوان گره ریشه شناخته می شود. برای کل درخت فقط یک ریشه می تواند وجود داشته باشد. هر گره به جز گره ریشه یک یال به سمت بالا تا یک گره دارد. به آن گره والد می گویند. گره زیر کد والد، گره فرزند آن نامیده می شود. هر گره والد می تواند حداکثر دو گره فرزند داشته باشد. آنها به عنوان گره فرزند چپ و گره فرزند راست نامیده می شوند.گره بدون گره فرزند را گره برگ می نامند. روش خاصی برای مرتب کردن داده ها در درخت باینری وجود ندارد. یک مسیر از گره ریشه به هر گره وجود دارد.
شکل 01: مثالی از درخت باینری
در بالا نمونه ای از درخت دودویی است. عنصر 2، در بالای درخت، ریشه است. هر گره حداکثر دو گره دارد. اگر یک درخت حاوی هر حلقه باشد یا اگر یک گره دارای بیش از دو گره باشد، نمی توان آن را به عنوان یک درخت باینری طبقه بندی کرد. برای رفتن از یک گره به گره دیگر، همیشه یک مسیر وجود دارد. گره های فرزند گره ریشه 2 7 و 5 هستند.همچنین ممکن است یک گره بدون گره باشد. اما هر گره ای نمی تواند بیش از دو گره داشته باشد. عنصر سمت راست ریشه 5 است. آن عنصر 5 گره والد برای گره فرزند 9 است. گره 4 و 11 هیچ عنصر فرزندی ندارند. بنابراین، آنها گره های برگ هستند.
درخت باینری برای ذخیره داده ها به ترتیب سلسله مراتبی استفاده می شود. این شبیه به ساختار فایل کامپیوتر است. ساختار داده مانند یک آرایه می تواند مقدار خاصی از داده را ذخیره کند. اما در یک درخت باینری، هیچ محدودیتی برای تعداد گره‌ها وجود ندارد.
درخت جستجوی باینری چیست؟
درخت جستجوی باینری یک ساختار داده درختی باینری است. مشابه درخت باینری، درخت جستجوی باینری نیز می تواند دو گره داشته باشد. هر گره به جز گره ریشه یک یال به سمت بالا تا یک گره دارد. به آن گره والد می گویند. گره زیر یک داده که با لبه آن به سمت پایین متصل می شود، گره فرزند آن نامیده می شود. گره بدون گره فرزند را گره برگ می نامند. هر گره والد می تواند حداکثر دو گره داشته باشد.گره های فرزند وجود دارند که به گره فرزند چپ و گره فرزند راست اشاره می کنند. بالاترین عنصر گره ریشه نام دارد. فرزند سمت چپ فقط شامل گره هایی با مقادیر کمتر یا مساوی با گره والد است. فرزند سمت راست فقط شامل گره هایی با مقادیر بزرگتر یا مساوی با گره والد است.
شکل 02: مثالی از درخت جستجوی باینری
عنصر 8 بالاترین عنصر است. بنابراین، گره ریشه است. اگر 3 یک گره والد است، 1 و 6 گره های فرزند هستند. 1 گره فرزند سمت چپ است در حالی که 6 گره فرزند سمت راست است.فرزند سمت چپ حاوی مقادیر کمتر یا مساوی با گره والد است. وقتی 3 گره والد است، سمت چپ باید عنصری داشته باشد که کمتر یا مساوی 3 باشد. در این مثال، 1 است. فرزند سمت راست فقط شامل گره هایی با مقادیر بیشتر از گره والد است. هنگامی که 3 گره والد است، گره فرزند سمت راست باید مقداری بالاتر از 3 داشته باشد. در این مثال، آن 6 است. به همین ترتیب، ترتیب خاصی برای مرتب کردن هر عنصر داده یک درخت جستجوی باینری وجود دارد. این یک ساختار داده است که روشی کارآمد برای انجام مرتب‌سازی، بازیابی و جستجوی داده‌ها فراهم می‌کند.
شباهت‌های بین درخت باینری و درخت جستجوی باینری چیست؟
- هر دو درخت باینری و درخت جستجوی دودویی ساختارهای داده سلسله مراتبی هستند.
- درخت باینری و درخت جستجوی دودویی ریشه دارند.
- هر دو درخت باینری و درخت جستجوی دودویی می توانند حداکثر دو گره فرزند داشته باشند.
تفاوت بین درخت باینری و درخت جستجوی باینری چیست؟
درخت باینری در مقابل درخت جستجوی دودویی |
|
| درخت باینری نوعی ساختار داده است که در آن هر گره والد می تواند حداکثر دو گره فرزند داشته باشد. | درخت جستجوی دودویی یک درخت باینری است که در آن فرزند سمت چپ فقط شامل گره هایی با مقادیر کمتر یا مساوی با گره والد است و در آن فرزند سمت راست فقط شامل گره هایی با مقادیر بیشتر از گره والد است. |
| سفارش تنظیم داده | |
| یک درخت باینری نظم خاصی برای ترتیب دادن عناصر داده ندارد. | یک درخت جستجوی باینری دارای نظم خاصی برای ترتیب دادن عناصر داده است. |
| استفاده | |
| یک درخت باینری به عنوان جستجوی کارآمد داده ها و اطلاعات در ساختار درختی استفاده می شود. | یک درخت جستجوی دودویی برای درج، حذف و جستجوی داده ها استفاده می شود. |
خلاصه - درخت دودویی در مقابل درخت جستجوی دودویی
ساختار داده راهی برای سازماندهی داده ها است. گاهی اوقات داده ها را می توان در یک ساختار درختی مرتب کرد. دو مورد از آنها درخت باینری و درخت جستجوی دودویی هستند. این مقاله تفاوت بین درخت باینری و درخت جستجوی باینری را مورد بحث قرار داد. درخت باینری نوعی ساختار داده است که در آن هر گره والد حداکثر می تواند دو گره فرزند داشته باشد. درخت جستجوی دودویی یک درخت باینری است که در آن فرزند سمت چپ فقط شامل گره هایی با مقادیر کمتر یا مساوی با گره والد است و در آن فرزند سمت راست فقط شامل گره هایی با مقادیر بیشتر از گره والد است.
دانلود PDF درخت باینری در مقابل درخت جستجوی باینری
می توانید نسخه PDF این مقاله را دانلود کنید و طبق یادداشت استنادی از آن برای اهداف آفلاین استفاده کنید. لطفاً نسخه PDF را از اینجا دانلود کنید: تفاوت بین درخت باینری و درخت جستجوی باینری
