Light-rbtree is a red black tree library implemented in C language. Although it has a relatively small amount of code, its performance is very powerful. It supports single command insertion, deletion and search. The best thing is that it supports C language for style traversal iterators and supports medium order traversal and subsequent traversal respectively.

It does not has any external dependency, so just make it directly in the project root directory.

cd light-rbtree
make

After you finish compiling above, you can run some simple tests.

./examples/simple
./examples/benchmark

Here is the output of benchmark:

Generate 1000000 Node:
  real time: 0.420000
  user time: 0.410000
  kern time: 0.000000
  rb deepth: 24
Middle Iteration:
  real time: 0.080000
  user time: 0.080000
  kern time: 0.000000
Postorder Iteration:
  real time: 0.080000
  user time: 0.070000
  kern time: 0.000000
Deletion All Node...
Done.

Light-rbtree library requires only two files to complete the migration.

src/rbtree.c
src/rbtree.h

The light rbtree library itself does not perform operations such as comparison, but uses a callback function to let users compare and return a result (greater than zero, less than zero and equal to zero). Therefore, in theory, we can insert infinite data into the red black tree. This design concept is applied to finding nodes (passing in a private data) and finding parent nodes during insertion (comparing two red black tree nodes).

This is an open source red black tree library, which uses the GPLV2 protocol

The Tencent QQ Group number is: 763756024