|
/** |
|
* Warning this function is very expensive. |
|
*/ |
|
template <typename TreeT> |
|
void testRedBlackPropertyViolation(TreeT const& tree) |
I don't think it has to be that expensive. Red-black tree properties are:
- Every node is either red or black.
- The root node must be black.
- All leaf nodes (null or NIL nodes) are considered black.
- If a node is red, then both its children must be black (no two consecutive red nodes).
- Every path from a given node to any of its descendant leaf nodes contains the same number of black nodes.
It should be possible to check all of these not only in linear time, but in one pass over the tree. Current implementation seems to be checking the 5th item twice:
- using
blackHeight recursive function (linear)
- using
leafCollector + the loop in the end of the function (lines 75-97). This is $O(n^2)$, since it recomputes paths from the leaves to each node again and again.
The second is ineffective and redundant. Removing it and moving all per-node checks inside the function which traverses a tree allows running all checks in one pass. This should allow running tree violation checks more often in unit tests. I will prepare a PR shortly.
interval-tree/tests/test_utility.hpp
Lines 11 to 15 in 875b625
I don't think it has to be that expensive. Red-black tree properties are:
It should be possible to check all of these not only in linear time, but in one pass over the tree. Current implementation seems to be checking the 5th item twice:
blackHeightrecursive function (linear)leafCollector+ the loop in the end of the function (lines 75-97). This isThe second is ineffective and redundant. Removing it and moving all per-node checks inside the function which traverses a tree allows running all checks in one pass. This should allow running tree violation checks more often in unit tests. I will prepare a PR shortly.