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)
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 359 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [1/16]

TEST_F	(	RbTreeTest	,
		EmptyTreeHasZeroSize
	)

Definition at line 141 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [2/16]

TEST_F	(	RbTreeTest	,
		HeightIsLogarithmic
	)

Definition at line 340 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [3/16]

TEST_F	(	RbTreeTest	,
		InorderTraversalIsSorted
	)

Definition at line 264 of file rb_tree_test.cc.

References inorder_keys(), and Aleph::maps().

TEST_F() [4/16]

TEST_F	(	RbTreeTest	,
		InsertIncreasesSize
	)

Definition at line 147 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [5/16]

TEST_F	(	RbTreeTest	,
		MinAndMaxFromInorder
	)

Definition at line 274 of file rb_tree_test.cc.

References inorder_keys(), and Aleph::maps().

TEST_F() [6/16]

TEST_F	(	RbTreeTest	,
		MultipleInsertsMaintainRbProperties
	)

Definition at line 204 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [7/16]

TEST_F	(	RbTreeTest	,
		MultipleRemovesMaintainRbProperties
	)

Definition at line 241 of file rb_tree_test.cc.

References Aleph::maps(), and Aleph::DynList< T >::remove().

TEST_F() [8/16]

TEST_F	(	RbTreeTest	,
		RandomInsertsAndRemovesMaintainRbProperties
	)

Definition at line 305 of file rb_tree_test.cc.

References Aleph::maps(), Aleph::DynList< T >::remove(), and rng.

TEST_F() [9/16]

TEST_F	(	RbTreeTest	,
		RandomInsertsMaintainRbProperties
	)

Definition at line 288 of file rb_tree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), rng, and Aleph::HTList::size().

TEST_F() [10/16]

TEST_F	(	RbTreeTest	,
		RemoveDecreasesSize
	)

Definition at line 171 of file rb_tree_test.cc.

References Aleph::maps(), and Aleph::DynList< T >::remove().

TEST_F() [11/16]

TEST_F	(	RbTreeTest	,
		RemoveMaintainsRbProperties
	)

Definition at line 229 of file rb_tree_test.cc.

References Aleph::maps(), and Aleph::DynList< T >::remove().

TEST_F() [12/16]

TEST_F	(	RbTreeTest	,
		RemoveNonExistentReturnsNull
	)

Definition at line 185 of file rb_tree_test.cc.

References Aleph::maps(), and Aleph::DynList< T >::remove().

TEST_F() [13/16]

TEST_F	(	RbTreeTest	,
		ReverseInsertsMaintainRbProperties
	)

Definition at line 220 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [14/16]

TEST_F	(	RbTreeTest	,
		SearchFindsInsertedKeys
	)

Definition at line 158 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [15/16]

TEST_F	(	RbTreeTest	,
		SequentialInsertsMaintainRbProperties
	)

Definition at line 210 of file rb_tree_test.cc.

References Aleph::maps().

TEST_F() [16/16]

TEST_F	(	RbTreeTest	,
		SingleInsertMaintainsRbProperties
	)

Definition at line 198 of file rb_tree_test.cc.

References Aleph::maps().