blob: d69eb8d3e33ef712145eb586d74543d1a505b84a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
|
test_rbtree is a test module for checking the correctness of red-black
tree operations.
These tests are performed on red-black trees that store integers.
Since the rbtree logic treats the comparison function as a black
box, it shouldn't be important exactly what the key type is.
Checking the correctness of traversals is based on the fact that a red-black
tree is a binary search tree, so the elements should be visited in increasing
(for Left-Current-Right) or decreasing (for Right-Current-Left) order.
Also, this module does some checks of the correctness of the find, delete
and leftmost operations.
|
