Կարմիր-սև ծառի ներածություն


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon CodeNation facebook Google Uber
Տվյալների առաջադեմ կառուցվածք Երկուական որոնման ծառ Երկուական ծառ Տվյալների կառուցվածքը ծառ

Կարմիր Սև ծառը ինքնահավասարակշռող երկուական ծառ է: Այս ծառում յուրաքանչյուր հանգույց կա՛մ կարմիր հանգույց է, կա՛մ սեւ հանգույց: Այս Կարմիր-սև ծառի ներածության մեջ մենք կփորձենք ծածկել դրա բոլոր հիմնական հատկությունները:

Կարմիր-սև ծառի հատկությունները

  1. Յուրաքանչյուր հանգույց ներկայացված է ինչպես կարմիր, այնպես էլ սև:
  2. Արմատային հանգույցը միշտ սեւ է:
  3. Կարմիր հանգույցը չի կարող ունենալ կարմիր ծնող կամ կարմիր երեխա (այսինքն `ոչ մի երկու կարմիր հանգույց հարակից չէ):
  4. Pathանկացած հանգույցից դեպի NIL հետնորդ յուրաքանչյուր ուղի պետք է պարունակի հավասար թվով սեւ հանգույցներ:

Կարմիր-սև ծառի վավեր և անվավեր օրինակներ

Կարմիր-սև ծառի ներածություն

Կարմիր-սև ծառի ներածություն

Timeամանակի բարդության վերլուծություն

BST- ի բոլոր գործողությունները, ինչպիսիք են որոնումը, տեղադրումը, ջնջումը և այլն, կարող են կատարվել O (h) ժամանակում, որտեղ h- ը կարմիր-սև ծառի բարձրությունն է, և BS- ի համար հավասարակշռված բարձրությունը միշտ կարգի է տեղեկամատյան (n) [n-> հանգույցների քանակը]:

Որոնում = O (տեղեկամատյան (n))
միացում = O (տեղեկամատյան (n))
ջնջում = O (տեղեկամատյան (n))

Սև հասակը Կարմիր-Սև ծառում

Կարմիր-սև ծառի Սև հասակը սահմանվում է որպես սև հանգույցների քանակը պարզ ուղու վրա (նույն հանգույցը երկու անգամ չեք այցելում) ցանկացած հանգույցից դեպի տերև (որը NIL է): Այն ներկայացված է bh (x) - ով:

Կարմիր-սև ծառի բարձրությունը

Ի տարբերություն AVL ծառ, բարձրության հաշվեկշիռը այնքան էլ խիստ չէ, բայց կարմիր-սև ծառերում պտույտների քանակը ավելի քիչ է, համեմատած AVL ծառերի հետ:
Կարմիր-սեւ ծառի բարձրությունը h <= 2 (տեղեկամատյան (n + 1)) {Գրանցման հիմքը 2} Մանրամասն ապացույց թե ինչու է RB ծառերի բարձրությունը <= 2 մատյան (n + 1):

Բարձրության վրա հավասարակշռությունը պահպանելու համար կարմիր-սեւ ծառը օգտագործում է վերափոխում և վերակազմավորում:

Դուք կարող եք տեսնել, թե ինչպես են RB ծառերը վերափոխվում և վերակազմավորվում այստեղ.

Գունաթափում

Այն վերաբերում է որոշ կարմիր հանգույցների գույնը սեւով փոխելուն և հակառակը, դա արվում է ամեն անգամ, երբ կարմիր հանգույցի կարմիր ծնողի եղբայրը կամ քույրը կարմիր է:

Կարմիր-սև ծառի ներածություն

 

Վերակազմակերպում

Այն վերաբերում է ծառի ռոտացիային, դա արվում է ամեն անգամ, երբ կարմիր երեխա ունի կարմիր ծնող և սև կամ առերես քեռի: Վերակազմավորման մեջ կա չորս դեպք,

  • Իրավունք
  • Left
  • Աջ ձախ
  • Ձախ աջ

Ծրագրեր

  • Իրական գրադարաններում օգտագործվում է ինքնահավասարակշռող ԲՍՏ-ներ իրականացնելու համար:
  • Օգտագործվում է որպես TreeSet և TreeMap- ը JAVA- ում և Կոմպլեկտներ և Քարտեզներ C ++ - ում:

Որոնում

Կարմիր-սեւ ծառը BST է, ուստի RBT- ում որոնումը ճիշտ նույնն է, ինչ BST- ում փնտրելը, հանգույցի գույնը նշանակություն չունի: