![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3a/2-3-4_tree_2-node.svg/langfa-640px-2-3-4_tree_2-node.svg.png&w=640&q=50)
درخت ۲–۳-۴
درخت_۲-۳-۴ / From Wikipedia, the free encyclopedia
درخت 2-3-4
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
در علوم کامپیوتر، درخت 2-3-4(که به آن درخت 2-4 هم گفته میشود) داده ساختاری است که عموماً برای پیادهسازی فهرست ها(لیست ها) استفاده میشوند. عدد هر گره نشانگر تعداد فرزندان گره است که میتواند دو، سه یا چهار گره باشند :
- گره-2، یک مقدار و دو گره فرزند دارد
- گره-3، دو مقدار و سه گره فرزند دارد
- گره-4، سه مقدار و چهار گره فرزند دارد
درختهای 2-3-4 درخت باینری مرتبه 4 هستند و مانند درخت باینری می توانند عملیات جستجو، درج کردن و حذف کردن را در زمان (O(log n انجام دهند. یک خاصیت این درخت این است که تمامی برگها (پایینترین گره که فرزند هم ندارد) در یک ارتفاع هستند . درخت های 2-3-4 و درخت های قرمز-سیاه یک به یک هستند، به این معنا که برای هر درخت 2-3-4 فقط یک درخت قرمز-سیاه وجود دارد . عملیات درج کردن و حذف کردن روی درخت 2-3-4 موجب گسترش، جـدا شدن و ادغام گره ها میشود که معادل تعویض رنگ و جابجایی گره ها در درخت قـرمز-سیاه است . برای آشنایی با درخت قـرمز-سیاه معــمولا در ابتــدا درخت 2-3-4 معرفی میشود، چرا که در مفهوم آسانتر است. اما بدلیل حالتهای خاص در انجام عملیات روی درخت 2-3-4 پیادهسازی این درخت در بسیاری از زبانهای برنامه نویسی مشکل است. چون پیادهسازی درخت قرمز-سیاه آسانتر است به درخت 2-3-4 ترجیح داده میشود .