نوعی ساختار داده در علوم رایانه From Wikipedia, the free encyclopedia
در علوم رایانه، یک درخت دودویی یک ساختمان دادهٔ درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده میشوند. در درخت دودویی، در جهٔ هر گره حداکثر میتواند دو باشد. درختهای دودویی برای پیادهسازی درخت جستجوی دودویی و انبوه دودویی و برای جستجوی کارآمد و مرتبسازی استفاده میشود. درخت دودویی یک حالت خاص از یک درخت kتایی است، که در آن k برابر ۲ است.
توجه داشتهباشید که اغلب در ادبیات متفاوتند، به خصوص در رابطه با معنای کلمات «کامل» و «پر».
انواع عملیاتهای مختلف را میتوان روی درخت دودویی انجام داد. بعضی از عملیاتها تغیری ایجاد میکنند، درحالی که دیگر عملیات اطلاعات مفیدی را در مورد درخت برمیگرداند.
گرهها در درخت دودویی میتوانند بین دو گره دیگر یا بعد از گره خارجی درج شوند. در درخت دودویی گره درج شده به عنوان فرزند مشخص میشود.
گره خارجی اضافه شده گره A است، برای اضافه کردن یک گره بعد از گره A، گره A گره جدید را به عنوان فرزند مشخص خود میکند و گره جدید گره A را به عنوان گره والد تعیین میکند.
درج در گرههای داخلی پیچیدهتر از گرههای خارجی است. فرض میکنیم که A گرهٔ داخلی و B فرزند گرهٔ A باشد. (اگر درج در قسمت فرزند راست باشد، آنگاه B فرزند سمت راست A است، برای درج فرزند سمت چپ هم همینطور است) A فرزند جدید را مشخص میکند و گرهٔ جدید A را که والدین آن است مشخص میکند.
حذف فرآیندی است که یک گره را از درخت حذف میکند. فقط میتوان گرههای خاصی را در درخت دودویی به وضوح حذف کرد.[5]
فرض کنید گرهای که میخواهیم حذف کنیم گرهٔ A باشد. اگر گره بدون فرزند باشد (گرۀ خارجی)، آنگاه فرزند والدین گرهٔ A تهی میشود. اگر دارای یک فرزند باشد، آنگاه فرزند A را به والدین گرهٔ A متصل میکنیم در نتیجه والدین فرزند A والدین گرهٔ A میشود.
در یک درخت دودویی نمیتوان گرهای که دارای دو فرزند است را به وضوح حذف کرد.[5] اگر چه، در درخت دودویی (شامل درخت جستجوی دودویی) این گرهها قابل حذف هستند، ولی با ترمیم ساختمان درخت همراه است.
پیمایشهای پسوندی، میانوندی و پیشوندی پیمایشهایی هستند که به وسیلهٔ آنها میتوان همهٔ گرهها زیردرخت چپ، راست و ریشه را بهطور بازگشتی ملاقات کرد.
در پیمایش عمق نخستین، همیشه قصد ما ملاقات دورترین گرهٔ ممکن از گرهٔ ریشه است، ولی با این آگاهی که آن گره باید فرزند گرهای باشد که در حال حاضر ملاقات شدهاست. برعکس در جستجوی عمق نخستین گرافها، احتیاجی به بخاطر سپردن گرههایی که قبلاً ملاقات شدهاند نیست، زیرا یک درخت نمیتواند دارای دور باشد. پیمایش پیشوندی یک مورد خاص آن است. برای اطلاعات بیشتر به الگوریتم جستجوی عمق اول مراجعه کنید.
پیمایش عرض نخستین در مقایسه با عمق نخستین در این است که در این پیمایش همیشه هدف ما ملاقات نزدیکترین گرهٔ ملاقات نشده به ریشه است. برای اطلاعات بیشتر به الگوریتم جستجوی اول سطح مراجعه کنید.
در یک درخت دودویی کامل، اندیس عرض گره ((i - (2d - 1)) را میتوان به عنوان دستور العمل پیماش از ریشه مورد استفاده قرار داد. با شروع از بیت d-1 از چپ به راست میخوانیم، که d در آن همان فاصلهٔ گره تا ریشه است ((d = floor(log2(i+1)) و در سؤال، گره نباید خود ریشه باشد (d>0). هنگامی که اندیس عرضی گره بیت d-1 باشد، دارای بیت ارزش 0 و1 است یعنی در هر مرحله بهطور مرتب چپ یا راست را میپوشاند. فرایند پی در پی با چک کردن بیت بعدی ادامه مییابد تا دیگر بیتی موجود نباشد. سمت راستترین بیت نشاندهندهٔ پیمایش نهایی والدین گرهٔ مورد نظر تا خود گره است.
در نظریه نوعها، در یک درخت دودویی با گرههایی از نوع A، بهصورت استقراء تعریف میشوند: .TA = μα. 1 + A × α × α
برای هر ساختمان دادهٔ درخت دودویی، ریشه در درخت دودویی معادل ریشه در نظریهٔ گراف است. در نظریههای گراف از تعاریف استفاده میشود: درخت دودویی گرافی همبند بدون دور است که درجهٔ هر رأس آن حداکثر سه است، که آن میتواند هر درخت دودویی با دو یا چند گره را نمایش دهد، دقیقاً بهازای هر گرهٔ درجه سه دو یا بیشتر گرهٔ درجهٔ یک وجود دارد، ولی دارای هر تعداد از گرهٔ درجه دو است. درخت دودویی ریشهدار مانند گرافی است که درجهٔ یکی از رئوس آن بیش از دو نیست در واقع بیش از دو گرهٔ تنها ندارد؛ بنابراین به وسیلهٔ ریشه، انتخاب هر رأس به عنوان والدین و دو فرزند آن منحصربهفرد تعریف شدهاست، با این حال، اطلاعات کافی برای تشخیص فرزند چپ یا راست وجود دارد. اگر ما به ارتباط کمتری نیاز داشتهباشیم گراف این امکان را به ما میدهد که از مؤلفههای همبندی استفاده کنیم. ما به چنین ساختاری جنگل میگوییم. راه دیگر تعریف درخت دودویی، تعریف بازگشتی روی گرافهای مستقیم است.
بهعلاوه این راه طرز رسیدن به فرزندان را تعین نمیکند، ولی جای خاص ریشه را درست میکند.
درختان دودویی را میتوان با راههای متفاوتی به وسیلهٔ زبان برنامهنویسی اولیه ایجاد کرد.
در یک زبان با سوابق و منابع، درختان دودویی معمولاً به وسیلهٔ یک ساختار گرهٔ درخت که حاوی برخی دادهها و مراجع در فرزند چپ و راست آن است ساخته میشوند. گاهی آن گره نیز حاوی یک مرجع به والدین منحصربهفرد خود است. اگر یک گره کمتر از دو فرزند داشتهباشد، ممکن است برخی اشارهگرهای فرزندان ارزش تهی خاصی را قرار دهند، یا اشارهگرها به گرۀ نگهبان خاصی اشاره کنند. در زبانهای برنامهنویسی با اجتماع برچسبها مانند زبان ML، یک گرهٔ درخت معمولاً از اجتماع برچسب دو نوع گره است، که یکی از آنها دارای دادهای ۳تایی، فرزند چپ و فرزند راست، و یکی دیگر از آنها گرهٔ برگ است، که شامل هیچ داده و تابعی ناست مانند ساختن مقدار تهی به وسیلهٔ اشارهگرها در زبان برنامهنویسی.
درختان دودویی نیز میتوانند با پیمایش عرض نخستین مانند ساختمان دادۀ مجازی در آرایهها ذخیره شوند، و اگر درخت دودویی کامل باشد در این روش هیچ فاصلهٔ زائدی ایجاد نمیشود. بهطور خلاصه، اگر گرهای دارای اندیس i باشد، آنگاه اندیس فرزند چپ آن و اندیس فرزند راست آن میشود، حال با داشتن اندیس هر کدام از فرزندان اندیس والدین به صورت بهدست میآید (با فرض اینکه اندیس ریشه صفر باشد). در این روش هر چه ذخیرهسازی فشردهتر باشد و محل ارجاع بهتر باشد مفیدتر است، بهخصوص در پیماش پیشوندی. اگرچه، رشد کردن درخت دارای هزینه است، که این فاصلهٔ زائد متناسب با h - n>2 است که در آن h عمق درخت و n تعداد گرهها است. این روش ذخیرهسازی معمولاً برای هرم دودویی استفاده میشود، و هیچ فضایی ازبین نمیرود چون گرهها به صورت عرض نخستین اضافه میشوند.
داده ساختارهای فشرده که فضای اشغال شده را تا حد ممکن کوچک میکند، و به عنوان کران پایین در نظریه اطلاعات تأسیس شدهاست. تعداد درختان دودویی متفاوت روی گره است. روی اعداد کاتالان است (با فرض اینکه ما درختان با ساختار یکسان را مشابه مشاهده میکنیم) برای بزرگ آن برابر است؛ به این ترتیب ما به حداقل آن نیاز داریم که تقریباً برابر بیت در کدگذاری آن است؛ بنابراین یک درخت دودویی فضا را اشغال میکند. یک نمایش ساده برای ملاقات گرههای درخت در پیمایش پیشوندی این است که خروجی عدد "۱" نشاندهندهٔ گرهٔ داخلی و عدد " ۰" نشاندهندهٔ برگ است. اگر درخت شامل داده باشد، میتوانیم به سادگی بهطور همزمان دادهها را با پیمایش پیشوندی در آرایههای پیدرپی ذخیره کنیم. تابع مورد نظر به صورت زیر است:
function EncodeSuccinct(node n, bitstring structure, array data) { if n = nil then append 0 to structure; else append 1 to structure; append n.data to data; EncodeSuccinct(n.left, structure, data); EncodeSuccinct(n.right, structure, data); }
در پایان ساختار رشتهای فقط دارای بیت است، که n در آن تعداد گرههای داخلی است؛ ما هیچ وقت عمق را ذخیره نمیکنیم. این نشان میدهد که هیچ اطلاعاتی از دست نمیرود، ما میتوانیم بااستفاده از کد زیر خروجی را به درخت اصلی تبدیل کنیم:
function DecodeSuccinct(bitstring structure, array data) { remove first bit of structure and put it in b if b = 1 then create a new node n remove first element of data and put it in n.data n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data) return n else return nil }
یک نگاشت یک به یک بین مدل معمولی درختان و درختان دودویی وجود دارد؛ که معمولاً این تبدیل توسط زبان لیسپ انجام میشود. برای تبدیل درخت معمولی به مدل معمولی آن، تنها نیاز داریم که مسیر فرزندان درخت معمولی را نشان دهیم، در نتیجه درخت بهطور خودکار به درخت دودویی تبدیل میشود. هر گره مانند N در درخت مورد نظر با گرهٔ 'N در درخت دودویی با هم رابطه دارند بهطوری که: فرزند چپ 'N همان اولین فرزند گرهٔ N است، و فرزند راست 'N همان برادر (خواهر) گرهٔ N است، گرهٔ بعدی از میان فرزندانی است که والدین آنها N است. این درخت دودویی، درخت بررسی شده معمولی را نشان میدهد که گاهی نیز به درخت دودویی فرزند-چپ همزاد- راست (درخت LCRS) یا درخت مضاعف زنجیر وار یا زنجیر ارث بری فرزندان مقایسه میکند. یکی از راههای فکر کردن در این مورد این است که هر یک از گرههای فرزند در (لیست پیوندی) قرار گیرند. برای مثال، در درخت سمت چپ، A دارای ۶ فرزند است {B,C,D,E,F,G}، که میتوان این درخت را به درخت دودویی سمت راست تبدیل کرد.
درخت دودویی را میتوان به مدل اصلی خودش برگرداند، گرهٔ متصل به یال سیاه رنگ سمت چپ نشاندهندهٔ فرزند اول آن است و گرههای متصل به یالهای آبی رنگ سمت راست آن نشاندهندهٔ برادر (خواهر) آن است. برگهای آن در سمت چپ قرار دارد که در لیسپ به صورت زیر است: (((N O) I J) C D ((P)(Q)) F (M))
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.