Rød-svart tre

Et rød-svart tre er en form for selvbalanserende binært søketre. Hver node i det binære treet har et ekstra bit, som dette bit blir ofte tolket som fargen (rød eller svart) til noden. Disse fargebitene benyttes for å sikre at treet forblir omtrentlig balansert under innsetting og slettinger.  Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.

Referanser

Kategori:Trær (datastrukturer)