100 lines
2.0 KiB
C++
100 lines
2.0 KiB
C++
#include "RBTree.hpp"
|
|
#include "AVLTree.hpp"
|
|
|
|
using namespace Lenyiin;
|
|
|
|
void test_RBTree()
|
|
{
|
|
// int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
|
|
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
|
|
RBTree<int, int> t;
|
|
for (const auto& e : a)
|
|
{
|
|
t.Insert(std::make_pair(e, e));
|
|
}
|
|
|
|
t.PreOrder();
|
|
t.InOrder();
|
|
t.PostOrder();
|
|
t.LevelOrder();
|
|
|
|
std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;
|
|
|
|
auto node = t.Find(5);
|
|
if (node != nullptr)
|
|
{
|
|
std::cout << node->_kv.first << std::endl;
|
|
}
|
|
else
|
|
{
|
|
std::cout << "没找到" << std::endl;
|
|
}
|
|
|
|
auto pre = t.FindPredecessor(node);
|
|
if (pre != nullptr)
|
|
{
|
|
std::cout << node->_kv.first << " 的前驱节点是: " << pre->_kv.first << std::endl;
|
|
}
|
|
else
|
|
{
|
|
std::cout << "前驱节点为空" << std::endl;
|
|
}
|
|
|
|
auto suc = t.FindSuccessor(node);
|
|
if (suc != nullptr)
|
|
{
|
|
std::cout << node->_kv.first << " 的后继节点是: " << suc->_kv.first << std::endl;
|
|
}
|
|
else
|
|
{
|
|
std::cout << "后继节点为空" << std::endl;
|
|
}
|
|
|
|
t.Erase(7);
|
|
t.LevelOrder();
|
|
std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;
|
|
|
|
t.Erase(15);
|
|
t.LevelOrder();
|
|
std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;
|
|
}
|
|
|
|
void testRB_AVLTree()
|
|
{
|
|
const int n = 100000;
|
|
std::vector<int> v;
|
|
v.reserve(n);
|
|
srand(time(0));
|
|
for (size_t i = 0; i < n; i++)
|
|
{
|
|
v.push_back(rand());
|
|
}
|
|
|
|
RBTree<int, int> rbtree;
|
|
AVLTree<int, int> avltree;
|
|
|
|
size_t begin1 = clock();
|
|
for (const auto& e : v)
|
|
{
|
|
rbtree.Insert(std::make_pair(e, e));
|
|
}
|
|
size_t end1 = clock();
|
|
|
|
size_t begin2 = clock();
|
|
for (const auto& e : v)
|
|
{
|
|
avltree.Insert(std::make_pair(e, e));
|
|
}
|
|
size_t end2 = clock();
|
|
|
|
std::cout << "红黑树测试时间:" << end1 - begin1 << std::endl;
|
|
std::cout << "AVL 测试时间:\t" << end2 - begin2 << std::endl;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
test_RBTree();
|
|
testRB_AVLTree();
|
|
|
|
return 0;
|
|
} |