Рудолф Байер развива системата на "червено-черните дървета" в началото на 70-те години. Името на същото е дадено на L. Gimpas и R. Sedgwick.

Какво ще кажете за червените и черните дървета

Струва си да се отбележи, че те са един от видовете самобалансиращи се двоични дървета, които осигуряват преброявана височина на броя на възлите и произвеждат основните и основни процеси на дървото за търсене за кратко време. Тези операции включват присъединяване, изключване и проследяване на сайта. Балансът се предоставя въз основа на допълнението към атрибута на приложението на цветовия код на сайта. Това свойство поема една от вероятните концепции и се обозначава с един от споменатите цветове.


Броят на черните единици на клоните от началото (корен) до финала (буква) се нарича черна височина на дървото.

Появата на термина

Авторите на статията, които описват самобалансиращото се дърво на търсенето, вероятно дори не са предположили, че ще станат основатели на нов термин. Съдбата обаче е наредена така, че печатницата е в присъствието на боя само на два цвята. Те също така маркираха всеки бит, който се присъединява към следващия възел.

Прилагане

В областта на информатиката червените и черните дървета се използват за формиране на съпоставими данни, които могат да включват различни експозиции и части от надписи или цифри. Можете да създадете червено-бяло дърво на Actionscript, Python, C ++ и почти всеки друг език за програмиране. Това е много просто. Червеното черно Java дърво също е хубавошироко разпространена.

Характеристики

Черно-червените дървета са дървета за търсене в двоична координатна система. В тези системи всеки сайт има определена цветова стойност. Той може да поеме един от гореспоменатите символи. В допълнение към всички условия, приложими към двоичните величествени дървета, към разглежданите от нас видове, се използват и следните правила:

Цветът на обекта е единствено от гореспоменатите два. Няма други опции, това се отразява и в името на термина.

Коренът на дървото трябва винаги да бъде черен. Изключения са възможни, но тази дерогация от правилото добавя риска, че самобалансирането на дървото ще се срине.

Всички листа имат нулева стойност (NIL) и са маркирани в черно.

Необходимо е да се гарантира, че двете потомци на всеки червен родителски възел са черни.

Всеки светлинен ход от специфичен възел към всеки допълнителен възел на листа осигурява точно равен брой черни структурни единици. Понякога червените и черните дървета се интерпретират като тривиални двоични дървета за търсене. Разликите им се определят само от факта, че в замяна на някои цветни възли, горепосочените стойности са филцови ребра.

Защо да изберем червените черни дървета

Черно-червените дървета представляват един от най-често използваните варианти на самобалансиращи се двоични дървета за търсене, които най-често се споменават на практика. Какво прави тази популярност ясна? Практиката е мързелива и си струва да се признае. Всичко е твърде тромавои трудно да се използва и в същото време дава сравнително сходни резултати при прилагането на по-прости методи, умира или изчезва в далечния план. Това разпространение на червено-черните дървета в хората се дължи на факта, че те най-често осигуряват оптимален баланс между качеството и нивото на баланс и zakovrystosti на неговата подкрепа. Например, ако ги сравним с перфектно балансирани дървета, тогава може да има ситуация, при която се наблюдава, че "идеалните" представители налагат твърде несъвместими изисквания. И по отношение на осъществяването на действието на изключване от дърво или обръщането на твърде много време и усилия се изразходва за стабилизиране на баланса в дадена ситуация.

Процеси

Процесът на проверка на черно-червените двоични дървета е почти еднакъв за всички други търсения с двоично разклоняване. Точно така, защото всяко черно-бяло дърво е една от частните опции на класическото двоично дърво за търсене. Работата с тях обаче трябва да отчита по-голямата вероятност, че директното производство на включването или изключването на данни може да навреди на структурата на черните и червените дървета. Голямо предимство е, че са необходими сравнително малък брой действия за възстановяване на свойствата, като промяна на цветовете и по-малко от три завъртания на дърво. Всъщност всички тези операции не отнемат много време. Стартирането на действие за вмъкване или вмъкване на елемент струва да се добави към следващия възел. Тази функция е еднаква за всички двоични дървета за търсене.Следващата стъпка е да оцветите възела в червено. Единствената разлика е, че ако вмъкването на едно двоично дърво за търсене първо добавя буква, то в черно и червено последно няма информация. Следователно вместо тях се добавя вътрешен възел, получаващ червения цвят и два от черните му потомци. По-нататъшните ни действия са пряко обусловени от цвета на съседните възли. За тях се използва терминът "чичо". Директна аналогия с родословното дърво. Следователно:

Характеристиката на факта, че всички листа са черни на цвят, трябва винаги да се прилага.

Последователността на факта, че две производни на всеки червен възел остават черни на цвят, може да бъде прекъсната. Но това се случва само при добавяне на червен сайт, когато се променя цвета на черното на червеното или когато се разпространява цялото дърво.

Също така отбелязваме, че последователността от възел до буква, която включва същия брой черни възли, може да бъде засегната. Това се случва само при включване на черния възел, като се сменя червения елемент в черно, както и в обратна ситуация, черно и червено пребоядисване. Същото може да се окаже и при обръщането на дърветата.

След като проучи всичко по-горе, е лесно да разберете как да търсите в червено и черно дърво. Интересна интерпретация на такова просто понятие като дърво, с описание на неговия цвят - червено-черно или черно-кафяво. Сега сте наясно с това.