]> sourceware.org Git - newlib-cygwin.git/commit
sys/tree.h: Red child with black sibling rotations
authorSebastian Huber <sebastian.huber@embedded-brains.de>
Tue, 5 Oct 2021 13:53:47 +0000 (15:53 +0200)
committerSebastian Huber <sebastian.huber@embedded-brains.de>
Thu, 7 Oct 2021 15:58:36 +0000 (17:58 +0200)
commiteb03ac17f16f1bd354482148426353fd35cd879d
tree33978d6fc1d9a392d679ebe1ff2a2673a9154ce3
parent5f7f27c81736c11c35c119cc5f18231eb8aaecec
sys/tree.h: Red child with black sibling rotations

Add specialized rotations RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() which
may be used if we rotate a red child which has a black sibling.  Such a red
node must have at least two child nodes so that the following red-black tree
invariant is fulfilled:

  Every path from a given node to any of its descendant NULL nodes goes through
  the same number of black nodes.

      PARENT
     /      \
  BLACK     RED
           /   \
        BLACK BLACK
newlib/libc/include/sys/tree.h
This page took 0.026627 seconds and 5 git commands to generate.