Overview

Implementation of Red-Black search tree.

Cloning & Building

• Firstly, copy source files or clone this repository: git clone [email protected]:RustamSubkhankulov/rbtree.git.
• Secondly, change current working directory: cd rbtree
• Thirdly, build tests:
  • cmake -B build
  • cmake --build build [--target <target_name>] , where <target_name> is available test option (see below). Omitting --target option will cause all targets to build. Executables are located in ./build/bin subdirectory.

Testing

Available test options are:

1. Interactive end-to-end tests: custom_query and sdtset_query - builds executables in ./build/bin subdirectory, that should be executed explicitly by user. Interactive test reads input from stdin and performs range queries of two types: 'k' - insertion - and 'q' - distance. Insertion query takes one int argument - this argument is inserted in tree. Distance query takes two arguments and calculates distance between two elements in tree. Second element must be greater or equal than the first. Result is written out to stdout. RBTREE::rbtree and std::set are used in custom_query and stdset_query tests accordingly. Example of input: k 10 k 20 k 30 q 10 30 q 20 20 q 10 20 Output in this case will be: 2 0 1

Options, available for configuring interactive testing:

• STDDIST - enables use of std::distance for q-queries instead of fast distance implementation in custom_query target.
• MEASURE_TIME - disables output of results on interactive test and enables time measurement with std::chrono features. Works for both custom_query and stdset_query tests. Instead of result of queries, test will show elapsed time. Results of queries are written to file res.txt. Example of output: Elapsed time: 1 ms 527 µs 166 ns
• DEBUGcode> - enables additional debug info printing in custom_query and stdset_query tests.
• DUMP_DOT - enables graphical dump at the end of custom_query test. Output is dot.txt file in project directory root, containing dump in dot format, that could be converted to image using 'dot'.

2. unit and query - these tests are implemented with GoogleTest. To run tests, following commands should be run after building targets:

• cd build
• ctest

Unit testing performs separate test for each interface method of RBTREE::rbtree. Query testings tests queries methods, that are used in interactive testing mode.

Debug features

1. Graphical dump. To make graphical dump, use graph_dump() RBTREE::rbtree method. This method is overloaded. One its overlod takes one argument - name of the output image file, relative to the current working directory, another - std::basic_ostream, where dot graphical dump will be written to.
2. Debug compilation flags. Enabled by option 'DEBUG_GLAGS'. Enables additional warnings during compilation. Forcefully disabled with CMAKE_BUILD_TYPE=RELEASE.

Performance comparison

RBTREE::rbtree provides additional features for fast computing of distance between two nodes. Tree method distance() takes two arguments - two iterators to elements in tree or two keys. This method uses subtree sizes, stored in nodes of the tree for faster calculation of distance comparing to std::distance.

For comparison, python script, that generates queries sequences, is written (scripts/query_gen.py). This scripts takes several args: number of elements in tree and name of the output file, where queries will be written. For example, if first arg is 10, 10 insertion k-queries for numbers from 0 to 9 including and distance q-queries for every pair of elements (except pairs where first and last are equal) will be generated.

Script does not generate random sequence of queries, that include both insertion and distance mixed up. Methods for generating a sequence of queries were chosen in such a way as to most clearly show the difference between std::distance and RBTREE::rbtree::distance.

For measuring time of queries executing std::chrono::steady_clock> was used. For measuting total execution time cli time util was used.

Results of comparison:

N, number of elements	RBTREE::rbtree::distance	std::distance
200	0,072	0,128
500	0,633	0,743
750	1,047	1,286
1.000	1,833	2,498
1.500	4,290	6,185
2.000	8,010	12,626
2.500	12,299	21,509
3.000	18,234	37,474
3.500	24,756	58,494
5.000	50,709	158,41
7.500	175,15	513,59