Rød-sort træ: Selvbalancerede binære søgetræer forklaret med eksempler

Hvad er et rød-sort træ?

Rød-sort træ er en type selvbalancerende Binary Search Tree (BST). I et rød-sort træ følger hver knude disse regler:

  1. Hver knude har to børn, farvet enten rød eller sort.
  2. Hver træbladknude er altid sort.
  3. Hver rød knude har begge sine børn farvet sort.
  4. Der er ikke to tilstødende røde noder (En rød node kan ikke have en rød forælder eller et rødt barn).
  5. Hver sti fra rod til en træbladknude har det samme antal sorte knudepunkter (kaldet "sort højde").

Indsættelse i rød-sorte træer

En node indsættes oprindeligt i et rød-sort træ ligesom ethvert binært søgetræ. Den nye knude får derefter en rød farve. Når denne node er indsat, skal træet valideres for at sikre, at ingen af ​​de fem egenskaber er blevet krænket. Hvis en ejendom er blevet overtrådt, er der tre potentielle tilfælde, der enten kræver venstre rotation, højre rotation og / eller omfarvning af noderne. Sagerne er afhængige af "onkelen" for den aktuelle node. Specifikt om "onkel" -noden er sort eller rød. For mere info om indsættelse kan de tre sager findes her.

Venstre-lænet rødt-sort træ

Et venstreorienteret rød – sort (LLRB) træ er en type selvbalancerende binært søgetræ. Det er en variant af det rød-sorte træ og garanterer den samme asymptotiske kompleksitet til operationer, men er designet til at være lettere at implementere.

Egenskaber ved venstre skæve rød-sorte træer

Alle de rød-sorte træalgoritmer, der er blevet foreslået, er kendetegnet ved en værst tænkelig søgetid afgrænset af et lille konstant multiplum af log N i et træ med N-nøgler, og den adfærd, der observeres i praksis, er typisk det samme multiple hurtigere end i værste fald bundet tæt på de optimale log N-noder, der blev undersøgt, og som ville blive observeret i et perfekt afbalanceret træ.

Specifikt i et venstreorienteret rød-sort 2-3-træ bygget fra N tilfældige taster: -> En tilfældig vellykket søgning undersøger log2 N- 0,5 noder. -> Den gennemsnitlige træhøjde er ca.2 log2 N