[so] Arbori balansati in nucleul Linux

[Razvan Deaconescu]

Salut!

A aparut o intrebare dupa curs legata de folosirea arborilor
rosu-negru[1] in loc de arbori AVL[2] in nucleul Linux.

Ce am aflat ( Google helps :-) ):
* arborii rosu-negru sunt folositi in diverse subsisteme ale nucleul
(memory management, I/O scheduling)[3]
* aparent, decizia de comutare de la arbori AVL la arbori rosu-negru a
survenit in 1999[4], pentru perfomanta mai buna in subsistemul de memory
managemet (mm)
* arborii rosu-negru permit inserari si eliminari mai rapide, in timp ce
arborii AVL permit accese mai rapide

Razvan

[1] http://en.wikipedia.org/wiki/Red-black_tree
[2] http://en.wikipedia.org/wiki/AVL_tree
[3] http://www.kernel.org/doc/Documentation/rbtree.txt
[4] http://mail.nl.linux.org/linux-mm/1999-11/msg00084.html