نمایش مبدأ برای درخت ۲–۳

در [[علوم کامپیوتر|علم رایانه]]، [[ساختمان داده]] '''درخت ۲-۳'''، یک نوع درخت جستجوی خودمتوازن است. [[درخت‌های جستجوی دودویی]] ممکن است با درج‌ها و حذف‌های گوناگون، حالت توازن خود را از دست بدهند.  حالتی را در نظر بگیرید که یک [[درخت دودویی جستجو]] دارید و n داده را که اتفاقاً از کوچک به بزرگ مرتب هستند به ترتیب در آن درج می‌کنید. در این حالت، این درخت عملاً به یک [[لیست پیوندی]] تبدیل می‌شود که جستجو در آن از مرتبه <math> (O(n </math> است و گذشته از این که مزیت استفاده از د.د.ج (درخت دودویی جستجو) از بین رفته، مقدار زیادی حافظه هم با اختصاص دادن به اشاره‌گرهای تهی از دست می‌رود. پیاده‌سازی توابع درج و حذف درخت ۲-۳ به گونه‌ای است که این درخت طی درج‌ها و حذف‌ها به صورت متوازن باقی می‌ماند.

== ویژگی‌ها ==
درخت ۲-۳ سه نوع گره دارد:
#گره برگ که فقط یک مقدار دارد.
#گرهِ ۲
#گرهِ ۳
[[پرونده:2-node.png|بندانگشتی|150px|چپ|گره ۲]] 
در گره ۲، <math>X</math> مقدار گره، <math>L</math> زیردرخت سمت چپ و <math>R</math> زیردرخت راست گره است. هر گره ۲ باید خصوصیات زیر را داشته باشد:
* هر مقدار در <math>L</math> باید کوچک‌تر از <math>X</math> باشد.
* هر مقدار در <math>R</math> باید بزرگ‌تر از <math>X</math> باشد.
* طول مسیرها از ریشه به برگ‌های هریک از زیردرخت‌ها باید یکسان باشد.
[[پرونده:3-node.png|بندانگشتی|150px|چپ|گره ۳]] 
در گره ۳، <math>X</math> مقدار گره، <math>L</math> زیردرخت سمت چپ، <math>M</math> زیردرخت میانی و <math>R</math> زیردرخت راست گره است. هر گره ۳ باید خصوصیات زیر را داشته باشد:
* هر مقدار در <math>L</math> باید کوچک‌تر از <math>X</math> باشد.
*هر مقدار در <math>R</math> باید بزرگ‌تر از <math>X</math> و کوچک‌تر از <math>Y</math>باشد.
*هر مقدار در <math>R</math> باید بزرگ‌تر از <math>Y</math> باشد.
*طول مسیرها از ریشه به برگ‌های هریک از زیردرخت‌ها باید یکسان باشد.
باید توجه داشت که همه مقادیر در گره‌های برگ وجود دارند و گره‌های داخلی فقط برای هدایت جستجو ایجاد شده‌اند. هر گره داخلی یک گره ۳(با دو یا سه فرزند) است که مقدار <math>X</math> آن برابر با '''کوچک‌ترین مقدار موجود در زیردرخت دوم''' و مقدار <math>Y</math> آن (در صورت وجود) برابر با '''کوچک‌ترین مقدار موجود در زیردرخت سوم''' است.

== جستجو ==
همان‌طور که گفته‌شد اطلاعات ذخیره‌شده در گره‌های داخلی باعث آسان‌شدن جستجو می‌شود. فرض کنید می‌خواهیم عنصر <math>n</math> را جستجو کنیم. از ریشه شروع می‌کنیم و به ترتیب زیر به سمت [[برگ (نظریه گراف)|برگ‌ها]] می‌رویم:
* اگر <math>n</math> کوچک‌تر از مقدار<math> X</math> ریشه بود به[[زیردرخت]] چپ می‌رویم.
* (درصورتی که دو زیر درخت داشته باشیم) اگر <math>n</math> بزرگ‌تر از مقدار <math>X</math> [[ریشه (نظریه گراف)|ریشه]] بود به زیردرخت راست می‌رویم.
*اگر <math>n</math> بزرگ‌تر از مقدار <math>X</math> ریشه و کوچک‌تر از <math>Y</math> آن بود به زیردرخت میانه می‌رویم.
*اگر <math>n</math> بزرگ‌تر از مقدار <math>Y</math> ریشه بود به زیردرخت راست می‌رویم.
این کار را برای گره‌های داخلی مسیر انجام می‌دهیم تا به برگ <math>l</math> برسیم. اگر <math>n=l</math>، جستجو موفق و در غیر این صورت ناموفق است.

== درج در درخت ۲-۳ ==
می‌خواهیم <math>x</math> را در درخت ۲-۳ درج کنیم.
ابتدا باید <math>x</math> را جستجو کنیم. اگر این جستجو ناموفق باشد به عنصری مثل <math>a</math> می‌رسیم که انتظار داشتیم پدر <math>x</math> باشد. حال دو حالت پیش می‌آید:
* <math>a</math> دو فرزند دارد که در این حالت <math>x</math> را به عنوان فرزند سوم <math>a</math> در جای مناسب آن درج می‌کنیم و تغییرات لازم را در گره‌های داخلی اعمال می‌کنیم.
* <math>a</math> سه فرزند دارد و درج چهار فرزند برای <math>a</math> مجاز نیست. یک برادر سمت چپ مثل <math>b</math> برای <math>a</math> ایجاد می‌کنیم دو فرزند کوچک‌تر را فرزند آن قرار می‌دهیم. <math>b</math> را هم به صورت بازگشتی در سطح بالاتر درخت درج می‌کنیم.

به عنوان یک مثال می‌خواهیم عنصر x=۵ را در درخت زیر درج کنیم.
[[پرونده:two-threeInsertion.png|بندانگشتی|وسط|200px|درج در درخت ۲-۳]]
درخت حاصل به شکل زیر خواهد بود:
[[پرونده:two-three-Insertion.png|بندانگشتی|وسط|200px|درج در درخت ۲-۳]]

== حذف از درخت ۲-۳ ==
برای حذف هم ابتدا باید عنصر مورد نظر مثل <math>x</math> را جستجو، پیدا و آن را حذف کنیم. اگر <math>a</math> پدر <math>x</math> باشد دو حالت وجود دارد:
*دو فرزند برای <math>a</math> باقی‌مانده‌است. که در این صورت حذف پایان یافته و نیاز به عمل دیگری نیست.
*تنها یک فرزند دیگر برای <math>a</math> باقی‌مانده‌است که آن را <math>b</math> می‌نامیم. در این حالت، اگر <math>a</math> ریشه باشد آن را حذف و <math>b</math> را ریشه قرار می‌دهیم. در غیر این صورت باید از عموهای <math>b</math> کمک بگیریم. بدین ترتیب که اگر یکی از آن‌ها سه فرزند داشته باشند فرزند مناسب آن را به <math>a</math> می‌دهیم تا هر دو دو فرزند داشته باشند. ولی اگر هر دو عموی <math>b</math> دو فرزند داشته باشند این بار <math>b</math> را به یکی از آن‌ها می‌دهیم و به طور بازگشتی <math>a</math> را از درخت حذف می‌کنیم.
== نگارخانه ==
<gallery>
Image:2-3-4 tree 2-node.svg|<!--2 node-->
Image:2-3-4-tree 3-node.svg|<!--3 node-->
</gallery>

== منابع ==
{{پانویس}}
* قدسی، محمد. ''داده‌ساختارها و مبانی الگوریتم‌ها''. تهران : موسسه فرهنگی فاطمی ، ۱۳۸۸ {{شابک|978-964-318-549-7}}.
{{چپ‌چین}}
* [https://web.archive.org/web/20100717051254/http://cs.wellesley.edu/~cs230/fall02/2-3-trees.pdf Prof. Lyn Turbak- CS۲۳۰- Data Structures- Computer Science- Wellesley College]
*[https://web.archive.org/web/20131008062759/http://www.cs.ucr.edu/cs14/cs14_06win/slides/2-3_trees_covered.pdf Ann Gordon-Ross- Introduction to Data Structures And Algorithms- Computer Science and Engineering- Bourns College of Engineering]
{{پایان چپ‌چین}}
{{درخت‌ها در علوم کامپیوتر}}

[[رده:درخت بی]]
[[رده:ساختمان داده]]
[[رده:جستجوی درخت‌ها]]
[[رده:داده ساختارهای استهلاکی]]