rödsvartträd
Rödsvartträd, eller red-black tree, är en självbalanserande binär sökträdsstruktur som används inom datavetenskapen för att lagra nyckel-värde-par i ordnade samlingar. Varje nod har en färg, antingen röd eller svart, och trädet upprätthåller egenskaper som garanterar nära logaritmisk tid för grundläggande operationer som sök, insättning och borttagning.
Egenskaperna inkluderar att roten är svart; varje röd nod har svarta barn (inga två röda noder bredvid
Operationer som insättning och borttagning genomförs oftast med rotations- och färgändringsfaser som återställer de tre grundläggande
Användningen är bred inom datorprogrammering: rödsvartträd används som underliggande struktur för många ordnade samlingar i olika
Historia och varianter: red-black-trädet uppfanns av Rudolf Bayer 1972 som en representation av 2-3-träd. En vanlig