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