درخت سرخ-سیاه

شباهت به درخت‌های بی مرتبه ۴

یک درخت قرمز-سیاه ار نظر ساختار شبیه یک درخت بی مرتبه ۴ است که در آن هر گره می‌تواند ۱ تا ۳ مقدار و همچنین ۲ تا ۴ اشاره گر به فرزندانش داشته باشد. در هر درخت بی، هر گره تنها یک مقدار دارد که برابر مقدار گره سیاه در درخت قرمز-سیاه است، و یک مقدار دلخواه دارد که و/یا بعد از آن در همان گره آمده‌است، که هر دوی آن‌ها مساوی گره قرمز در درخت قرمز-سیاه هستند.
یک راه دیدن این برابری این است که در گره‌های قرمز درخت قرمز-سیاه در یک نمایش گرافیکی به سمت بالا حرکت کنیم، به‌طوری‌که با پدر سیاهشان در یک ردیف قرار بگیرند و یک دسته افقی را تشکیل دهند. در درخت بی، یا در نمایش گرافیکی تغییر یافته درخت قرمز-سیاه که گفته شد، همه برگ‌ها عمق یکسانی دارند.
در این حالت درخت قرمز-سیاه، از نظر ساختار با درخت بی مرتبه ۴ برابر است که حداقل میزان پرشدن در یک دسته برابر ۳۳٪ است.
این نوع درخت بی، عمومی تر از درخت قرمز-سیاه است اما هنگام تبدیل به درخت قرمز-سیاه، ابهاماتی دارد چون از یک درخت بی مرتبه ۴، چندین درخت قرمز-سیاه ساخته می‌شود. اگر یک دسته در درخت بی تنها ۱ مقدار را شامل شود، این مقدار کمینه است، گره مربوطه سیاه است و دو اشاره گر به فرزندانش دارد. اگر یک دسته شامل ۳ مقدار شود، مقدار وسطی در یک گره سیاه قرار می‌گیرد و گره‌های کناری آن باید قرمز باشند. اگر دسته شامل ۲ مقدار باشد، هر کدام از آن‌ها می‌تواند در درخت قرمز-سیاه، سیاه باشد و دیگری باید قرمز باشد؛ بنابراین درخت بی مرتبه ۴، مشخص نمی‌کند که کدامیک از مقادیر در هر دسته ریشه سیاه کل آن دسته و پدر بقیه مقادیر دسته است. با وجود این، عملیات در درخت‌های قرمز-سیاه از نظر زمان بهینه تر هستند چون نیازی به نگهداشتن برداری از مقادیر نیست. این نگهداری زمانی که مقادیر مستقیماً در هر گره ذخیره شده‌اند، نسبت به وقتی که تنها مرجع آن‌ها نگهداری شده‌است، پر هزینه است. البته گره‌های درخت بی از نظر حافظه به صرفه تر هستند چون لازم نیست برای آن‌ها صفت رنگ نگهداری شود. در عوض باید مشخص شود کدام بخش از دسته استفاده شده‌است.
می‌توان شباهت‌هایی با درخت‌های بی مرتبه‌های بالاتری که از نظر ساختار شبیه درخت دودویی رنگ شده باشند هم ایجاد کرد چون تنها به رنگ‌های بیشتری نیاز است. مثلاً فرض کنید آبی را هم استفاده کنیم. در نتیجه درخت آبی-قرمز-سیاه مثل درخت قرمز-سیاه تعریف می‌شود اما با این محدودیت اضافه که دو گره متوالی از نظر مقدار نباید آبی باشند و همه گره‌های آبی باید فرزندان گره قرمز باشند. چنین درختی معادل یک درخت بی می‌شود که دسته‌های آن حداکثر ۷ مقدار و با این رنگ‌ها دارند :آبی، قرمز، آبی، سیاه، آبی، قرمز، آبی (هر گروه حداکثر ۱ گره سیاه، ۲ گره قرمز و ۴ گره آبی دارد).
برای تعدیل کردن حجم مقادیر، درج و حذف در یک درخت دودویی سریعتر از درخت‌های بی است چون درخت‌های رنگ شده تلاشی برای بیشینه کردن مقدار پر شدن در یک دسته افقی از گره‌ها نمی‌کنند. (تنها کمینه مقدار پرشدن در درخت‌های دودویی رنگ شده تضمین شده‌است). چرخش در درخت‌های بی سریع تر است (چون چرخش‌ها اغلب در دسته یکسان رخ می‌دهند به جای اینکه در چند گره مجزا در یک درخت دودویی رنگ شده انجام شوند). با این وجود برای مرتب‌سازی حجم زیادی از داده‌ها، درخت‌های بی بسیار سریعتر هستند چون با گروهی کردن چند فرزند در یک دسته و امکان دسترسی محلی، فشرده تر شده‌اند.
همه بهینه‌سازی‌های ممکن در درخت‌های بی برای افزایش متوسط میزان پرشدن گروه‌ها در درخت‌های دودویی رنگ شده هم ممکن است. بیشینه کردن میزان پرشدن در یک درخت بی، مانند کم کردن ارتفاع درخت چند رنگ است که با افزایش تعداد گره‌های غیر سیاه انجام می‌شود. بدترین حالت زمانی رخ می‌دهد که همه گره‌ها در یک درخت دودویی رنگ شده، سیاه باشند. بهترین حالت زمانی است که تنها یک سوم آن‌ها سیاه باشند (و دو سوم بقیه، قرمز باشند).

