درخت ۲–۳

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

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

در گره ۲، ${\displaystyle X}$

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

در گره ۳، ${\displaystyle X}$

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

باید توجه داشت که همه مقادیر در گره‌های برگ وجود دارند و گره‌های داخلی فقط برای هدایت جستجو ایجاد شده‌اند. هر گره داخلی یک گره ۳(با دو یا سه فرزند) است که مقدار ${\displaystyle X}$

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

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

این کار را برای گره‌های داخلی مسیر انجام می‌دهیم تا به برگ ${\displaystyle l}$

می‌خواهیم ${\displaystyle x}$

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

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

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

برای حذف هم ابتدا باید عنصر مورد نظر مثل ${\displaystyle x}$

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

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