缘起 最近在复习数据结构，顺便把以前自己写的博客简单的看了一遍，然后发现了一篇手写AVL树的博客 徒手写的AVL竟然比STL中的红黑树效率更高？✨，看了下代码，风格确实不忍直视，尤其比较草率的测试方式。所以我决定重新对 AVL 和 stl的红黑树进行测试对比，顺便也复习下左旋、右旋、寻找结点的前驱后继，方便为手写红黑树打基础。性能测试测试代码#include <iostream> #include<vector> #include<set> #include "AVLTree.h" #include "SimpleBenchTool4cpp/runtime_assert.hpp" #include "SimpleBenchTool4cpp/timer.hpp" //测试规模 const int testNum = 1000000; //验证内容是否一致 void validSequence(AVLTree& avl, std::set<int>& rb) { auto avlIter = avl.begin(); auto rbIter = rb.begin(); while (avlIter != avl.end()) { assert(*avlIter == *rbIter); ++avlIter; ++rbIter; } assert(rbIter == rb.end()); } //产生随机序列 std::vector<int> genRandomNum() { srand(time(NULL)); std::vector<int> ret; for (int i = 0; i < testNum; i++) { ret.push_back(rand() % testNum); } return ret; } //测试插入操作 void testAVLTreeInsert(AVLTree& avl, std::set<int>& rb, std::vector<int>& src) { { Timer t; for (auto n : src) { avl.insert(n); } } { Timer t; for (auto n : src) { rb.insert(n); } } validSequence(avl, rb); } //测试遍历操作 void testAVLTreeIter(AVLTree& avl, std::set<int>& rb) { int n1, n2; { Timer t; for (int num : avl) { n1 = num; } } { Timer t; for (int num : rb) { n2 = num; } } assert(n1 == n2); } //测试查找操作 void testAVLTreeFind(AVLTree& avl, std::set<int>& rb, std::vector<int>& src) { assert(avl.size() == rb.size()); { Timer t; for (auto&& n : src) { assert(avl.find(n)); } } { Timer t; for (auto&& n : src) { assert(rb.find(n) != rb.end()); } } } //测试删除操作 void testAVLErase(AVLTree& avl, std::set<int>& rb, std::vector<int>& src) { { Timer t; for (int n : src) { avl.remove(n); } } { Timer t; for (int n : src) { rb.erase(n); } } } int main() { AVLTree avl; std::set<int> rb; auto randomTestNum = genRandomNum(); std::cout << "-----------------insert--------------" << std::endl; testAVLTreeInsert(avl, rb, randomTestNum); std::cout << "-----------------iter--------------" << std::endl; testAVLTreeIter(avl, rb); std::cout << "-----------------find--------------" << std::endl; testAVLTreeFind(avl, rb, randomTestNu…