توضیحات
در این قسمت تیم کدگیت سورس درخت قرمز و سیاه در سی پلاس پلاس آماده کرده است. با استفاده از زبان سی پلاس پلاس و بدون استفاده از توابع آماده، درخت قرمز و سیاه را پیاده سازی می کنیم. در ادامه ویژگی این محصول آورده شده است.
سورس درخت قرمز و سیاه در سی پلاس پلاس
درخت قرمز مشکی، درخت جستجوی دودویی با یک بیت فضای اضافی به ازای هر گره است. این یک بیت اضافی، رنگ گره است که می‌تواند قرمز یا مشکی باشد. ویژگی‌های این درخت به صورت زیر است:
- هر گره این درخت، به رنگ قرمز یا سیاه است.
- ریشه‌ی درخت، سیاه است.
- رنگ هر برگ (Null)در ابتدا سیاه است.
- پدر هر گره قرمز، سیاه است.
- در هر مسیر از گره x به هر نواده برگی، تعداد گرههای سیاه برابر هستند.
ویژگی‌های که در پیاده سازی درخت سیاه و قرمز آورده شده است:
- پیاده سازی کامل عملیات درج
- پیاده سازی کامل عملیات حذف
- پیاده سازی عملیات پیمایش پیش ترتیب
- پیاده سازی عملیات پیمایش level order
- …
خروجی برنامه
تمامی عملیات‌های پیاده سازی شده دارای تابع Main بوده و یک درخت تعریف شده و پس از اضافه کردن گره به درخت، پیمایش آن صدا زده می شود. خروجی برنامه، پیمایش پیش ترتیب و Level order درخت بعد از عملیات حذف و اضافه کردن گره ها می‌باشد.