rb_tree_test.cc File Reference

Tests for Red-Black Tree (tpl_rb_tree.H) More...

#include <algorithm>
#include <random>
#include <set>
#include <vector>
#include <gtest/gtest.h>
#include <tpl_rb_tree.H>

Include dependency graph for rb_tree_test.cc:

Go to the source code of this file.

Classes
class	RbTreeTest

Functions
	TEST_F (RbTreeTest, EmptyTreeHasZeroSize)
	TEST_F (RbTreeTest, InsertIncreasesSize)
	TEST_F (RbTreeTest, SearchFindsInsertedKeys)
	TEST_F (RbTreeTest, RemoveDecreasesSize)
	TEST_F (RbTreeTest, RemoveNonExistentReturnsNull)
	TEST_F (RbTreeTest, SingleInsertMaintainsRbProperties)
	TEST_F (RbTreeTest, MultipleInsertsMaintainRbProperties)
	TEST_F (RbTreeTest, SequentialInsertsMaintainRbProperties)
	TEST_F (RbTreeTest, ReverseInsertsMaintainRbProperties)
	TEST_F (RbTreeTest, RemoveMaintainsRbProperties)
	TEST_F (RbTreeTest, MultipleRemovesMaintainRbProperties)
	TEST_F (RbTreeTest, InorderTraversalIsSorted)
	TEST_F (RbTreeTest, MinAndMaxFromInorder)
	TEST_F (RbTreeTest, RandomInsertsMaintainRbProperties)
	TEST_F (RbTreeTest, RandomInsertsAndRemovesMaintainRbProperties)
	TEST_F (RbTreeTest, HeightIsLogarithmic)
	TEST_F (RbTreeTest, DuplicateMaxKeyZeroPopBranch)
	TEST_F (RbTreeTest, Property_DuplicateMax_RandomisedStress)
int	main (int argc, char **argv)

Detailed Description

Tests for Red-Black Tree (tpl_rb_tree.H)

Tests the bottom-up Red-Black tree implementation including:

• Basic operations (insert, search, remove)
• Red-Black properties verification
• Iterator traversal
• Copy/move semantics
• Stress tests with random data

Definition in file rb_tree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 410 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [1/18]

TEST_F	(	RbTreeTest	,
		DuplicateMaxKeyZeroPopBranch
	)

Definition at line 362 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [2/18]

TEST_F	(	RbTreeTest	,
		EmptyTreeHasZeroSize
	)

Definition at line 141 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [3/18]

TEST_F	(	RbTreeTest	,
		HeightIsLogarithmic
	)

Definition at line 340 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [4/18]

TEST_F	(	RbTreeTest	,
		InorderTraversalIsSorted
	)

Definition at line 264 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), and keys.

TEST_F() [5/18]

TEST_F	(	RbTreeTest	,
		InsertIncreasesSize
	)

Definition at line 147 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [6/18]

TEST_F	(	RbTreeTest	,
		MinAndMaxFromInorder
	)

Definition at line 274 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), and keys.

TEST_F() [7/18]

TEST_F	(	RbTreeTest	,
		MultipleInsertsMaintainRbProperties
	)

Definition at line 204 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [8/18]

TEST_F	(	RbTreeTest	,
		MultipleRemovesMaintainRbProperties
	)

Definition at line 241 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [9/18]

TEST_F	(	RbTreeTest	,
		Property_DuplicateMax_RandomisedStress
	)

Definition at line 381 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and rng.

TEST_F() [10/18]

TEST_F	(	RbTreeTest	,
		RandomInsertsAndRemovesMaintainRbProperties
	)

Definition at line 305 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST_F() [11/18]

TEST_F	(	RbTreeTest	,
		RandomInsertsMaintainRbProperties
	)

Definition at line 288 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST_F() [12/18]

TEST_F	(	RbTreeTest	,
		RemoveDecreasesSize
	)

Definition at line 171 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [13/18]

TEST_F	(	RbTreeTest	,
		RemoveMaintainsRbProperties
	)

Definition at line 229 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [14/18]

TEST_F	(	RbTreeTest	,
		RemoveNonExistentReturnsNull
	)

Definition at line 185 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [15/18]

TEST_F	(	RbTreeTest	,
		ReverseInsertsMaintainRbProperties
	)

Definition at line 220 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [16/18]

TEST_F	(	RbTreeTest	,
		SearchFindsInsertedKeys
	)

Definition at line 158 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [17/18]

TEST_F	(	RbTreeTest	,
		SequentialInsertsMaintainRbProperties
	)

Definition at line 210 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [18/18]

TEST_F	(	RbTreeTest	,
		SingleInsertMaintainsRbProperties
	)

Definition at line 198 of file rb_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().