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 lui R. Sedgwick.

Ce copac rosu-negru

Trebuie remarcat faptul că aceștia sunt un tip de arbori binari de auto-echilibrare, care oferă o mărime de înălțime care poate fi numărat din numărul de noduri și care generează procese primare și de bază ale arborelui de căutare într-un timp scurt. Astfel de operațiuni includ atașarea, excluderea și căutarea 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 neagră 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ă aibă doar două culori disponibile. De asemenea, au notat fiecare bit care se alătură nodului următor.

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 figuri.

Puteți crea un arbore roșu-negru pe Actionscript, Python, C ++ și aproape orice alt limbaj de programare. Este foarte simplu. Arborele roșu-negru Java 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 binar. În aceste sisteme, orice nod are o anumită valoare a culorii. 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ă enumerate mai sus. Nu există alte opțiuni, se reflectă și în numele termenului.
• Rădăcina copacului trebuie întotdeauna să fie vopsită în negru. Excepțiile sunt posibile, însă o astfel de abatere de la regula adaugă riscul de a se autocalibra.
• 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 cale ușoară de la un anumit nod la orice nod copil frunzit 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 banale. Diferențele lor sunt determinate numai de faptul că, în locul anumitor noduri colorate, coastele sunt colorate în valorile de mai sus.

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 se adresează cel mai adesea în termeni practici.

Ce explică popularitatea lor? Practica este leneșă și merită să recunoaștem. Orice lucru care este prea greoi și greu de folosit, și în același timp produce un rezultat comparabil cu metodele mai simple, moare sau merge în viitorul îndepărtat. O asemenea prevalență în rândul copacilor roșu-negru se explică prin faptul că ele 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 apărea o situație în care se observă că reprezentanții "ideal" impun exigențe excesive. Iar în condițiile implementării acțiunilor de excludere din arbore sau de inversare, se petrece prea mult timp și efort pentru stabilizarea echilibrului în situația dată.

procese

Procesul de verificare a copacilor binari 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. Avantajul uriaș 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 durează prea mult.

Pentru a continua acțiunea de a introduce sau a activa un element, este necesar să creștem următorul nod. 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 inserați î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 săi negri.

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 atunci când nodul negru este pornit, elementul roșu se schimbă în negru și, de asemenea, în situația opusă de revopsire negru la 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 simplu de 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.