自学教程：C++ AVLTree类代码示例

int main(){	AVLTree<int>* tree = new AVLTree<int>;	for (int i = 0; i < 10; i++){		int* toInsert = new int(rand()%200);		std::cout<<"inserting:"<<*toInsert<<std::endl;		tree->insert(toInsert);		// tree->printTree(AVLTree<int>::PRE_ORDER_TRAVERSAL);		// std::cout<<"**** INSERT ****/n"<<std::endl;	}	std::cout<<"/n----------- INSERTED ------------"<<std::endl;	tree->printTree(AVLTree<int>::PRE_ORDER_TRAVERSAL);	int del = 0;	std::cout<<"/n----------- TO ERASE ------------"<<std::endl;	while(del != -1){		std::cout<<"Digite un número para borrar"<<std::endl;		cin>>del;		std::cout<<"----.----"<<std::endl;		tree->erase(&del);		//tree->insert(new int(del));		tree->printTree(AVLTree<int>::PRE_ORDER_TRAVERSAL);	}	return 0;}

void demo2(int n, double lf) {    //generate random strings    fp = fopen("test2.txt", "w");    string *v = new string[n + 10];    time_t t1;    AVLTree<string, bool> used;    OpenStrHashTable<int> openhash(ceil((double)n / lf));    ListStrHashTable<int> listhash(ceil((double)n / lf));    cout << "Generating data:" << endl;    for (int i = 1; i <= n; ) {        string s;        int len = ceil(log(n)/log(3)) + rand() % 15; // min length satisfying(3^len>n) +- 3        for (int j = 1; j <= len; ++j)            s += (33 + rand()%(127-33));        if (used.hasKey(s)) {            //cout << "duplicate key:" << s << endl;            continue;        }        else {            fprintf(fp, "%s", s.c_str());            v[i++] = s;            used.insert(s, true);        }    }    cout << "Generation finished." << endl;        cout << "Inserting all (key = string, value = length) pairs to OpenStrHashTable..." << endl;    t1 = clock();    openhash.clearcrash();    for (int i = 1; i <= n; i++)        openhash.insert(v[i], v[i].length());    t1 = clock() - t1;    cout << "Crashes: " << openhash.crashcount << ", Time used: " << (double)t1/CLOCKS_PER_SEC << endl;        cout << "Searching all keys in OpenStrHashTable..." << endl;    t1 = clock();    openhash.clearcrash();    for (int i = 1; i <= n; i++)        openhash.get(v[i]);    //cout << v[i] << ": " << openhash.get(v[i]) << endl;    t1 = clock() - t1;    cout << "Crashes: " << openhash.crashcount << ", Time used: " << (double)t1/CLOCKS_PER_SEC << endl;        cout << "Inserting all (key = string, value = length) pairs to ListStrHashTable..." << endl;    listhash.clearcrash();    t1 = clock();    for (int i = 1; i <= n; i++)        listhash.insert(v[i], v[i].length());    t1 = clock() - t1;    cout << "Crashes: " << listhash.crashcount << ", Time used: " << (double)t1/CLOCKS_PER_SEC << endl;        cout << "Searching all keys in ListStrHashTable..." << endl;    t1 = clock();    listhash.clearcrash();    for (int i = 1; i <= n; i++)        listhash.get(v[i]);    //cout << v[i] << ": " << listhash.get(v[i]) << endl;    t1 = clock() - t1;    cout << "Crashes: " << listhash.crashcount << ", Time used: " << (double)t1/CLOCKS_PER_SEC << endl;}

int main(){    AVLTree<char> Tree;        std::string input("ABCDEF"), str;    for( auto x: input )        Tree.add(x);                // std::function<void(const char& )> visit =                         // []( const char& x)                        // { std::cout << x << ' '; } ;    // Tree.display (visit ) ;        std::function<void(const char& )> visit1 =                         [&str]( const char& x)                        { str+=x; } ;                            Tree.display ( visit1 ) ;        assert( str == "DBEACF" );     assert( Tree.count() == input.length() );    assert( Tree.contains('E') == true );     assert( Tree.contains('X') == false );         return 0;}

intmain() {  AVLTree<int>	t;  std::cout << "ajout de 1" << std::endl;;  t.push(1);  /*  std::cout << std::endl << std::endl << "ajout de -10" << std::endl;  t.push(-10);  std::cout << std::endl << std::endl << "ajout de -11" << std::endl;  t.push(-9);  */  /*std::cout << "ajout de -12" << std::endl;  t.push(-12);  */  /*std::cout << "ajout de -13" << std::endl;    t.push(-13);*/  std::cout << "ajout de 15" << std::endl;  t.push(15);  std::cout << "ajout de 10" << std::endl;  t.push(10);  /*    std::cout << "ajout de 21" << std::endl;    t.push(21);    std::cout << "ajout de 23" << std::endl;    t.push(23);  */  //t.push(1);  t.applyToTree(display);}

/* * removal */intAVLTree::Remove (AVLTree * &racine, bool rebalance){  AVLTree *startNode = NULL;  int remDiff = 0;  int res = Remove (racine, startNode, remDiff);  if (res == avl_no_err && rebalance && startNode)    res = startNode->RestoreBalances (remDiff, racine);  return res;}

int main(){	cout<<"AVL Tree/n";	int arr[] = {5,4,3,6,8,2,1};	cout<<"Print elements :";	for(int i=0;i<7;i++)		cout<<arr[i]<<" ";	cout<<"/n/n";	AVLTree<int> a;		for(int i=0;i<7;i++)		a.insert(arr[i]);	cout<<"PreOrder :";	a.preOrder();	cout<<"/nInOrder :";	a.inOrder();	cout<<"/nPostOrder :";	a.postOrder();    cout<<"Remove 6/n";  a.remove(6);  cout<<"PreOrder :";	a.preOrder();	cout<<"/nInOrder :";	a.inOrder();	cout<<"/nPostOrder :";	a.postOrder();	return 0;}

TEST(AVLTree, Insert) {  {  AVLTree<int, int> a;  for (int i = 0; i < 1000; i++) {    a.Insert(i, i * i);    for (int k = 0; k <= i; k++) {      ASSERT_EQ(a.Find(k).first, k * k);      ASSERT_TRUE(a.Find(k).second);    }  }  }  {  AVLTree<int, int> a;  for (int i = 100; i > 0; i--) {    a.Insert(i, i * i);    for (int k = i; k <= 100; k++)      ASSERT_EQ(a.Find(k).first, k * k);  }  }  AVLTree<int, int> b;  mt19937_64 _e1(chrono::system_clock::now().time_since_epoch().count());  std::uniform_int_distribution<int> dist(0, 1000000);  for (int i = 0; i < 1000; i++) {    int t = dist(_e1);    b[t] = i * i;    ASSERT_EQ(b.Find(t).first, i * i);  }}

void TestAVLTree(){	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };	// int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };	AVLTree<int, int> tree;	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)	{		tree.Insert(arr[i]);	}	tree.InOrder();}

void AVLStressSmall(void){  const char *test = "AVLStressSmall";  std::cout << "/n====================== " << test << " ======================/n";  int *ia = 0;  try  {    AVLTree tree;    int correct_nums[] = {1, 15, 22, 20, 12, 3, 0, 19, 18, 17, 8, 10, 9, 24, 6, 11, 4, 21, 7, 14, 13, 23, 5, 2, 16};    int size = 25;    ia = new int[size];    for (int i = 0; i < size; i++)      ia[i] = correct_nums[i];    //Shuffle(ia, size, 1);    Print(ia, size);    for (int i = 0; i < size; i++)    {      tree.insert(ia[i]);      //PrintInfo(tree);      std::cout << "Insert item #" << i << ":" << ia[i] << " =========================================/n";      PrintBST(tree);    }    PrintInfo(tree);    //PrintBST(tree);    Shuffle(ia, size, 1);    for (int i = 0; i < size - 10; i++)    {      tree.remove(ia[i]);      std::cout << "Remove item #" << i << ":" << ia[i] << " =========================================/n";      PrintBST(tree);    }    PrintInfo(tree);    PrintBST(tree);    if (tree.ImplementedIndexing())      for (unsigned i = 0; i < tree.size(); i++)        std::cout << "Index " << i << ": " << tree[static_cast<int>(i)]->data << std::endl;  }  catch(const BSTException& e)  {    std::cout << "Exception caught: " << e.what() << std::endl;  }  catch(...)  {    std::cout << "Unknown exception." << std::endl;  }  delete [] ia;}

void runTest(const vector< pair<K, V> > & elems, const string & filename){    AVLTree<K, V> tree;	stringstream output;    tree.setOutput(output);    for(auto elem = elems.begin(); elem != elems.end(); ++elem)        tree.insert(elem->first, elem->second);    tree.print(output);    ASSERT_TREE_EQUALS(output.str(), filename);}

int main() {	//freopen("..//advanced-pat-python//test.txt", "r", stdin);	int N;	cin >> N;	AVLTree tree;	int tmp;	while (N--) {		cin >> tmp;		tree.insert(tmp);	}	cout << tree.root->value << endl;}

void testRotateRightLeft(){	AVLTree<int, int> tree;	printHeader("Right-Left Rotation");	tree.insert(3, 3);	tree.insert(8, 8);	printBefore();	tree.print();	printAfter(6);	tree.insert(6, 6);	tree.print();	printEnd();}

int main(void) {	int n;	AVLTree tree;	scanf("%d", &n);	for (int i = 0; i < n; i++) {		int x;		scanf("%d", &x);		tree.insert(x);	}	printf("%d/n", tree.getRoot());	system("pause");	return 0;}

int main(){	AVLTree T;	char ch;	int n;	while(1)	{		cin >> ch ; 		switch(ch)		{			case'I':cin >> n;				T.insert(n);				break;			case'T':T.traverse(T.getroot());				break;			case'S':cin >> n;				cout << T.search(n,T.getroot())<<endl;				break;			case'D':cin >> n;				T.delnode(n);				break;			case'R':cout<< T.getroot()->data<<endl;				break;			case'X':return 0;		}	}}

int main(){	AVLTree al;	for (int i = 1; i < 10; i ++) {		al.Insert(i);			}	al.Print();	for (int i = 1; i < 10; i += 2) {		al.Delete(i);		al.Print();	}	return 0;}

/*	Test the AVLTree*/void main(){	AVLTree<int>* avl;	avl = new AVLTree<int>(30);	avl = avl->insert(30);	avl = avl->insert(20);	avl = avl->insert(40);	avl = avl->insert(15);	avl = avl->insert(25);	avl = avl->insert(10);// should also balance the tree	delete avl;	system("pause");}

void TestAVLTree(int argc, char **argv){	int array[TREE_SIZE];	int seed;	bool IsInsert;	if (argc == 2)		seed = atoi(argv[1]);	else		seed = time(0) *257%32768;	SimpleCompareNodesAlgorithm<int, int> CompareAlgorithm;	for (int iteration = 1; iteration <= N_ITERATIONS; iteration++)	{		AVLTree<int, int> *tree;		int i;		printf("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);		fflush(stdout);		srand(seed++);		for (i = 0; i < TREE_SIZE; i++)			array[i] =  i;		Shuffle(array, TREE_SIZE);		tree = new AVLTree<int, int>(&CompareAlgorithm);		for (i = 0; i< TREE_SIZE; i++)			tree->Search(&(array[i]), &IsInsert);		//		if (tree->Verify(&IsDone))//			return;		for(i = 0; i < TREE_SIZE; i++)		{			tree->Delete(&(array[i]));//			if (tree->Verify(&IsDone))//				return;		}		printf("/ttest good./n");		fflush(stdout);		delete tree;	}}

int main(){		//avl tree    cout<<endl << "avl test :"<<endl;    AVLTree<int> te;    for (int i=0;i<10;i++)    {        te.insert(i);    }    te.Treversal();    cout << endl;	return(0);}

int main(){	AVLTree rbt;	vector<int> values = { 10, 5, 2, 1, 3, 7, 15, 25, 30 };	for (auto v : values) {		rbt.add(v);	}	values = { 45, 36, 67, 90, 04, 23, 52, 11 };	for (auto v : values){		rbt.add(v);		rbt.print();		cin.ignore(1);	}	return 0;}

int main() {  AVLTree tree;  tree.insert(3);  tree.insert(5);  tree.insert(4);  //tree.DFS(print);  rotateRight(tree.root->right);  rotateLeft(tree.root);    printer.start();  tree.DFS(print);  printer.end();}

int main() {  AVLTree avl;  while (cin.good()) {    string instr, word;    cin >> instr;    cin >> word;    if (instr == "I") {      avl.insert(word);    } else if (instr == "R") {      avl.remove(word);    } else if (instr == "L") {      cout << "AVL path: " << avl.pathTo(word) << endl;    }  }  cout << "AVL numNodes: " << avl.numNodes() << endl;}

 int reversePairs(const vector<int> &nums) {     AVLTree tree;     int ans = 0;     for (int n : nums) {         int64_t test_num = 2 * (int64_t)n;         if (test_num >= numeric_limits<int>::max()) {             // noop         } else if (test_num < numeric_limits<int>::min()) {             ans += tree.size();         } else {             ans += tree.count_gt(test_num);         }         tree.insert(n);     }     return ans; }

void testFind(){	AVLTree<string, string> tree;	printHeader("Testing Find");	tree.insert("C", "C++");	tree.insert("free", "delete");	tree.insert("malloc", "new");	tree.insert("bool", "void");	cout << "find(C) -> " << tree.find("C") << endl;	cout << "find(free) -> " << tree.find("free") << endl;	cout << "find(malloc) -> " << tree.find("malloc") << endl;	cout << "find(bool) -> " << tree.find("bool") << endl;	printEnd();}

int main() {	AVLTree BST;	string insertKey[] = { "one", "two", "thr", "fou", "fiv", "six", "sev", "eig", "nin", "ten", "ele", "twe", "thi", "fout", "fift", "sixt", "sevt", "eigt", "nint", "twet" , "tone", "ttwo", "tthr", "tfou", "tfiv", "tsix", "tsev", "teig", "tnin", "thit" };	//string insertKey[] = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20" };	try {		cout << "
C++ AVSValue类代码示例
C++ AVEC类代码示例