درخت سرخ-سیاه (Red-Black Tree)، در ریاضیات (Mathematics)
انواع درخت (Tree) را در آموزش زیر شرح دادیم :
درخت سرخ-سیاه (Red-Black Tree) :
درخت سرخ-سیاه نوع دیگری از درخت های جستجوی دودویی خود-متوازن است که قوانین ساده تری نسبت به AVL برای توازن دارد. هر گره دارای یک رنگ (قرمز یا سیاه) است و قوانین زیر رعایت می شود: ریشه همیشه سیاه است، هیچ دو گره قرمز متوالی وجود ندارد (فرزند یک گره قرمز نمی تواند قرمز باشد)، و تعداد گره های سیاه در هر مسیر از ریشه تا برگ یکسان است. این قوانین تضمین می کند که طولانی ترین مسیر از کوتاه ترین مسیر بیش از دو برابر بلندتر نباشد. به همین دلیل، عملیات آن همچنان
\[ O(\log n) \]است و در بسیاری از کتابخانه های استاندارد مانند map در ++C و TreeMap در جاوا استفاده می شود.
نویسنده علیرضا گلمکانی
شماره کلید 5534
گزینه ها 
نظرات 0 0 0