From Wikipedia, the free encyclopedia
در علم رایانه، ساختمان داده درخت ۲-۳، یک نوع درخت جستجوی خودمتوازن است. درختهای جستجوی دودویی ممکن است با درجها و حذفهای گوناگون، حالت توازن خود را از دست بدهند. حالتی را در نظر بگیرید که یک درخت دودویی جستجو دارید و n داده را که اتفاقاً از کوچک به بزرگ مرتب هستند به ترتیب در آن درج میکنید. در این حالت، این درخت عملاً به یک لیست پیوندی تبدیل میشود که جستجو در آن از مرتبه است و گذشته از این که مزیت استفاده از د.د.ج (درخت دودویی جستجو) از بین رفته، مقدار زیادی حافظه هم با اختصاص دادن به اشارهگرهای تهی از دست میرود. پیادهسازی توابع درج و حذف درخت ۲-۳ به گونهای است که این درخت طی درجها و حذفها به صورت متوازن باقی میماند.
درخت ۲-۳ سه نوع گره دارد:
در گره ۲، مقدار گره، زیردرخت سمت چپ و زیردرخت راست گره است. هر گره ۲ باید خصوصیات زیر را داشته باشد:
در گره ۳، مقدار گره، زیردرخت سمت چپ، زیردرخت میانی و زیردرخت راست گره است. هر گره ۳ باید خصوصیات زیر را داشته باشد:
باید توجه داشت که همه مقادیر در گرههای برگ وجود دارند و گرههای داخلی فقط برای هدایت جستجو ایجاد شدهاند. هر گره داخلی یک گره ۳(با دو یا سه فرزند) است که مقدار آن برابر با کوچکترین مقدار موجود در زیردرخت دوم و مقدار آن (در صورت وجود) برابر با کوچکترین مقدار موجود در زیردرخت سوم است.
همانطور که گفتهشد اطلاعات ذخیرهشده در گرههای داخلی باعث آسانشدن جستجو میشود. فرض کنید میخواهیم عنصر را جستجو کنیم. از ریشه شروع میکنیم و به ترتیب زیر به سمت برگها میرویم:
این کار را برای گرههای داخلی مسیر انجام میدهیم تا به برگ برسیم. اگر ، جستجو موفق و در غیر این صورت ناموفق است.
میخواهیم را در درخت ۲-۳ درج کنیم. ابتدا باید را جستجو کنیم. اگر این جستجو ناموفق باشد به عنصری مثل میرسیم که انتظار داشتیم پدر باشد. حال دو حالت پیش میآید:
به عنوان یک مثال میخواهیم عنصر x=۵ را در درخت زیر درج کنیم.
درخت حاصل به شکل زیر خواهد بود:
برای حذف هم ابتدا باید عنصر مورد نظر مثل را جستجو، پیدا و آن را حذف کنیم. اگر پدر باشد دو حالت وجود دارد:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.