Arbori roșii și negri: descriere, caracteristici

Rudolf Bayer a dezvoltat sistemul de "copaci roșu-negru" la începutul anilor 1970. Numele lui a fost dat lui L. Gimpas și R. Sedgwick.

Ce copaci roșu-negru

Trebuie remarcat faptul că acestea sunt un tip de arbori binari care se auto-echilibrează, oferind o dimensiune de înălțime care se poate număra din numărul de noduri și care generează într-un timp scurt procesele primare și de bază ale arborelui de căutare. Aceste operațiuni includ atașarea, ștergerea și găsirea unui nod. Soldul este furnizat pe baza completării atributului de desemnare a aplicației nodului, culoare. Această proprietate preia unul dintre conceptele posibile și este marcată de una dintre culorile menționate.

Numărul de unități negre de pe ramură de la început (rădăcină) la final (frunze) se numește înălțimea negru a copacului.

Apariția termenului

Descriind un arbore de căutare cu auto-echilibrare în lucrarea sa, autorii articolului probabil că nici măcar nu se așteptau să devină fondatorii noului termen. Cu toate acestea, soarta a ordonat ca tipografia să fi avut în stoc doar două culori. De asemenea, au notat fiecare bit care se alătură noului nod.

cerere

În domeniul informaticii, copacii roșu-negru sunt utilizați pentru a genera date comparabile, care pot include diferite fragmente și părți de inscripții sau cifre.

Puteți crea un arbore roșu-negru pe Actionscript, Python, C ++ și aproape orice alt limbaj de programare. Este foarte simplu. Arborele Java rosu-negru este, de asemenea, destul de răspândit.

caracteristici

Copacii de culoare roșie și roșie sunt arbori de căutare în sistemul de coordonate binare. În aceste sisteme, orice nod are o anumită valoare de culoare. Poate să ia una dintre notele de mai sus. În plus față de toate condițiile aplicate copacilor binari, la soiurile luate în considerare, se aplică și aceste reguli:

• Culoarea nodului este exclusiv una dintre cele două de mai sus. Nu există alte opțiuni, se reflectă și în numele termenului.
• Rădăcina copacului ar trebui întotdeauna să fie pictată în negru. Excepțiile sunt posibile, însă o astfel de abatere de la regula adaugă riscul ca acel copac să se autocarbească.
• Toate frunzele au o valoare nulă (NIL) și sunt notate cu culoarea neagră.
• Este important să se asigure că cei doi descendenți ai fiecărui nod părinte roșu sunt negri.
• Orice curs ușor de la un nod particular la orice nod de tip foarfece oferă exact același număr de unități structurale negre.

Uneori, copacii roșu-negru sunt interpretați ca arbori binari de căutare banali. Diferențele lor sunt determinate numai de faptul că în locul anumitor noduri colorate, valorile menționate mai sus sunt coaste colorate.

De ce să alegeți exact copaci roșu-negru

Copacii de culoare roșie și roșie reprezintă una dintre cele mai comune variante de arbori binari de auto-echilibrare, care sunt abordați cel mai adesea în termeni practici.

Ce explică popularitatea lor? Practica este leneșă și merită admisă. Orice lucru care este prea greoaie și greu de utilizat, și în același timp produce un rezultat similar similar atunci când se aplică metode mai simple, moare sau merge în viitorul îndepărtat. O asemenea prevalență în rândul copacilor roșu-negru se explică prin faptul că acestea oferă cel mai adesea un echilibru optim între calitatea și nivelul echilibrului și viclenia de întreținere.

De exemplu, dacă le comparăm cu cele care sunt perfecte în măsura echilibrului lor de către copaci, atunci poate fi o situație când se observă că reprezentanții "ideal" impun exigențe prea extinse. Și în condițiile punerii în aplicare a acțiunilor de excludere din arbore sau de inversare, prea mult timp și efort sunt cheltuite pentru stabilizarea echilibrului necesar în această situație.

procese

Procesul de verificare a copacilor binar negru și roșu este aproape același pentru toate celelalte ramuri de căutare binară. Acest lucru este adevărat, deoarece orice copac negru-roșu este una dintre variantele particulare ale arborelui binar clasic de căutare.

Cu toate acestea, atunci când se lucrează cu acestea, trebuie să se țină seama de faptul că este mai probabil ca producția directă a acțiunii de includere sau excludere a datelor să poată afecta structura copacilor negri și roșii. Un avantaj imens este că, pentru reconstrucția proprietăților, este necesar un număr relativ mic de acțiuni, cum ar fi schimbarea culorilor și adesea mai puțin de trei rotații ale unui copac. De fapt, toate aceste operațiuni nu necesită prea mult timp.

Pentru a continua acțiunea de a introduce sau de a activa un element, este necesar să creștem nodul ulterior. Această funcție este similară în toți arborii binari de căutare. Următorul pas este să colorați nodul în roșu. Singura diferență este că dacă adăugați mai întâi foaia atunci când efectuați o inserare în arborele de căutare binar, atunci negru și roșu nu transporta nicio informație. Prin urmare, în locul lor, se adaugă un nod intern care are o culoare roșie și cei doi descendenți ai lui negru.

Mai departe, acțiunile noastre sunt condiționate direct de culoarea nodurilor adiacente. Pentru ei, termenul "unchiul" este folosit. Analogie directă cu arborele genealogic. Prin urmare:

• Caracteristica că toate frunzele păstrează o culoare neagră trebuie să fie întotdeauna realizată.
• Secvența faptului că cele două derivate ale fiecărui nod roșu păstrează o culoare neagră poate fi întreruptă. Dar acest lucru se întâmplă numai atunci când adăugați un nod roșu, când schimbați culoarea negru în roșu sau când întoarceți întregul copac.
• De asemenea, rețineți că secvența de la nod la foaie, incluzând același număr de noduri negre, poate fi încălcată. Acest lucru se întâmplă numai când nodul negru este pornit, elementul roșu este schimbat în negru, iar în situația opusă revopsării culorii negre în roșu. Acest lucru se poate face și în timpul răsucirii arborelui.

După ce am studiat toate cele de mai sus, nu este greu de înțeles cum se efectuează căutarea într-un copac roșu-negru.

Interpretarea unui concept atât de simplu ca un copac este interesantă, cu o descriere a culorii sale - roșu-negru sau negru-maro. Acum sunteți, de asemenea, conștienți de acest lucru.