موضوع مقاله: درخت دودویی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت دودویی | مقدمه: در علوم رایانه، یک درخت دودویی یک ساختمان دادهٔ درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می‌شوند. | ## بخش 1: درخت دودویی | درخت‌های دودویی برای پیاده‌سازی درخت جستجوی دودویی و انبوه دودویی و برای جستجوی کارآمد و مرتب‌سازی استفاده می‌شود. درخت دودویی ریشه‌دار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد. درخت دودویی پر(گاهی درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودویی گفته می‌شود) یک درخت که در آن هر گره به غیر از برگ‌ها دارای دو فرزند است. یک درخت دودویی کامل (complete) یک درخت دودویی است که در آن هر سطح، به جز احتمالاً آخرین سطح، به‌طور کامل پر شده‌است، و همهٔ گره‌ها تا جایی که ممکن است در چپ درخت قرار می‌گیرند. درختی که این استثناء را داشته‌باشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند. درخت دودویی کامل نا محدود درختی است که دارای بی‌نهایت سطح قابل شمارش است، که در آن هر گره دارای دو فرزند است به‌طوری که گره‌های 2d در سطح d هستند. مجموعهٔ گره‌ها شمارای نامتناهی است، ولی مجموعه‌ای از بی‌نهایت مسیر از ریشه، ناشمارا است، که دارای عدد کاردینالیتی پیوسته است. این مسیرها رابطهٔ دوسویی را با نقاط مجموعه کانتور، یا مجموعه‌ای از اعداد گنگ حفظ می‌کند. درختی دودویی متوازن که معمولاً به‌عنوان درخت دودویی است که در آن اختلاف عمق زیردرخت چپ و راست آن ۱ یا کمتر است، اگر چه به‌طور کلی درخت دودویی است که هیچ برگی نسبت با برگ‌های دیگر فاصلهٔ زیادی تا ریشه ندارد. (طرح توازن متمایز اجازه می‌دهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش‌بینی باشد. (بسیاری از گره‌ها از ریشه تا برگ پیموده می‌شوند، چنان‌که شمارهٔ ریشه به عنوان گرهٔ ۰ و بقیهٔ گره‌ها اعداد ۱ ۲ … n را می‌گیرند) این عمق (ارتفاع هم نامیده می‌شود) برابر قسمت صحیح (log2(n است، که در آن n تعداد گره‌ها در درخت متوازن است؛ مثلاً، برای درخت متوازنی که دارای ۱ گره است، log2(1) = ۰، در نتیجه عمق درخت برابر صفر است. برای یک درخت متوازن با ۱۰۰ گره، log2(100) = ۶٫۶۴، در نتیجه عمق درخت برابر ۶ است. این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادهٔ لیست پیوندی است. توجه داشته‌باشید که اغلب در ادبیات متفاوتند، به خصوص در رابطه با معنای کلمات «کامل» و «پر». خواص درخت دودویی تعداد n گره در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد: که در آن h ارتفاع درخت است. تعداد برگ‌ها (به انگلیسی: Leaves) در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد :l = 2 h که در آن h ارتفاع درخت است. تعداد n گره در درخت دودویی کامل را همچنین می‌توان با استفاده از این فرمول به‌دست‌آورد: n = 2 l - ۱ که در آن l تعداد برگ‌های درخت است. تعداد پیوندهای تهی (گره‌های فرزند وجود ندارند) در درخت دودویی کامل با n گره برابر (n + 1) است. | ## بخش 2: درخت دودویی | بعضی از عملیات‌ها تغیری ایجاد می‌کنند، درحالی که دیگر عملیات اطلاعات مفیدی را در مورد درخت برمی‌گرداند. درج گره‌ها در درخت دودویی می‌توانند بین دو گره دیگر یا بعد از گره خارجی درج شوند. گره‌های خارجی گره خارجی اضافه شده گره A است، برای اضافه کردن یک گره بعد از گره A، گره A گره جدید را به عنوان فرزند مشخص خود می‌کند و گره جدید گره A را به عنوان گره والد تعیین می‌کند. (اگر درج در قسمت فرزند راست باشد، آنگاه B فرزند سمت راست A است، برای درج فرزند سمت چپ هم همین‌طور است) A فرزند جدید را مشخص می‌کند و گرهٔ جدید A را که والدین آن است مشخص می‌کند. اگر دارای یک فرزند باشد، آنگاه فرزند A را به والدین گرهٔ A متصل می‌کنیم در نتیجه والدین فرزند A والدین گرهٔ A می‌شود. گره با دو فرزند در یک درخت دودویی نمی‌توان گره‌ای که دارای دو فرزند است را به وضوح حذف کرد. اگر چه، در درخت دودویی (شامل درخت جستجوی دودویی) این گره‌ها قابل حذف هستند، ولی با ترمیم ساختمان درخت همراه است. پیمایش پیمایش‌های پسوندی، میانوندی و پیشوندی پیمایش‌هایی هستند که به وسیلهٔ آن‌ها می‌توان همهٔ گره‌ها زیردرخت چپ، راست و ریشه را به‌طور بازگشتی ملاقات کرد. برعکس در جستجوی عمق نخستین گراف‌ها، احتیاجی به بخاطر سپردن گره‌هایی که قبلاً ملاقات شده‌اند نیست، زیرا یک درخت نمی‌تواند دارای دور باشد. پیمایش عرض نخستین پیمایش عرض نخستین در مقایسه با عمق نخستین در این است که در این پیمایش همیشه هدف ما ملاقات نزدیکترین گرهٔ ملاقات نشده به ریشه است. در یک درخت دودویی کامل، اندیس عرض گره i - (2d - 1 را می‌توان به عنوان دستور العمل پیماش از ریشه مورد استفاده قرار داد. هنگامی که اندیس عرضی گره بیت d-1 باشد، دارای بیت ارزش 0 و1 است یعنی در هر مرحله به‌طور مرتب چپ یا راست را می‌پوشاند. نظریه نوع‌ها در نظریه نوع‌ها، در یک درخت دودویی با گره‌هایی از نوع A، به‌صورت استقراء تعریف می‌شوند: .TA = μα. 1 + A × α × α تعاریف در نظریه گراف برای هر ساختمان دادهٔ درخت دودویی، ریشه در درخت دودویی معادل ریشه در نظریهٔ گراف است. در نظریه‌های گراف از تعاریف استفاده می‌شود: درخت دودویی گرافی همبند بدون دور است که درجهٔ هر رأس آن حداکثر سه است، که آن می‌تواند هر درخت دودویی با دو یا چند گره را نمایش دهد، دقیقاً به‌ازای هر گرهٔ درجه سه دو یا بیشتر گرهٔ درجهٔ یک وجود دارد، ولی دارای هر تعداد از گرهٔ درجه دو است. درخت دودویی ریشه‌دار مانند گرافی است که درجهٔ یکی از رئوس آن بیش از دو نیست در واقع بیش از دو گرهٔ تنها ندارد؛ بنابراین به وسیلهٔ ریشه، انتخاب هر رأس به عنوان والدین و دو فرزند آن منحصربه‌فرد تعریف شده‌است، با این حال، اطلاعات کافی برای تشخیص فرزند چپ یا راست وجود دارد. اگر ما به ارتباط کمتری نیاز داشته‌باشیم گراف این امکان را به ما می‌دهد که از مؤلفه‌های همبندی استفاده کنیم. یک رأس تک یک گراف از دو درخت دودویی تشکیل می‌شود، به این صورت که یک رأس و یک یال مستقیم اضافه می‌شود، که آن یال رأس جدید را به ریشهٔ هر کدام از درخت دودویی متصل می‌کند. | ## بخش 3: درخت دودویی | به‌علاوه این راه طرز رسیدن به فرزندان را تعین نمی‌کند، ولی جای خاص ریشه را درست می‌کند. روش‌های ذخیره‌سازی درختان دودویی درختان دودویی را می‌توان با راه‌های متفاوتی به وسیلهٔ زبان برنامه‌نویسی اولیه ایجاد کرد. اگر یک گره کمتر از دو فرزند داشته‌باشد، ممکن است برخی اشاره‌گرهای فرزندان ارزش تهی خاصی را قرار دهند، یا اشاره‌گرها به گرۀ نگهبان خاصی اشاره کنند. در زبان‌های برنامه‌نویسی با اجتماع برچسب‌ها مانند زبان ML، یک گرهٔ درخت معمولاً از اجتماع برچسب دو نوع گره است، که یکی از آن‌ها دارای داده‌ای ۳تایی، فرزند چپ و فرزند راست، و یکی دیگر از آن‌ها گرهٔ برگ است، که شامل هیچ داده و تابعی ناست مانند ساختن مقدار تهی به وسیلهٔ اشاره‌گرها در زبان برنامه‌نویسی. آرایه‌ها درختان دودویی نیز می‌توانند با پیمایش عرض نخستین مانند ساختمان دادۀ مجازی در آرایه‌ها ذخیره شوند، و اگر درخت دودویی کامل باشد در این روش هیچ فاصلهٔ زائدی ایجاد نمی‌شود. به‌طور خلاصه، اگر گره‌ای دارای اندیس i باشد، آنگاه اندیس فرزند چپ آن و اندیس فرزند راست آن می‌شود، حال با داشتن اندیس هر کدام از فرزندان اندیس والدین به صورت به‌دست می‌آید (با فرض اینکه اندیس ریشه صفر باشد). در این روش هر چه ذخیره‌سازی فشرده‌تر باشد و محل ارجاع بهتر باشد مفیدتر است، به‌خصوص در پیماش پیشوندی. اگرچه، رشد کردن درخت دارای هزینه است، که این فاصلهٔ زائد متناسب با h - n>2 است که در آن h عمق درخت و n تعداد گره‌ها است. این روش ذخیره‌سازی معمولاً برای هرم دودویی استفاده می‌شود، و هیچ فضایی ازبین نمی‌رود چون گره‌ها به صورت عرض نخستین اضافه می‌شوند. 300px|ذخیرهٔ درخت کوچک دودویی کامل در آرایه سیستم‌های کدگذاری کدگذاری فشرده داده ساختارهای فشرده که فضای اشغال شده را تا حد ممکن کوچک می‌کند، و به عنوان کران پایین در نظریه اطلاعات تأسیس شده‌است. روی اعداد کاتالان است (با فرض اینکه ما درختان با ساختار یکسان را مشابه مشاهده می‌کنیم) برای بزرگ آن برابر است؛ به این ترتیب ما به حداقل آن نیاز داریم که تقریباً برابر بیت در کدگذاری آن است؛ بنابراین یک درخت دودویی فضا را اشغال می‌کند. یک نمایش ساده برای ملاقات گره‌های درخت در پیمایش پیشوندی این است که خروجی عدد "۱" نشان‌دهندهٔ گرهٔ داخلی و عدد " ۰" نشان‌دهندهٔ برگ است. اگر درخت شامل داده باشد، می‌توانیم به سادگی به‌طور همزمان داده‌ها را با پیمایش پیشوندی در آرایه‌های پی‌درپی ذخیره کنیم. برای تبدیل درخت معمولی به مدل معمولی آن، تنها نیاز داریم که مسیر فرزندان درخت معمولی را نشان دهیم، در نتیجه درخت به‌طور خودکار به درخت دودویی تبدیل می‌شود. هر گره مانند N در درخت مورد نظر با گرهٔ 'N در درخت دودویی با هم رابطه دارند به‌طوری که: فرزند چپ 'N همان اولین فرزند گرهٔ N است، و فرزند راست 'N همان برادر (خواهر) گرهٔ N است، گرهٔ بعدی از میان فرزندانی است که والدین آن‌ها N است. این درخت دودویی، درخت بررسی شده معمولی را نشان می‌دهد که گاهی نیز به درخت دودویی فرزند-چپ همزاد- راست (درخت LCRS) یا درخت مضاعف زنجیر وار یا زنجیر ارث بری فرزندان مقایسه می‌کند. یکی از راه‌های فکر کردن در این مورد این است که هر یک از گره‌های فرزند در (لیست پیوندی) قرار گیرند. برای مثال، در درخت سمت چپ، A دارای ۶ فرزند است {B,C,D,E,F,G}، که می‌توان این درخت را به درخت دودویی سمت راست تبدیل کرد. | ## جمع‌بندی | 400x240px|مثالی برای تبدیل درخت nتای به درخت دودویی درخت دودویی را می‌توان به مدل اصلی خودش برگرداند، گرهٔ متصل به یال سیاه رنگ سمت چپ نشان‌دهندهٔ فرزند اول آن است و گره‌های متصل به یال‌های آبی رنگ سمت راست آن نشان‌دهندهٔ برادر (خواهر) آن است.