Червени и черни дървета: описание, функции

Рудолф Байер разработи системата от "червено-черни дървета" още в началото на 70-те години. Името на това бе дадено на Л. Гимпас и Р. Седжуик.

Какво червено-черно дърво

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

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

Появата на понятието

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

приложение

В областта на компютърната наука червено-черни дървета се използват за генериране на сравними данни, които могат да включват различни откъси и части от надписи или фигури.

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

Удобства

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

• Цветът на възела е един от изброените по-горе. Няма други опции, отразява се и в името на термина.
• Коренът на дървото трябва винаги да бъде боядисан в черно. Изключения са възможни, но такова отклонение от правилото увеличава риска дървото да се самоизравните.
• Всички листа имат нулева стойност (NIL) и са обозначени с черен цвят.
• Важно е да се гарантира, че двамата потомци на всеки червен родителски възел са черни.
• Всяка лесна пътека от конкретен възел към всеки листов детски възел осигурява точно същия брой черни структурни единици.

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

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

Черно-червените дървета са един от най-разпространените варианти на самобалансиращи се двоични дървета за търсене, които най-често се разглеждат в практически план.

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

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

процеси

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

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

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

Освен това нашите действия са пряко обусловени от цвета на съседните възли. За тях се използва терминът "чичо". Пряка аналогия с генеалогичното дърво. Ето защо:

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

След като проучихме всичко това, не е трудно да се разбере как се извършва търсенето в червено-черно дърво.

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