Rød-svart tre

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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.[1]

Referanser[rediger | rediger kilde]

  1. ^ 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.
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.