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 varandra längs någon stig); och varje väg från roten till en Nil-nod (svart sentinel) har samma antal svarta noder. Dessa regler gör trädet självbalanserande utan att behöva helt jämna höjder.

Operationer som insättning och borttagning genomförs oftast med rotations- och färgändringsfaser som återställer de tre grundläggande egendomarna vid behov. Rotationsoperationer (vänster- och högerrotation) samt omfärgning används för att bevara balansen. Sök i ett rödsvartträd tar O(log n) tid i ordnade träd med n noder.

Användningen är bred inom datorprogrammering: rödsvartträd används som underliggande struktur för många ordnade samlingar i olika programmeringsspråk. Exempel på implementeringar finns i C++ STL (associativa behållare som std::map och std::set) och i Java:s TreeMap och TreeSet, där operationer i ordnade tabeller uppnås med hjälp av red-black-träd.

Historia och varianter: red-black-trädet uppfanns av Rudolf Bayer 1972 som en representation av 2-3-träd. En vanlig variant är vänster-leaning red-black tree (LLRB) som förenklar implementeringen genom att använda en särskild tolkning av färg och rotationer medan egenskaperna bevaras.