درخت ۲–۳

در علم رایانه، ساختمان داده درخت ۲-۳، یک نوع درخت جستجوی خودمتوازن است. درخت‌های جستجوی دودویی ممکن است با درج‌ها و حذف‌های گوناگون، حالت توازن خود را از دست بدهند. حالتی را در نظر بگیرید که یک درخت دودویی جستجو دارید و 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$ را از درخت حذف می‌کنیم.

نگارخانه

• 
• 

منابع

• قدسی، محمد. داده‌ساختارها و مبانی الگوریتم‌ها. تهران : موسسه فرهنگی فاطمی ، ۱۳۸۸ شابک ‎۹۷۸−۹۶۴−۳۱۸−۵۴۹−۷.

• 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