red-black trees : Java Glossary

red-black trees
This is the modern equivalent of IBM (International Business Machines) ’s old ISAM (Indexed Sequential Access Method) 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).

CMP homejump to top

available on the web at:

http://mindprod.com/jgloss/redblacktree.html
  

optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\jgloss\redblacktree.html
logo
Please email your , letters to the editor, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green : feedback email. If you want your message, your name or email kept confidential, not considered for public posting, please explicitly specify that. Unless you state otherwise, I will treat your message as a letter to the editor that I may or may not publish in the feedback section. After that, it will be too late to retract it. If you disagree with something I said, especially when sending an ad-hominem attack, a rant composed mainly of obscenities or a death threat, please quote the offending passage and cite the web page where you found it, tell me why you think it is wrong, and, if possible, provide some supporting evidence. I can’t very well fix erroneous or ambiguous text if I can’t find it.
Blog
IP:[65.110.21.43]
Your face IP:[107.20.7.65]
You are visitor number 14,829.