کاربردها و ساختمان داده‌های مرتبط

درخت‌های قرمز-سیاه، ضمانتی برای بدترین حالت زمان درج، حذف و جستجو می‌دهند. این نکته نه تنها باعث ارزشمندی آن‌ها در کاربردهایی که زمان برای آن‌ها حیاتی است مانند real-time application شده‌است بلکه آن‌ها را سازنده باارزش بلوک‌ها در سایر ساختمان داده‌های استفاده شده در هندسه محاسباتی که ضمانت بدترین زمان اجرا دارند، کرده‌است.
درخت متوازن ساختار دیگری است که جستجو، درج و حذف را در زمان اجرای O(log n)پشتیبانی می‌کند. این درخت بیشتر از درخت قرمز-سیاه مرتب شده‌است که منجر به درج و حذف آهسته‌تر اما بازیابی سریعتر می‌شود.
درخت‌های قرمز-سیاه به ویژه در برنامه‌نویسی تابعی ارزشمند هستند که یکی از رایج‌ترین انواعساختار پایدار داده‌های استفاده شده برای ساختن آرایه‌های اشتراکی و مجموعه‌ها است. نسخه پایدار درخت‌های قرمز-سیاه علاوه بر زمان، نیازمند فضایی به اندازه O(log n) برای هر درج یا حذف است.
درخت‌های قرمز-سیاه یک ایزومتری از درخت‌های ۲–۴ هستند. به عبارت دیگر، برای هر درخت ۲–۴، یک درخت قرمز-سیاه همتا که عناصر داده‌ای آن از همان مرتبه است، وجود دارد. عملیات درج و حذف در درخت‌های ۲–۴ هم معادل تغییر رنگ و چرخش در درخت‌های قرمز-سیاه هستند. این باعث می‌شود درخت‌های ۲–۴ ابزار مهمی برای درک منطق درخت‌های قرمز-سیاه باشند؛ و این همان دلیلی است که بسیاری از متن‌های معرفی الگوریتم‌ها، درخت‌های ۲–۴ را قبل از درخت‌های قرمز-سیاه معرفی می‌کنند باوجود اینکه درخت‌های ۲–۴ معمولاً در عمل استفاده نمی‌شوند.
در سال ۲۰۰۸، رابرت سجویک یک نسخه ساده‌تر از درخت‌های قرمز-سیاه را معرفی کرد که Left-Leaning Red-Black Trees نامیده شد که با حذف کردن درجه آزادی نا مشخص در پیاده‌سازی به وجود آمده بود. LLRB یک ویژگی اضافه دارد که همه رئوس قرمز باید هنگام درج‌ها و حذف‌ها در سمت چپ درخت قرار بگیرند. درخت‌های قرمز-سیاه می‌توانند برای هر مجموعه‌ای از عملیات، به درخت‌های ۲–۳ یا درخت‌های ۲–۴ ایزومتریک باشند. درخت ۲–۴ ایزومتری در سال ۱۹۸۷ توسط سجویک معرفی شد. با درخت‌های ۲–۴، ایزومتری با یک «تغییر رنگ» حل شده است که در آن رنگ قرمز هر دو گره فرزند، به پدر منتقل می‌شود.

عملگرها

عملگرهای فقط خواندنی نسبت به درخت‌های دودویی ساده نیاز به تغییر ندارند چراکه یک حالت خاص از آن‌ها می‌باشند ولی حذف و اضافهٔ معمولی می‌تواند تأثیراتی از قبیل خارج شدن از شروط اولیهٔ درخت‌های قرمز- سیاه داشته باشد که برای بازگردانی آن ویژگی‌ها نیاز به تغییر رنگ و چرخش درخت دارد. اگرچه این نوع حذف واضافه پیچیدگی بسیاری دارد ولی بازهم نرخ جستجوی آن همچنان
(O(logn می‌باشد.