GitLab

(This is just a placeholder for future ideas for refactoring some RBT...)

Since RBT was invented in seventies, there has been some improvements to the algorithm since, namely:

• Lock-Free Red-Black Trees Using CAS
  • https://www.cs.umanitoba.ca/~hacamero/Research/RBTreesKim.pdf
  • http://swapnil-pimpale.github.io/lock-free-BST/
• Left-leaning Red-Black Trees:
  • http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
  • http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282
  • http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
  • http://www.mew.org/~kazu/proj/red-black-tree/
  • http://25thandclement.com/~william/projects/llrb.h.html
• OpenBSD's <sys/tree.h>:
  • https://ftp.netbsd.org/pub/NetBSD/NetBSD-current/src/sys/sys/tree.h