درخت ۲-۳

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

ویژگی‌ها

درخت ۲-۳ سه نوع گره دارد:

1. گره برگ که فقط یک مقدار دارد.
2. گرهِ ۲
3. گرهِ ۳

گره ۲

در گره ۲، $X$ مقدار گره، $L$ زیردرخت سمت چپ و $R$ زیردرخت راست گره است. هر گره ۲ باید خصوصیات زیر را داشته باشد:

• هر مقدار در $L$ باید کوچک‌تر از $X$ باشد.
• هر مقدار در $R$ باید بزرگ‌تر از $X$ باشد.
• طول مسیرها از ریشه به برگ‌های هریک از زیردرخت‌ها باید یکسان باشد.

گره ۳

در گره ۳، $X$ مقدار گره، $L$ زیردرخت سمت چپ، $M$ زیردرخت میانی و $R$ زیردرخت راست گره است. هر گره ۳ باید خصوصیات زیر را داشته باشد:

• هر مقدار در $L$ باید کوچک‌تر از $X$ باشد.
• هر مقدار در $R$ باید بزرگ‌تر از $X$ و کوچک‌تر از $Y$باشد.
• هر مقدار در $R$ باید بزرگ‌تر از $Y$ باشد.
• طول مسیرها از ریشه به برگ‌های هریک از زیردرخت‌ها باید یکسان باشد.

باید توجه داشت که همه مقادیر در گره‌های برگ وجود دارند و گره‌های داخلی فقط برای هدایت جست‌وجو ایجاد شده‌اند. هر گره داخلی یک گره ۳(با دو یا سه فرزند) است که مقدار $X$ آن برابر با کوچک‌ترین مقدار موجود در زیردرخت دوم و مقدار $Y$ آن (در صورت وجود) برابر با کوچک‌ترین مقدار موجود در زیردرخت سوم است.

جست‌وجو

همان‌طور که گفته‌شد اطلاعات ذخیره‌شده در گره‌های داخلی باعث آسان‌شدن جست‌وجو می‌شود. فرض کنید می‌خواهیم عنصر $n$ را جست‌وجو کنیم. از ریشه شروع می‌کنیم و به ترتیب زیر به سمت برگ‌ها می‌رویم:

• اگر $n$ کوچک‌تر از مقدار$X$ ریشه بود بهزیردرخت چپ می‌رویم.
• (درصورتی که دو زیر درخت داشته باشیم) اگر $n$ بزرگ‌تر از مقدار $X$ ریشه بود به زیردرخت راست می‌رویم.
• اگر $n$ بزرگ‌تر از مقدار $X$ ریشه و کوچک‌تر از $Y$ آن بود به زیردرخت میانه می‌رویم.
• اگر $n$ بزرگ‌تر از مقدار $Y$ ریشه بود به زیردرخت راست می‌رویم.

این کار را برای گره‌های داخلی مسیر انجام می‌دهیم تا به برگ $l$ برسیم. اگر $n=l$، جست‌وجو موفق و در غیر این صورت ناموفق است.

درج در درخت ۲-۳

می‌خواهیم $x$ را در درخت ۲-۳ درج کنیم. ابتدا باید $x$ را جست‌وجو کنیم. اگر این جست‌وجو ناموفق باشد به عنصری مثل $a$ می‌رسیم که انتظار داشتیم پدر $x$ باشد. حال دو حالت پیش می‌آید:

• $a$ دو فرزند دارد که در این حالت $x$ را به عنوان فرزند سوم $a$ در جای مناسب آن درج می‌کنیم و تغییرات لازم را در گره‌های داخلی اعمال می‌کنیم.
• $a$ سه فرزند دارد و درج چهار فرزند برای $a$ مجاز نیست. یک برادر سمت چپ مثل $b$ برای $a$ ایجاد می‌کنیم دو فرزند کوچک‌تر را فرزند آن قرار می‌دهیم. $b$ را هم به صورت بازگشتی در سطح بالاتر درخت درج می‌کنیم.

به عنوان یک مثال می‌خواهیم عنصر x=۵ را در درخت زیر درج کنیم.

درج در درخت ۲-۳

درخت حاصل به شکل زیر خواهد بود:

درج در درخت ۲-۳

حذف از درخت ۲-۳

برای حذف هم ابتدا باید عنصر مورد نظر مثل $x$ را جست‌وجو، پیدا و آن را حذف کنیم. اگر $a$ پدر $x$ باشد دو حالت وجود دارد:

• دو فرزند برای $a$ باقی مانده‌است. که در این صورت حذف پایان یافته و نیاز به عمل دیگری نیست.
• تنها یک فرزند دیگر برای $a$ باقی‌مانده‌است که آن را $b$ می‌نامیم. در این حالت، اگر $a$ ریشه باشد آن را حذف و $b$ را ریشه قرار می‌دهیم. در غیر این صورت باید از عموهای $b$ کمک بگیریم. بدین ترتیب که اگر یکی از آن‌ها سه فرزند داشته باشند فرزند مناسب آن را به $a$ می‌دهیم تا هر دو دو فرزند داشته باشند. ولی اگر هر دو عموی $b$ دو فرزند داشته باشند این بار $b$ را به یکی از آن‌ها می‌دهیم و به طور بازگشتی $a$ را از درخت حذف می‌کنیم.

نگارخانه

• 
• 

منابع

• قدسی، محمد. داده‌ساختارها و مبانی الگوریتم‌ها. تهران : موسسه فرهنگی فاطمی ، ۱۳۸۸ ISBN 978-964-318-549-7.

• Prof. Lyn Turbak- CS۲۳۰- Data Structures- Computer Science- Wellesley College
• Ann Gordon-Ross- Introduction to Data Structures And Algorithms- Computer Science and Engineering- Bourns College of Engineering