red-black trees : Java Glossary

by Roedy Green ©1996-2008 Canadian Mind Products
Go to : punctuation 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (all)

red-black trees: This is the modern equivalent of IBM’s old ISAM Indexed Sequential Access Method or SoftCraft’s Btrieve. Red-black trees allow you to both iterate through a collection in the proper sequential order and lookup directly by key. A red-black tree is a binary search tree that uses an extra bit on every node to store the node’s "colour", (Colour is just an analogy. It has nothing to do with light.) Red-black trees constrain the way that nodes may be coloured in such a way that the tree remains reasonably balanced. This property is important for insuring a good overall performance — red-black trees guarantee that the worst case performance for the most common dynamic set operations is O(log N).
STL

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.16]	The information on this page is for non-military use only.
	You are visitor number 8,691.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/Mindprod website mirror)
	http://mindprod.com/jgloss/redblacktree.html	J:\mindprod\jgloss\redblacktree.html