درخت دودویی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک درخت دودویی ساده با ۹ گره و ارتفاع ۳، در این درخت گره شماره ۲ ریشه است. این درخت غیر متوازن و تامرتب است.

در علوم رایانه، یک درخت دودویی یک ساختمان دادهٔ درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می‌شوند. در درخت دودویی، در جهٔ هر گره حداکثر می‌تواند دو باشد. درخت‌های دودویی برای پیاده‌سازی درخت جستجوی دودویی و انبوه دودویی و برای جستجوی کارآمد و مرتب‌سازی استفاده می‌شود. درخت دودویی یک حالت خاص از یک درخت kتای است، که در آن k برابر ۲ می‌باشد.

انواع درختان دودویی[ویرایش]

چرخش درخت عملیات بسیار رایج روی درختان دودویی خود متعادل است.
  • درخت دودویی ریشه‌دار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد.
  • درخت دودویی پر(گاهی اوقات درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودویی گفته می‌شود) یک درخت که در آن هر گره به غیر از برگ‌ها دارای دو فرزند است. هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است. یک درخت پر گاهی‌اوقات به‌طور ابهام‌انگیزی به عنوان درخت دودویی کامل تعریف می‌شود. فیزیکدانان یک درخت دودویی را به‌عنوان درخت دودویی پر تعریف می‌کنند.[۱]
    یک تبارنامه که روی یک درخت دودویی کامل به عمق ۴ نگاشت شده‌است
  • یک درخت دودویی کامل (perfect) یک درخت دودویی پر است که در آن همه برگ‌ها دارای عمق یکسان و یا هم‌سطح باشند، و در آن هر پدری دارای دو فرزند است.[۲](به طور مبهم درخت دودویی کامل نامیده می‌شود (بعدی را مشاهده کنید).) نمونه‌ای از یک درخت دودویی کامل را می‌توان در تبارنامه از یک فرد به عمق داده‌شده مشاهده کرد، به‌طوریکه هر فرد دقیقاً دو پدر و مادر (یک مادر و یک پدر) دارد؛ توجه داشته‌باشید که این معکوس قرارداد معمول درخت پدر\ فرزند است، و این درختان خلاف جهت معمول هستند (ریشه در پایین).
  • یک درخت دودویی کامل (complete) یک درخت دودویی است که در آن هر سطح، به جز احتمالاً آخرین سطح، به‌طور کامل پر شده‌است، و همهٔ گره‌ها تا جایی که ممکن است در چپ درخت قرار می‌گیرند.[۳] درختی که این استثناء را داشته‌باشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند. این نوع درختان از ساختمان دادهٔ ویژه‌ای به نام هیپ استفاده می‌کنند.
  • درخت دودویی کامل نا محدود درختی است که دارای بی‌نهایت سطح قابل‌شمارش می‌باشد، که در آن هر گره دارای دو فرزند است به‌طوریکه گره‌های 2d در سطح d هستند. مجموعهٔ گره‌ها شمارای نامتناهی است، ولی مجموعه‌ای از بی‌نهایت مسیر از ریشه، ناشمارا است، که دارای عدد کاردینالیتی پیوسته است. این مسیرها رابطهٔ دوسویی را با نقاط مجموعۀ کانتر، یا مجموعه‌ای از اعداد گنگ حفظ می‌کند.
  • درختی دودویی متوازن که معمولاً به‌عنوان درخت دودویی است که در آن اختلاف عمق زیردرخت چپ و راست آن ۱ یا کمتر است، اگر چه به طور کلی درخت دودویی است که هیچ برگی نسبت با برگ‌های دیگر فاصلهٔ زیادی تا ریشه ندارد. (طرح توازن متمایز اجازه می‌دهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش بینی باشد. (بسیاری از گره‌ها از ریشه تا برگ پیموده می‌شوند، چنان‌که شمارهٔ ریشه به عنوان گرهٔ ۰ و بقیهٔ گره‌ها اعداد ۱ ۲ … n را می‌گیرند) این عمق (ارتفاع هم نامیده می‌شود) برابر قسمت صحیح (log2(n است، که در آن n تعداد گره‌ها در درخت متوازن است. مثلاً، برای درخت متوازنی که دارای ۱ گره است، log2(1) = ۰، درنتیجه عمق درخت برابر صفر است. برای یک درخت متوازن با ۱۰۰ گره، log2(100) = ۶٫۶۴، درنتیجه عمق درخت برابر ۶ است.
  • درخت منحط درختی است که هر گرهٔ والدین فقط به یک گرهٔ فرزند متصل است. این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادهٔ لیست پیوندی است.

توجه داشته‌باشید که اغلب در ادبیات متفاوتند، به خصوص در رابطه با معنای کلمات «کامل» و «پر».

خواص درخت دودویی[ویرایش]

  • تعداد n گره در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد :n = 2 h + 1 - ۱ که در آن hارتفاع درخت است.
  • تعداد n گره در درخت دودویی با ارتفاع h حداقل برابر n = h + 1 و حداکثر n = 2 h + 1 - ۱ است.
  • تعداد برگ‌های l در درخت دودویی کامل را می‌توان با استفاده ازاین فرمول بدست‌آورد :l = 2 h که در آن h ارتفاع درخت است.
  • تعداد n گره در درخت دودویی کامل را همچنین می‌توان با استفاده از این فرمول بدست آورد: n = 2 l - ۱ که در آن l تعداد برگ‌های درخت است.
  • تعداد پیوندهای تهی (گره‌های فرزند وجود ندارند) در درخت دودویی کامل با n گره برابر (n + 1) است.
  • تعداد گره‌های داخلی (گره‌های غیر از برگ یا n - l) در درخت دودویی کامل با n گره برابر (floor (n/2 است.
  • برای هر درخت دودویی ناتهی با n0 برگ و n2 گره با درجهٔ ۲ داریم :n0 = n2 + 1.[۴]

عملیات متداول[ویرایش]

انواع عملیات‌های مختلف را می‌توان روی درخت دودویی انجام‌داد. بعضی از عملیات‌ها تغیری ایجاد می‌کنند، درحالی که دیگر عمیات اطلاعات مفیدی را درمورد درخت برمی‌گرداند.

درج[ویرایش]

گره‌ها در درخت دودویی می‌توانند بین دو گره دیگر و یا بعد از گره خارجی درج شوند. در درخت دودویی گره درج شده به عنوان فرزند مشخص می‌شود.

گره‌های خارجی[ویرایش]

گره خارجی اضافه شده گره A است، برای اضافه کردن یک گره بعد از گره A، گره A گره جدید را به عنوان فرزند مشخص خود می‌کند و گره جدید گره A را به عنوان گره والد تعیین می‌کند.

گره‌های داخلی[ویرایش]

فرایند درج یک گره در یک درخت دودویی

درج در گره‌های داخلی پیچیده‌تر از گره‌های خارجی است. فرض می‌کنیم که A گرهٔ داخلی و B فرزند گرهٔ A باشد. (اگر درج در قسمت فرزند راست باشد، آنگاه B فرزند سمت راست A است، برای درج فرزند سمت چپ هم همین‌طور است) A فرزند جدید را مشخص می‌کند و گرهٔ جدید A را که والدین آن است مشخص می‌کند.

حذف[ویرایش]

حذف فرآیندی است که یک گره را از درخت حذف می‌کند. فقط می‌توان گره‌های خاصی را در درخت دودویی به وضوح حذف کرد.[۵]

گرهٔ بدون فرزند یا دارای یک فرزند[ویرایش]

فرایند حذف یک گرهٔ داخلی از درخت دودویی

فرض کنید گره‌ای که می‌خواهیم حذف کنیم گرهٔ A باشد. اگر گره بدون فرزند باشد (گرۀ خارجی)، آنگاه فرزند والدین گرهٔ A تهی می‌شود. اگر دارای یک فرزند باشد، آنگاه فرزند A را به والدین گرهٔ A متصل می‌کنیم درنتیجه والدین فرزند A والدین گرهٔ A می‌شود.

گره با دو فرزند[ویرایش]

در یک درخت دودویی نمی‌توان گره‌ای که دارای دو فرزند است را به وضوح حذف کرد.[۵] اگر چه، در درخت دودویی (شامل درخت جستجوی دودویی) این گره‌ها قابل حذف هستند، ولی با ترمیم ساختمان درخت همراه است.

پیمایش[ویرایش]

الگو:مقا لهٔ اصلی پیمایش‌های پسوندی، میانوندی و پیشوندی پیمایش‌هایی هستند که به وسیلهٔ آنها می‌توان همهٔ گره‌ها زیردرخت چپ، راست و ریشه را به طور بازگشتی ملاقات کرد.

پیمایش عمق نخستین[ویرایش]

در پیمایش عمق نخستین، همیشه قصد ما ملاقات دورترین گرهٔ ممکن از گرهٔ ریشه است، ولی با این آگاهی که آن گره باید فرزند گره‌ای باشد که در حال حاضر ملاقات شده است. برعکس در جستجوی عمق نخستین گراف‌ها، احتیاجی به‌بخاطر سپردن گره‌هایی که قبلاً ملاقات شده‌اند نیست، زیرا یک درخت نمی‌تواند دارای دور باشد. پیمایش پیشوندی یک مورد خاص آن است. برای اطلاعات بیشتر به الگوریتم جستجوی عمق اول مراجعه کنید.

پیمایش عرض نخستین[ویرایش]

پیمایش عرض نخستین در مقایسه با عمق نخستین در این است که در این پیمایش همیشه هدف ما ملاقات نزدیکترین گرهٔ ملاقات نشده به ریشه است. برای اطلاعات بیشتر به الگوریتم جستجوی اول سطح مراجعه کنید.

در یک درخت دودویی کامل، اندیس عرض گره ((i - (2d - 1)) را می‌توان به عنوان دستور العمل پیماش از ریشه مورد استفاده قرار داد. با شروع از بیت d-1 از چپ به راست می‌خوانیم، که d در آن همان فاصلهٔ گره تا ریشه است ((d = floor(log2(i+1)) و در سؤال، گره نباید خود ریشه باشد (d>0). هنگامی که اندیس عرضی گره بیت d-1 باشد، دارای بیت ارزش 0 و1 است یعنی در هر مرحله به طور مرتب چپ یا راست را می‌پوشاند. فرایند پی در پی با چک کردن بیت بعدی ادامه می‌یابد تا دیگر بیتی موجود نباشد. سمت راست‌ترین بیت نشان‌دهندهٔ پیمایش نهایی والدین گرهٔ مورد نظر تا خود گره است.

نظریه نوع‌ها[ویرایش]

در نظریه نوع‌ها، در یک درخت دودویی با گره‌هایی از نوع A، به‌صورت استقراء تعریف می‌شوند: .TA = μα. 1 + A × α × α

تعاریف در نظریه گراف[ویرایش]

برای هر ساختمان دادهٔ درخت دودویی، ریشه در درخت دودویی معادل ریشه در نظریهٔ گراف است. در نظریه‌های گراف از تعاریف استفاده می‌شود: درخت دودویی گرافی همبند بدون دور است که درجهٔ هر رأس آن حداکثر سه می‌باشد، که آن می‌تواند هر درخت دودویی با دو یا چند گره را نمایش دهد، دقیقاً به‌ازای هر گرهٔ درجه سه دو یا بیشتر گرهٔ درجهٔ یک وجود دارد، ولی دارای هر تعداد از گرهٔ درجه دو است. درخت دودویی ریشه‌دار مانند گرافی است که درجهٔ یکی از رئوس آن بیش از دو نیست در واقع بیش از دو گرهٔ تنها ندارد؛ بنابراین به وسیلهٔ ریشه ، انتخاب هر رأس به عنوان والدین و دو فرزند آن منحصربه‌فرد تعریف شده‌است، با این حال، اطلاعات کافی برای تشخیص فرزند چپ یا راست وجود دارد. اگر ما به ارتباط کمتری نیاز داشته‌باشیم گراف این امکان را به ما می‌دهد که از مؤلفه‌های همبندی استفاده کنیم. ما به چنین ساختاری جنگل می‌گوییم. راه دیگر تعریف درخت دودویی، تعریف بازگشتی روی گراف‌های مستقیم است.

  • یک رأس تک
  • یک گراف از دو درخت دودویی تشکیل می‌شود، به این صورت که یک رأس و یک یال مستقیم اضافه می‌شود، که آن یال رأس جدید را به ریشهٔ هر کدام از درخت دودویی متصل می‌کند.

بعلاوه این راه طرز رسیدن به فرزندان را تعین نمی‌کند، ولی جای خاص ریشه را درست می‌کند.

روش‌های ذخیره‌سازی درختان دودویی[ویرایش]

درختان دودویی را می‌توان با راه‌های متفاوتی به وسیلهٔ زبان برنامه‌نویسی اولیه ایجاد کرد.

گره‌ها و مراجع[ویرایش]

در یک زبان با سوابق و منابع، درختان دودویی معمولاً به وسیلهٔ یک ساختار گرهٔ درخت که حاوی برخی داده‌ها و مراجع در فرزند چپ و راست آن است ساخته می‌شوند. گاهی اوقات آن گره نیز حاوی یک مرجع به والدین منحصربه‌فرد خود است. اگر یک گره کمتر از دو فرزند داشته‌باشد، ممکن است برخی اشاره‌گرهای فرزندان ارزش تهی خاصی را قرار دهند، یا اشاره‌گرها به گرۀ نگهبان خاصی اشاره کنند. در زبان‌های برنامه‌نویسی با اجتماع برچسب‌ها مانند زبان ML، یک گرهٔ درخت معمولاً از اجتماع برچسب دو نوع گره است، که یکی از آنها دارای داده‌ای ۳تایی، فرزند چپ و فرزند راست، و یکی دیگر از آنها گرهٔ برگ است، که شامل هیچ داده وتابعی نمی‌باشد مانند ساختن مقدار تهی به وسیلهٔ اشاره‌گرها در زبان برنامه‌نویسی.

آرایه‌ها[ویرایش]

درختان دودویی نیز می‌توانند با پیمایش عرض نخستین مانند ساختمان دادۀ مجازی در آرایه‌ها ذخیره شوند، و اگر درخت دودویی کامل باشد در این روش هیچ فاصلهٔ زائدی ایجاد نمی‌شود. به‌طور خلاصه، اگر گره‌ای دارای اندیس i باشد، آنگاه اندیس فرزند چپ آن و اندیس فرزند راست آن می‌شود، حال با داشتن اندیس هر کدام از فرزندان اندیس والدین به صورت بدست می‌آید (با فرض اینکه اندیس ریشه صفر باشد). در این روش هر چه ذخیره‌سازی فشرده‌تر باشد و محل ارجاع بهتر باشد مفیدتر است، به‌خصوص در پیماش پیشوندی. اگرچه، رشد کردن درخت دارای هزینه است، که این فاصلهٔ زائد متناسب با sup>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تای به درخت دودویی

درخت دودویی را می‌توان به مدل اصلی خودش برگرداند، گرهٔ متصل به یال سیاه رنگ سمت چپ نشان‌دهندهٔ فرزند اول آن است وگره‌های متصل به یال‌های آبی رنگ سمت راست آن نشان‌دهندهٔ برادر (خواهر) آن است. برگ‌های آن در سمت چپ قرار دارد که در لیسپ به صورت زیر است: (((N O) I J) C D ((P)(Q)) F (M))

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. Unitary Symmetry, James D. Louck, World Scientific Pub. , 2008
  2. "perfect binary tree". NIST. 
  3. "complete binary tree". NIST. 
  4. Mehta, Dinesh; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall. ISBN 1-58488-435-5. 
  5. ۵٫۰ ۵٫۱ Dung X. Nguyen (2003). "Binary Tree Structure". rice.edu. Retrieved December 28, 2010. 

پیوند به بیرون[ویرایش]