درخت دودویی

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

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

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

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

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

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

  • تعداد n گره در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد :n = 2 h + 1 - 1 که در آن hارتفاع درخت است.
  • تعداد n گره در درخت دودویی با ارتفاع h حداقل برابر n = h + 1 و حداکثر n = 2 h + 1 - 1 است.
  • تعداد برگ‌های l در درخت دودویی کامل را می‌توان با استفاده ازاین فرمول بدست‌آورد :l = 2 h که در آن h ارتفاع درخت است.
  • تعداد n گره در درخت دودویی کامل را همچنین می‌توان با استفاده از این فرمول بدست آورد : n = 2 l - 1 که در آن l تعداد برگ‌های درخت است.
  • تعداد پیوندهای تهی (گره‌های فرزند وجود ندارند) در درخت دودویی کامل با n گره برابر (n + 1) است.
  • تعداد گره‌های داخلی (گره‌های غیر از برگ یا n - l ) در درخت دودویی کامل با n گره برابر (floor (n/2 است.
  • برای هر درخت دودویی ناتهی با n0 برگ و n2 گره با درجۀ 2 داریم :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 ،یک گرۀ درخت معمولاً از اجتماع برچسب دو نوع گره است ، که یکی از آنها دارای داده‌ای 3تایی ، فرزند چپ و فرزند راست، و یکی دیگر از آنها گرۀ برگ است، که شامل هیچ داده وتابعی نمی‌باشد مانند ساختن مقدار تهی به وسیلۀ اشاره‌گر ها در زبان برنامه‌نویسی.

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

درختان دودویی نیز می‌توانند با پیمایش عرض نخستین مانند ساختمان دادۀ مجازی در آرایه‌ها ذخیره شوند، و اگر درخت دودویی کامل باشد در این روش هیچ فاصلۀ زائدی ایجاد نمی‌شود. به‌طور خلاصه، اگر گره‌ای دارای اندیس i باشد، آنگاه اندیس فرزند چپ آن 2i + 1 و اندیس فرزند راست آن 2i +2 می‌شود، حال با داشتن اندیس هر کدام از فرزندان اندیس والدین به صورت \left \lfloor \frac{i-1}{2} \right \rfloor بدست می‌آید( با فرض اینکه اندیس ریشه صفر باشد). در این روش هر چه ذخیره‌سازی فشرده‌تر باشد و محل ارجاع بهتر باشد مفیدتر است ، به‌خصوص در پیماش پیشوندی. اگر‌چه ، رشد کردن درخت دارای هزینه است ، که این فاصلۀ زائد متناسب با sup>h - n>2 است که در آن h عمق درخت و n تعداد گره‌ها می‌باشد. این روش ذخیره‌سازی معمولاً برای هیپ دودویی استفاده می‌شود،و هیچ فضایی ازبین نمی‌رود چون گره‌ها به صورت عرض نخستین اضافه می‌شوند.

ذخیرۀ درخت کوچک دودویی کامل در آرایه

سیستم‌های کد‌گذاری[ویرایش]

کد‌گذاری مختصر[ویرایش]

ساختمان‌داده مختصر که فضای اشغال شده را تا حد ممکن کوچک می‌کند،و به عنوان کران پایین در نظریه اطلاعات تأسیس شده‌است. تعداد درختان دودویی متفاوت رویn گره\mathrm{C}_{n} است. n روی اعداد کاتالان است( با فرض اینکه ما درختان با ساختار یکسان را مشابه مشاهده می‌کنیم) برای n بزرگ آن برابر4^{n} است ؛ به این ترتیب ما به حداقل آن نیاز داریم که تقریباً برابر\log_{2}4^{n} = 2n بیت در کد‌گذاری آن است. بنابراین یک درخت دودویی 2n+o(n) فضا را اشغال می‌کند. یک نمایش ساده برای ملاقات گره‌های درخت در پیمایش پیشوندی این است که خروجی عدد "1" نشان‌دهندۀ گرۀ داخلی و عدد " 0" نشان‌دهندۀ برگ است. [۱] اگر درخت شامل داده باشد ، می‌توانیم بسادگی به طور همزمان داده‌ها را با پیمایش پیشوندی در آرایه‌های پی‌در‌پی ذخیره کنیم. تابع مورد نظر به صورت زیر است:

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);
}

در پایان ساختار رشته ای فقط دارای2n + 1 بیت است، که 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 دارای 6 فرزند است {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. 

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

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