سلام
درخت Red_Black جزو درخت های متوازن هست.
در درخت های دودویی حذف و درج ممکنه ارتفاع درخت را زیاد بکند برای همین زمان جست و جو زیاد میشود . برای اینکه زمان جست و جو را در O(logn) نگه داریم از این نوع درخت ها استفاده میکنیم .
دقیقا همانند درخت دودویی است که نودهایش به دو رنگ قرمز و سیاه رنگ شده است .
این درخت شرایطی داره :
1-ریشه ی درخت معمولا (default) سیاه است .
2-هر نودی که قرمز باشد پدرش سیاه است .
3-به هر نود انتهایی برگ های تهی اضافه میکنیم و فرض میکنیم که این برگ های تهی به رنگ سیاه هستند .
در این درخت به ازای هر گره تمام مسیرها به سمت برگ ها باید دارای تعداد مساوی گره سیاه باشند .
اگر شما درختی داشته باشید که ارتفاعش از 2(logn+1) بزرگ تر بود این درخت حتما درخت قرمز سیاه نیست .
حذف و درج در این درحت باید به گونه ای باشه که این شرایط را در اون حفظ بکنه
برای حفظ این حالت هم میتوانیم از rotate استفاده کنیم که اینجا توضیح داده شده :http://www.7khatcode.com/3353/%D9%86%D8%AD%D9%88%D9%87-%D9%86%D9%88%D8%B4%D8%AA%D9%86-%D8%AF%D8%B1%D8%AE%D8%AA-%D8%A7%DB%8C-%D9%88%DB%8C-%D8%A7%D9%84-%DB%8C%D8%A7-avl-tree?show=3353#q3353