Червено-черното дърво е вид самобалансиращо двоично дърво за търсене. Всеки елемент от двоичното дърво съдържа допълнителен бит, като този бит често се интерпретира като цвят (червен или черен) на елемента. Този цветен бит се използва, за да се осигури, че дървото остава относително балансирано по време на въвеждане и изтриване. Балансът се контролира, като се „оцветяват“ отделните елементи в един от двата цвята (червено или черно) по определени критерии. Това ограничава разбалансирането на дървото, дори и в най-лошия случай. След като дървото се модифицира, настъпва последователно преподреждане и преоцветяване, за да се възстановят цветовите свойства. Тези свойства са проектирани така, че преподреждането и преоцветяването да се извършват бързо.
Балансирането на дървото не е идеално, но позволява ефективно търсене — за време O(log n), където n е броят на елементите в дървото. Операциите вмъкване и изтриване, преподреждане и преоцветяване стават също за време O(log n).
История През 1972 Рудолф Байер създава структура от данни, която има специална подредба — четири случая на Б-дърво. Тези дървета поддържат всички пътища от корените до листата с еднакъв брой разклонения, създавайки идеално балансирани дървета. Въпреки това те не са двоични дървета за търсене. Байер ги нарича „симетрични двоични Б-дървета“ в записките си, но по-късно те стават известни като 2-3-4 Дървета и 2–4 Дървета.
В една записка от 1978 г. със заглавие „Двуцветна структура за балансирани дървета“ Леонидас Дж. Гуибас и Робърт Седжуик извличат Червено-черното дърво от симетричното двоично Б-дърво. Цветът червено е избран, защото по това време е бил най-добре пресъздаван от цветните принтери, достъпни за авторите, които работят в Xerox PARC. Според разказа на проф. Гуибас двамата тогава разполагали само с червени и черни химикали за рисуването на дърветата.
През 1993, Андерсън представя идеята за Дясно наклонено дърво с цел опростяване въвеждащите и изтриващи операции.
През 1999, Окасаки показал как може да се направи въвеждащата операция изцяло функционална. Неговата балансираща функция трябвало да се погрижи само за 4 небалансирани случая и един дефолтен балансиран случай.
Оригиналният алгоритъм използвал 8 небалансирани случая, но Кормен ет. Ал. (2001) ги намалил до 6 небалансирани. Седжуик показал, че въвеждащата операция може да бъде имплементирана само с 46 реда код на Java. През 2008, Седжуик предложил Ляво наклонено червено-черно дърво, противоположно на идеята на Андерсън за опростяване на алгоритми. Седжуик първоначално разрешил разклонения, чийто два дъщерни елемента са червени, приличайки повече като 2-3-4 Дървета, но по-късно е добавено ограничение, правейки новите дървета повече като 2 – 3 Дървета. Впоследствие Седжуик имплементирал въвеждащ алгоритъм само от 33 реда код, намалявайки значително оригиналните 46 реда код.
Терминология Червено-черно дърво е специален тип двоично дърво, използвано в компютърните науки за класификация на фрагменти от сравними данни, като част от текст или числа.
Листовите разклонения на червено-черните дървена не съдържат данни. Тези листа не трябва да бъдат експлицитни в компютърната памет – зададеният дъщерен елемент показва, че елемента е листо – но опростява някои от алгоритмите за операции на червено-черните дървета, ако листата наистина са експлицитни разклонения. За спестяване памет, понякога едно-единствено сентинално разклонение върши ролята на всички зададени листни разклонения; всички референции от вътрешните разклонения до листните сочат към сентинелното разклонение.
Червено-черните дървета, като всички двоични дървета за търсене, позволяват ефективно подредено търсене (което е в ред: ляво-корен-дясно) на техните елементи. Времето за намиране на резултати от търсенето от корен към листо, следователно балансирано дърво с n разклонения, имайки възможно най-малката височина на дървото, се получава О(log n) време за търсене.
Свойства
В допълнение на изискванията, изброени в двоично дърво трябва да бъдат изпълнени и следните условия: Всеки елемент има само черен или червен цвят. Основния елемент е черен. Това правило понякога се пропуска. Понеже основният елемент винаги може да бъде променен от черен на червен, това правило има малък ефект върху анализа. Ако един елемент е червен, и двете му деца са черни. Всеки път от даден елемент до кой да е празен елемент от неговите наследници, съдържа еднакъв брой черни елементи.
Ето някои дефиниции: броят на черните елементи от основния до даден елемент се нарича черна дълбочина; постоянният брой черни елементи от основата до даден изход се нарича черна височина на червено-черното дърво. p. 155.
Тези ограничения налагат едно критично свойство на червено-черните дървета: пътят от основата до най-отдалеченото листо е не повече от двойния път до най-близкото . Резултатът е, че дървото е грубо балансирано по височина. Понеже операции като вмъкване, изтриване и търсене изисква време, пропорционално в най-лошия случай на височината на дървото, ограничената височина позволява на дървото да бъде по-ефективно от обикновеното двоично дърво.
Аналогия с Б-дървета от 4-ти ред
Червено-черното дърво е подобно като структура на Б-дърво от 4-ти ред, където всеки възел може да съдържа между 1 и 3 стойности и (съответно) между 2 и 4 указателя към деца. В такова Б-дърво всеки възел съдържа само една стойност, съвпадаща със стойността в черен възел от Червено-черно дърво, с допълнителна (незадължителна) стойност преди и/или след нея в същия възел, като и двете съвпадат с еквивалентен червен възел на Червено-черно дърво.
Един от начините да се види тази еквивалентност е да „се придвижат нагоре“ червените възли в графичното представяне на Червено-черно дърво, така че те да се приравнят хоризонтално с техния черен възел родител, чрез съвместно създаване на хоризонтален клъстер. В Б-дърво или в модифицираното графично представяне на червено-черно дърво, всички листни възли са на една и съща дълбочина.
След това Червено-черното дърво е структурно еквивалентно на Б-дърво от 4-ти ред, с минимален коефициент на запълване 33% от стойностите на клъстер, с максимален капацитет от 3 стойности.
Все пак този вид Б-дърво е все още по-общ от Червено-черното дърво, тъй като позволява двусмислие при преобразуване в Червено-черно дърво – множество Червено-черни дървета могат да бъдат направени от еквивалентно Б-дърво от 4-ти ред. Ако клъстер на Б-дърво съдържа само една стойност, което е минимално, е черно, и има два указателя към деца. Ако клъстер съдържа 3 стойности, тогава централната стойност ще бъде черна и всяка стойност, съхранявана от двете страни ще бъде червена. Ако обаче клъстер съдържа две стойности, всяка една може да стане черен възел в Червено-черно дърво (а другата ще бъде червена).
Б-дървото от 4-ти ред не поддържа коя от стойностите, които се съдържат във всеки клъстер, е основното черно дърво за целия клъстер и родител на останалите стойности в същия клъстер. Въпреки това, операциите в Червено-черните дървета са по-икономични по отношение на времето, тъй като не е нужно да се поддържа векторът на стойностите. Може да бъде времеемко, ако стойностите се съхраняват директно във всеки възел, вместо да се съхраняват чрез препратка. Възлите в Б-дървото обаче са по-икономични по отношение на пространството, защото не е нужно да се съхраняват цветовите атрибути на всеки възел. Вместо това, трябва да се знае кой слот в клъстерния вектор е използван. Ако стойностите се съхраняват референтно, например обекти, могат да се използват нулеви референции и така клъстера може да бъде представен чрез вектор, съдържащ 3 слота за указатели към стойностите плюс 4 слота за препратки към деца в дървото. В този случай Б-дървото може да бъде по-компактно в паметта, подобрявайки местоположението на данните.
Приложения и свързани структури от данни Червено-черни дървета предлагат гаранции в най-лошия случай (worst-case guarantees) за времето за вмъкване, изтриване и търсене. Това ги прави ценни не само в приложения, чувствителни по отношение на времето за работа, като например приложения в реално време, но това ги прави ценни и в градивни елементи в други структури от данни, които осигуряват гаранции в най-лошия случай (worst-case guarantees); например много структури от данни, използвани в компютърната геометрия, може да са базирани на Червено-черно дървета, а Completely Fair Scheduler, използван в сегашните Линукс ядра използва Червено-черни дървета.
АВЛ Дървото е друга структура, която поддържа O(log n) търсене, вмъкване и изтриване. Тя е по-строго балансирана отколкото Червено-черните дървета, което води до по-бавно вмъкване и изтиване, но по-бързо обработване. Това го прави привлекателно за структури от данни, които могат да бъдат изградени веднъж и заредени без реконструкция, като например езикови речници (или програмни речници, като опкодовете на един асемблер или интерпретатор).
Червено-черните дървета също са особено ценни във функционалното програмиране, където те са едни от най-често срещаните устойчиви структури от данни, използвани за изграждане на асоциативни масиви и сетове, които могат да запазят предишните версии след промени. Постоянната версия на червено-черните дървета изисква O(log n) пространство за всяко вмъкване или изтриване, в допълнение към времето.
За всяко 2–4 Дърво има съответстващи Червено-черни дървета с елементи на данните в същия ред. Операциите на вмъкване и изтриване върху 2–4 Дървета също са еквивалентни на промяната на цвета и ротациите в Червено-черните дървета. Това прави 2–4 Дървото важен инструмент за разбиране на логиката зад Червено-черните дървета и това е причината много уводни текстове за алгоритми да представят 2–4 Дървета точно преди Червено-черните дървета, въпреки че 2–4 Дърветата не са често използвани в практиката.
През 2008 г., Седжуик въвежда по-опростена версия на Червено-черно дърво, наречена Ляво наклонено червено-черно дърво (LLRB) чрез елиминирането на по-рано неуточнена степен на свобода в изпълнението. LLRB поддържа допълнителен инвариант, че всички червени връзки трябва да са ляво наклонени, освен по време на вмъкване и изтриване. Червено-черните дървета могат да бъдат направени изометрични до 2–3 Дървета, или 2–4 Дървета, за всяка последователност от операции. Изометрията на 2–4 Дърветата е описана през 1978 г. от Седжуик. С 2–4 Дървета изометрията е решена чрез „обръщане на цвета“ (color-flip), съответстваща на раделяне, в което червеният цвят на два възела на децата науска децата и се движи към възела родител.
Дървото танго е оптимизирано за бързо търсене и използва Червено-черно дърво, като част от неговата структура от данни.
Операции Операциите „само за четене“ (read-only) на Червено-черно дърво не се нуждаят от промяна спрямо тези, използвани за двоично дърво за търсене, защото всяко Червено-черно дърво е специален случай на просто двоично дърво за търсене. Въпреки това, прекият резултат на вмъкване или изтриване може да наруши свойствата на Червено-черното дърво. Възстановяването на свойствата на Червено-черно дърво изисква малък брой (O(log n) или амортизирано O(1)) промени в цвета (които са много бързи практически) и не повече от три ротации в дърветата (две за вмъкване). Въпреки че операциите вмъкване и изтриване са сложни, техните времена остават O(log n).
Вмъкване Вмъкването започва чрез добавяне на възел както при всяко вмъкване при двоично дърво за търсене и чрез оцветяването му в червено. Докато в двоичното дърво за търсене винаги добавяме лист, в червено-черното дърво листата не съдържат информация, така че вместо това прибавяме червен вътрешен възел с две черни листа, на мястото на съществуващ черен лист.
Какво се случва след това зависи от цвета на другите близки възли. Терминът uncle node ще се използва за означаване на сродните на основния възел, както в човешките родословни дървета. Трябва да се отбележи, че: свойство 3 (всички листа са черни) винаги се запазва.