cltnrbtree.pas

Delphi技术手册源码 Delphi技术手册源码

unit CltnRbTree;

(*
  Red-black trees.
  The trees implement the ISet and IMap interfaces, using red-black trees
  as the implementation. See Introduction to Algorithms, by Cormen, Leiserson,
  and Rivest for details.

  The "color" of each node is stored by setting or clearing the
  least-significant bit in the node's parent pointer. This trick works
  because the LSBit is clear for word-aligned pointers. Delphi always allocates
  memory on aligned boundaries, so the least significant bit is always zero.

  Note that saving 4 bytes of memory improves performance and more than
  compensates for the additional time needed to access the parent
  pointer and color. Performance tests on an AMD K6-2/266 show that
  using this trick is about 10% faster than using simple, direct
  properties for parent and color. If you don't believe me, find out
  for yourself by defining the "DIRECT" compiler macro.

  Copyright